215 Numar

[ditzone]

Aici puteţi discuta despre problema Numar.

[cristi8]

dubios ca nu iau nici un test (WA pe toate), desi la cat m-am testat, merge ok programul
vad ca s-au luat multe 100
puteti sa-mi dati macar cel mai mic test al evaluatorului ?
daca chiar nu se poate.. cine a rezolvat problema.. pe testul cu n = 987654321 va da si voua:

Cod:

-987654320 1975308642
-329218105 658436214
329218106 3
-109739364 219478738
109739365 9
-6455180 12910514
6455181 153
-378420 759442
378421 2601
-19365745 38731542
19365746 51
-1138729 2278326
1138730 867
-58097304 116194626
58097305 17
-3417344 6834978
3417345 289
54869676 18
-54869675 109739369
3227476 306
-3227475 6455257
164609051 6
-164609050 329218107
9682835 102
-9682834 19365771
493827160 2
-493827159 987654321
29048640 34
-29048639 58097313
1708456 578
-1708455 3417489
568715 1734
-568714 1139163
187260 5202
-187259 379721

?

[•alexthero]

Trebe afisate in ordine descrescatoare dupa primul termen al sumei

[cristi8]

[•alexthero]

Cod:

 Descompunerile vor fi afisate in ordine descrescatoare dupa primul numar din sir. 

[ditzone]

Enuntul din arhiva fusese introdus initial gresit.. a fost corectat intre timp...

[cristi8]

mda, am pierdut o gramada de timp sa caut vreo gresala.
100 puncte daca mai si sortez.
noapte buna.

[•wefgef]

mda, am pierdut o gramada de timp sa caut vreo gresala.
100 puncte daca mai si sortez.
noapte buna.

nu esti singurul.  

[•Viksen]

Exista vreun caz special pt. problema asta? Iau 90 de puncte shi nu inteleg de ce... Pik testul 8...
Help, please! 

[•Coty]

am si eu o problema aici... de la C:

Cod:

long long x,z;
...
		printf("%lld %lld\n",-x+1,z);

ambele sunt long long, care, din cate stiu, are semn... si la afisare am numere pozitive si.. -1:

Cod:

...
568715 1734
378421 2601
187260 5202
-187259 -1
-378420 -1
-568714 -1
-1138729 -1
...

de la ce e???    (mai am si TLE pe 8 teste, dar asta presupun ca e de la mine )

[•filipb]

Daca faci sub windows, pe devcpp de exemplu, formatul de afisare e I64d. ( primul e i mare, nu l ). Daca faci sub Linux e din cauza codului si a comportamentului programului.

[•Coty]

  si asta vine de la versiunea de gcc? (ca din cate stiu o am pe ultima)... sau pur si simplu bube de windows? (da, am uitat sa zic, acu lucrez in windows ca am reusit sa bulesc linuxu si acum imi dau numere pozitive... si, se pare, corecte)

bine, acum am de rezolvat 7 TLE-uri si... un wrong answer ?!?  se complica problema...

[Much Later Edit]
anyway, am rezolvat TLE-urile, iau 90 de puncte... tot ramane un WA pe testul 8 (am mai vazut ca au mai fost probleme cu el)... stiti ce are? sau daca e un caz special?

[•gogu]

Daca ai acolo un for pana la sqrt(n), incearca sa mergi un pic ma departe, pana cand i*(i-1)/2>N.
Asta daca ai avut aceasi idee ca si mine.

[•Coty]

   mersi, acum merge 
ok, eu luam toti divizorii lui 2*n pana la sqrt(n)... AH, mi-am dat seama, daca faceam pana la sqrt(2*n) luam 100 (am luat acum cu ideea asta)... mersi mult de indicatie 

[•pocaitu]

are cineva vreo idee de ce imi da WA la ultimul test ?

[•tm_radu]

Folosesti long long? poate de la aia ii. ce metoda folosesti?

[•pocaitu]

 pai descompun numarul n in factori primi diferiti de doi intr-un vector st[] apoi iau un i=j si un j=1<<(k+1),k=nr de factori primi-1 si merg cu un for de la i la j si aflu toate combinarile. bineinteles ca unele combinari se vor repeta asa ca le elimin la sfarsit. folosesc long long doar pt i , j, si masca cu ajutorul careia aflu reprezentarea binara a lui i;

[•Adrian001]

loool ce se intampla cu evaluatorul la prob asta??? Am crezut ca gresesc algoritmul pentru ca la testele 8 si 9 am luat TLE dar nu este asa ca am trimis o sursa in care citesc numarul de intrare si la testele 8 si 9 la fel TLE nuami daca citesc numarul Ce poate sa fie?

[•cosmin79]

Poate sa imi dea si mie cineva niste teste? Nu imi dau seama ce gresesc de iau numai 10 pct.  Multumesc anticipat

[•gorgovan]

Eu iau 60, busesc ultimele 4 teste(iau WA). Imi zice si mie cineva ce e special la ele.
Cred ca am ideea corecta(desi nu stiu sa demonstrez ce complexitate are). Eu iau 60, busesc ultimele 4 teste(iau WA). Imi zice si mie cineva ce e special la ele.

[•SpiderMan]

1. Nu trebuie sa repeti de 2 ori acelasi mesaj
2. Ai citit subiectele topicului asta ? Daca faci cumva un for i = 1 , sqrt ( n ) , fa-l pana cand i * (i - 1) / 2 > N.
3. Poate trebuie sa folosesti long long ( desi eu am folosit int si am luat 100 )
4. Vezi poate uiti 2 elemente care trebuie introduse la sfarsit : -N + 1 si N * 2.
5. Sa sortezi corect vectorul

[•gorgovan]

1. Nu trebuie sa repeti de 2 ori acelasi mesaj
2. Ai citit subiectele topicului asta ? Daca faci cumva un for i = 1 , sqrt ( n ) , fa-l pana cand i * (i - 1) / 2 > N.
3. Poate trebuie sa folosesti long long ( desi eu am folosit int si am luat 100 )
4. Vezi poate uiti 2 elemente care trebuie introduse la sfarsit : -N + 1 si N * 2.
5. Sa sortezi corect vectorul

2. Nu fac un asemenea for.
3. Folosesc si long long si double si invers(int + float).
4  Le-am introdus.
5  Nu stiu la ce sortare te referi ca eu le fac in ordine bazandu-ma pe faptul ca inputul X=s*(n+1)+n*(n+1)/2 cu s si n+1 numerele care trebuie afisate pentru o solutie anume.
Practic incep de la n=1 si calculez s-ul pana cand s>=0 si daca s este intreg am gasit o solutie, o afisez si introduc intr-un vector<int>.
Apoi cat timp vectorul nu este gol iau ultimul element si in prelucrez(cred ca cei care au facut problema de 100 si nu numai stiu la ce ma refer) si afisez solutia cu s negativ
si apoi elimin elementul din vector<int>.
In final afisez ceea ce ai zis tu.

[•SpiderMan]

Da-mi sursa ta prin P.M.

[•dornescuvlad]

Salut!
Am si eu un O(lgmax_secventa * logn).
Vreo idee pentru ceva mai optim? Nu ma prind la ce ma ajuta descompunerea in factori primi.Merci

[•cosmin79]

Gandeste-te ca daca ai un nr impar de termeni consecutivi ei pot fi scrisi: x-k,...,x-1,x,x+1,...,x+k.Suma lor o sa fie (2k+1)x.Deci poti cauta x printre divizorii lui n. Asemanator si daca ai nr par de termeni: x-(2k-1)/2,...,x-1/2,x+1/2,...x+(2k-1)/2.Suma lor este 2k*x.