BitCell

Your IT power source

Skip to content


[16] Concurs - Carte

Post a reply

[16] Concurs - Carte

Postby cata45 » 03 Oct 2011, 16:03

Marinica a scris o carte cu care se lauda mereu. La un moment dat, un prieten de-al sau il intreaba de cate ori apare cifra X in numerotarea paginilor. Marinica va cere ajutorul. :)

Cartea are N pagini. Numerotarea paginilor incepe cu 1.

In fisierul bitcell16.in se afla N si X.

Exemplu:

bitcell16.in __________________ 0 puncte
Line number On/Off | Expand/Contract | Select all
  1. 7
  2. 5

bitcell16.out
Line number On/Off | Expand/Contract | Select all
  1. 1
  2.  

Paginile sunt: 1 2 3 4 5 6 7 , iar 5 apare o singura data in numerotarea lor.


bitcell16.in __________________ 0 puncte
Line number On/Off | Expand/Contract | Select all
  1. 11
  2. 1

bitcell16.out
Line number On/Off | Expand/Contract | Select all
  1. 4
  2.  

Paginile sunt: 1 2 ... 10 11 , iar 1 apare de 4 ori in numerotarea lor.

Restrictii si precizari
  • 0<N<=10000
  • 0<=X<=9

Data start: 03/10/2011
Data stop : 09/10/2011 (Pe 10 incepe cursul de inteligenta artificiala de la Stanford :) )
Desemnare castigator : 10/10/2011
0,0p / 0 votes
The EARTH without ART is just EH.
User avatar
cata45
Byte
 
Joined: 02 Sep 2010
Status: 9

Re: [16] Concurs - Carte

Postby andreiandreiq » 03 Oct 2011, 17:28

Salut,

Am o întrebare, dacă numărul la pagina este de ex: 22, iar numărul căutat este 2. Pentru pagina 22 se iau în considerare 2 afișări, nu?
0,0p / 0 votes
Image
User avatar
andreiandreiq
Word
 
Joined: 30 Dec 2009
Status: 33.33

Re: [16] Concurs - Carte

Postby cata45 » 03 Oct 2011, 17:55

Da... am dat un exemplu cu 11... paginile pana la 11 (inclusiv) sunt 1 2 3 .... 10 11
Si se foloseste 1 la pagina 1, la pagina 10 si de doua ori la pagina 11 (in total de 4 ori)
0,0p / 0 votes
The EARTH without ART is just EH.
User avatar
cata45
Byte
 
Joined: 02 Sep 2010
Status: 9

Re: [16] Concurs - Carte

Postby andreiandreiq » 03 Oct 2011, 19:07

Ah, da... nu am fost atent (eram obosit).

My bad.
0,0p / 0 votes
Image
User avatar
andreiandreiq
Word
 
Joined: 30 Dec 2009
Status: 33.33

Re: [16] Concurs - Carte

Postby new_luca » 06 Oct 2011, 00:07

Astazi, dupa 6 zile de stat fara PC (a inceput facultatea, Bucuresti ,camin , mutat, monitor lipsa ;))) mare mi-a fost bucuria sa vad ca s-a propus alta problema =P~ (tot vreau sa inteleg algoritmii pentru [15]Concurs - Dezastru Nuclear, dar nu am reusit inca). Asa ca uitati rezolvarea mea :

Download
1p / 1 votes
Image
User avatar
new_luca
Byte
 
Joined: 03 Jul 2011
Location: Gaesti
Status: 12

Re: [16] Concurs - Carte

Postby cata45 » 06 Oct 2011, 22:41

Sa imi trimiti PM cu sursa. E valabil pentru toti care trimit solutii la problema.

L.E
In legatura cu concursul 15 ... voi scrie un articol cand voi avea timp
0,0p / 0 votes
The EARTH without ART is just EH.
User avatar
cata45
Byte
 
Joined: 02 Sep 2010
Status: 9

Re: [16] Concurs - Carte

Postby Mihai » 10 Oct 2011, 06:59

Am avut ceva timp liber așa că m-am băgat și eu la concursul ăsta. Totuși, din cauză că nu pot compila codul pentru Windows, am așteptat să se termine concursul și să postez direct sursa. Rezolvarea mea, în O(N), unde N reprezintă numărul de cifre al numărului de pagini:

Line number On/Off | Expand/Contract | Select all
  1. #include <stdio.h>
  2.  
  3. int numarAparitii(int numar, int cifra, int sufix=0, int putere=1)
  4. {
  5.     if(numar!=0)
  6.     {
  7.         int t1=numarAparitii(numar/10,cifra,sufix+(numar%10)*putere,putere*10);
  8.         int t2=(numar/10)*putere;
  9.         if(cifra==0&&t2)
  10.             t2-=putere;
  11.         int t3=(cifra==0&&numar<=9)?0:(numar%10==cifra?sufix+1:numar%10>cifra?putere:0);
  12.         return t1+t2+t3;
  13.     }
  14.     else
  15.         return 0;
  16. }
  17.  
  18. int main()
  19. {
  20.     int nPagina, cPagina;
  21.     fscanf(fopen("bitcell16.in","r"),"%d%d",&nPagina,&cPagina);
  22.     fprintf(fopen("bitcell16.out","w"),"%d\n",numarAparitii(nPagina,cPagina));
  23.     return 0;
  24. }
3p / 1 votes
User avatar
Mihai
Byte
 
Joined: 29 Dec 2009
Status: 25

Re: [16] Concurs - Carte

Postby cata45 » 10 Oct 2011, 13:47

Testul 1 (10 puncte)
in: 1235 2
ok: 390
mihai.out: 390 OK
luca.out: 390 OK
_____________________________________

Testul 2 (10 puncte)
in: 0 9
ok: 0
mihai.out: 0 OK
luca.out: 0 OK
_____________________________________

Testul 3 (10 puncte)
in: 2 1
ok: 1
mihai.out: 1 OK
luca.out: 1 OK
_____________________________________

Testul 4 (10 puncte)
in: 25 2
ok: 9
mihai.out: 9 OK
luca.out: 9 OK
_____________________________________

Testul 5 (10 puncte)
in: 11 1
ok: 4
mihai.out: 4 OK
luca.out: 4 OK
_____________________________________

Testul 6 (10 puncte)
in: 9999 9
ok: 4000
mihai.out: 4000 OK
luca.out: 4000 OK
_____________________________________

Testul 7 (20 puncte)
in: 10000 0
ok: 2893
mihai.out: 2893 OK
luca.out: 2893 OK
_____________________________________

Testul 8 (20 puncte)
in: 555 2
ok: 216
mihai.out: 216 OK
luca.out: 216 OK
_____________________________________

Acestea au fost testele. Cea mai buna rezolvare a fost oferita de Mihai (media de timp pe teste a fost sub 0.0001 sec). - Din pacate nu a trimis rezolvarea pana pe data de 9/10/2011, dar nici new_luca nu a trimis sursa.
Castigatorul este......(suspans )
Offtopic
Felcitari... te asteptam cu noul concurs.
0,0p / 0 votes
The EARTH without ART is just EH.
User avatar
cata45
Byte
 
Joined: 02 Sep 2010
Status: 9

Re: [16] Concurs - Carte

Postby new_luca » 10 Oct 2011, 14:02

Am trimis sursa chiar in ziua in care ai postat ca nu am trimis-o.
Am cautat-o in contul meu si nu exista, singura explicatie la care ma pot gandi e ca a fost ceva cu conexiunea de internet , nu?

Si programul meu ce medie de raspuns ca timp a avut pe teste ?

Lasand problemele tehnice la o parte aici este sursa mea :
Line number On/Off | Expand/Contract | Select all
  1. #include <stdio.h>
  2.  
  3. int functie(int);
  4. const int cifra, numar_pagini;
  5.  
  6. int main(void)
  7. {
  8.     int i, aparitii = 0;
  9.     freopen("bitcell16.in", "r", stdin);
  10.     freopen("bitcell16.out", "w", stdout);
  11.    
  12.     scanf("%d", &numar_pagini);
  13.     scanf("%d", &cifra);
  14.    
  15.     for(i = 1;i <= numar_pagini;i++)
  16.     {
  17.         aparitii += functie(i);
  18.     }
  19.    
  20.     printf("%d", aparitii);
  21.    
  22.     return 0;
  23. }
  24.  
  25. int functie(int numar_pagina)
  26. {
  27.     int aparitie = 0;
  28.    
  29.     while(numar_pagina)
  30.     {
  31.         if(numar_pagina % 10 == cifra)aparitie++;
  32.         numar_pagina /= 10;
  33.     }
  34.     return aparitie;
  35. }
  36.  
0,0p / 0 votes
Image
User avatar
new_luca
Byte
 
Joined: 03 Jul 2011
Location: Gaesti
Status: 12

Re: [16] Concurs - Carte

Postby cata45 » 10 Oct 2011, 19:58

Ca exemplu, am modificat sursele voastre sa accepte N teste si am bagat si numere mai mari de 10000. Ambele surse merg si pe numere mai mari de 10000 pentru a evidentia diferenta de timp.
Pe testul:
Line number On/Off | Expand/Contract | Select all
  1. 21
  2. 1235 2
  3. 0 9
  4. 2 1
  5. 25 2
  6. 11 1
  7. 9999 9
  8. 5496 2
  9. 1239 7
  10. 555 2
  11. 10000 0
  12. 5612 3
  13. 100000 0
  14. 54456 1
  15. 1365 4
  16. 123456 9
  17. 12345 5
  18. 55489 1
  19. 14587 5
  20. 4557 2
  21. 214165 7
  22. 225441 1
  23.  

Ambele surse returneaza raspuns corect:
Line number On/Off | Expand/Contract | Select all
  1. 390
  2. 0
  3. 1
  4. 9
  5. 4
  6. 4000
  7. 2700
  8. 344
  9. 216
  10. 2893
  11. 2721
  12. 38894
  13. 32396
  14. 377
  15. 58985
  16. 4665
  17. 32699
  18. 5407
  19. 2416
  20. 105226
  21. 220695


timp luca pe testul de mai sus: 0.047 s
timp Mihai pe testul de mai sus: 0 (nu se poate cronometra) deci timpul este mai mic de 0.0001.
In concluzie diferenta de timp este aproximativ 0.0469.

L.E. (-- 10 Oct 2011, 19:58 --)

Mihai, daca nu ai timp sa propui urmatorul concurs te rog sa anunti... (poate se ofera altcineva) :)
0,0p / 0 votes
The EARTH without ART is just EH.
User avatar
cata45
Byte
 
Joined: 02 Sep 2010
Status: 9

Re: [16] Concurs - Carte

Postby Mihai » 10 Oct 2011, 21:20

Cel putin azi, ma simt mult prea obosit pentru a propune o noua tema. Voi posta totusi tema concursului maine, daca nu cumva are altcineva vreo idee de concurs si vrea sa se implice (salvandu-ma totodata si pe mine de putina munca :-" ).
0,0p / 0 votes
User avatar
Mihai
Byte
 
Joined: 29 Dec 2009
Status: 25

Re: [16] Concurs - Carte

Postby nomemory » 11 Oct 2011, 12:57

Departe de a fi o solutie eficienta, o implementare in BASH ar arata asa:
Line number On/Off | Expand/Contract | Select all
  1. #!/bin/bash
  2.  
  3. #
  4. # Determina de cate ori apare $2 in numerotarea paginilor de la 1 la $1
  5. #
  6. function ccount {
  7.     seq 1 $1 | tr -d "\n" | grep -o "$2" | wc -l
  8. }
  9.  
  10. #
  11. #Testam functia sa vedem daca se executa corect
  12. #
  13. TEST="1235:2:390;0:9:0;2:1:1;25:2:9;11:1:4;9999:9:4000;10000:0:2893;555:2:216"
  14. function ccount_test {
  15.     echo "ccount $1 $2 == $3"
  16.     if [ $(ccount $1 $2) -eq $3 ] ; then echo "(TRUE)" ; else echo "(FALSE)"; fi
  17. }
  18.  
  19. for data in $(echo "$TEST" | tr ";" "\n") ; do
  20.     ccount_test $(echo "$data" | tr ":" " ")
  21. done


Dupa rularea script-ului:
Line number On/Off | Expand/Contract | Select all
  1. ccount 1235 2 == 390
  2. (TRUE)
  3. ccount 0 9 == 0
  4. (TRUE)
  5. ccount 2 1 == 1
  6. (TRUE)
  7. ccount 25 2 == 9
  8. (TRUE)
  9. ccount 11 1 == 4
  10. (TRUE)
  11. ccount 9999 9 == 4000
  12. (TRUE)
  13. ccount 10000 0 == 2893
  14. (TRUE)
  15. ccount 555 2 == 216
  16. (TRUE)


Ideea este sa generezi un string concatenand toate paginile, si sa numeri de cate ori se repeta un caracter in string .
0,0p / 0 votes
User avatar
nomemory
Bit
 
Joined: 24 Aug 2011
Location: Bucuresti
Status: 2
Post a reply

Return to Concursuri de programare desktop

Who is online

Users browsing this forum: No registered users and 0 guests


Powered by phpBB © phpBB Group
cron