006 Factorial

[•Dastas]

Salut!
Daca mi-ati putea da si mie un indiciu in legatura cu ce as putea gresi...
Iau 90 de puncte, picand testele 3 si 15. Verific cand p = 1 sau cand nu exista un n! cu exact p zerouri la sfarsit si afisez -1... dar totusi pe acele 2 teste primesc raspuns gresit, si sincer nu stiu ce ar putea fi :/

Folosesc cautarea binara.

[•skyel]

si eu am avut o prob de genu asta din cate imi aduc aminte la 15 era un test de genu 60 sau 311, in mod normal ar trebui sa afiseze -1?

[•Dastas]

Atat pentru 60 cat si pentru 311, programul meu afiseaza -1...

Edit: am luat 100... cand afisam -1 afisam cu %lld, trebuia cu %d 

[•Agent_Smith]

ce ar putea fi la astea doua tete k nu-mi da 
Test Timp executie Memorie folosita Mesaj Punctaj
1      0ms              8kb                  Corect! 5
2      0ms              8kb                  Corect! 5
3      559ms           156kb               Time limit exceeded. 0
4      0ms              8kb                  Corect! 5
5      0ms              8kb                  Corect! 5
6      0ms              8kb                  Corect! 5
7      0ms              8kb                  Corect! 5 
8      0ms              8kb                  Corect! 5
9      0ms              8kb                  Corect! 5
10    0ms              8kb                  Corect! 5
11    0ms              8kb                  Corect! 5
12    0ms              8kb                  Corect! 5
13    0ms              8kb                  Corect! 5
14    0ms              8kb                  Corect! 5
15    559ms          156kb                Time limit exceeded. 0
16    0ms              8kb                  Corect! 5
17    0ms              8kb                  Corect! 5
18    1ms              8kb                  Corect! 5 
19    0ms              8kb                  Corect! 5
20    0ms              8kb                   Corect! 5
Punctaj total: 90

 
folosesc si eu cautarea binara    .. . .. PLEASE HELP 

[•devilkind]

vezi dak ai tratat cazul in care nu ai solutie. E posibil ca programu tau sa cicleze pe un astfel de caz.

[•Agent_Smith]

    si sa zicem k nu ii asta problema ce altceva ar putea fi??? 

[•DITzoneC]

Poate nu faci bine cautarea binara... se poate intampla sa cicleze daca nu ai grija la cazul cand intervalul in care ai ajuns sa cauti are lungime 2...

[•Agent_Smith]

care ar trebui sa fie intervalul de cautare??? 0 - 50000000 ajunge???

[•devilkind]

greseala ta in cu o probabilitate de 90% este acolo unde a zis adi diaconu, dak intervalul tau de cautare ar fi prea mic nu ar justifica TLE-u. Intervalul il poti lua de la 1 la 1 << 31.

[•pauldb]

Da, ce spui tu e prea mic. Mai adauga un 0. Justificare: Stii ca P<=10^8 si stii ca apare cel putin un 0 terminal din 5 in 5 numere, deci 5*10^8 e suficient.
Nu te sfatuiesc sa iei intervalul pana 2^31 pentru ca poti depasi valoarea maxima acceptata in int (long / longint) facand adunari sau alte operatii.

[•devilkind]

  yep my mistake, oricum cu unsigned long int nu cred ca ar fi problem.

[•Agent_Smith]

Tot  nu imi merge 
CE ar trebui sa fac? am un cod de 90 puncte  si nu pot lua inca 10 puncte???

[•DITzoneC]

Nu era vorba de intervalul initial in care cauti ci de intervalele la care restrangi cautarea.
Sa zicem ca ai ajuns sa cauti in intervalul [a,a+1]. Fixezi m = (a+a+1)/2=a. Si observi ca vei avea solutie in intervalul [m,a+1] deci continui cautarea aici, dar acesta este indentic cu [a,a+1]. De aici iti cicleaza la infinit.

[•Adix]

Imi spune cineva care este greseala in implementarea cautarii binare aici ? (imi da numai 55 de puncte)

Cod:

// nrz este numarul de zerouri al lui c 
// st , dr , sunt limitele cautarii
// p reprezinta numarul de intrare 
st=0;
dr=1000000000;
n=1;
if(p>0){
while(n){  c=(st+dr)/2;
              nrz=numarzerouri(c);
              if(nrz==p&&st==dr) {n=st;break;} 
              if(dr<st) {n=-1;break;} 
    	      if(p>nrz) st=c+1;
   	  	 else dr=c-1;                            
           }
}

Pana la urma am rezolvat problema cu un if care verifica inca odata la sfarsit stanga si dreapta dar sunt curios care e greseala .. help pliiiz

[•Aymd]

problema e simpla ... 12 while-uri una dupa alta si ai rezolvat problema, la toate testele in 0 ms.

[•devilkind]

problema e simpla ... 12 while-uri una dupa alta si ai rezolvat problema, la toate testele in 0 ms

ce 12 whileuri?? ce faci cu ele??

[•azotlichid]

problema e simpla ... 12 while-uri una dupa alta si ai rezolvat problema, la toate testele in 0 ms

S-a nascut un nou Ciucu 

[•sima_cotizo]

  daca nu ma insel 5^12 e maximul care furnizeaza un P pana in 10^8 ...

On topic, am refacut problema, dar pic si eu testul 1... care nu trebuie sa dea -1 (verificat cu sursa care dadea doar -1 si am primit WA)... am verificat si la afisare daca N>0 afisez N altfel afisez -1 ... ce altceva poate fi ?   

[•wefgef]

afisezi vreodata 0? scrie in enunt ca trebuie sa fie strict pozitiv ce afisezi.

Ia uite ca uneori are rost sa te citezi pe tine insuti .

Incercati si voi sa cititi posturile anterioare cand aveti o nelamurire. Nu are rost sa discutam acelasi lucru in mod repetat .

[•sima_cotizo]

Hai sa ma citez si eu pe mine:

am verificat si la afisare daca N>0 afisez N altfel afisez -1 ... ce altceva poate fi ?  

Deci verific sa afisez mereu pozitiv, intrebarea era unde altundeva poate fi greseala? si da, stiu ca s-au mai discutat, de la 85 puncte pana la 95 am mai "rafinat" solutia pe baza observatiilor voastre anterioare ... totusi nu ma prind, (cred ca) respect toate conditiile...

[•astronomy]

Poate fi P = 0 pe testul ala, tu sa faci cautarea binara in intervalul [0, INF] sa iti gaseasca N = 0 solutia si tu sa afisezi -1 cand defapt trebuia 1

[•sima_cotizo]

  faceam cautarea de la 0, dar tratam separat cazul pt P=0... acum mi-a dat

Multumesc mult! 

PS: Andrei, iarta-ma ca am postat si eu un citat din ce am zis, dar mentionasem ca verificam chestia aia si citisem tot threadul inainte... totusi greseam ceva minor...

[•Aymd]

problema e simpla ... 12 while-uri una dupa alta si ai rezolvat problema, la toate testele in 0 ms

ce 12 whileuri?? ce faci cu ele??

scaderi

[•Florian]

super tare...!!! eu sunt ink o persoana kre ia 90 de puncte din cauza unor cazuri particulare.. ..mai lucrez putin la ea, sper sa le depistez....



[later edit] aku iau 95 de puncte :rotfl:o fi vreun caz nasol??? (iau WA pe testul 5)

[•Florian]

Stie kareva ce are testul 5 de nu-mi iese?? [ps:poate a mai avut probleme cineva ku testul 5] 10x anticipat