059 Farfurii

[•domino]

Aici puteţi discuta despre problema Farfurii.

[•ParrAzitU]

Well, cat de simpla ar parea rezolvarea in O(N) , eu tot iau WA pe ultimele 2 teste si nu-mi dau sema nici cum dece.. Ma poate ajuta cineva cu ceva ?

[•sarabogdan]

100000*100001 depaseste longu asa ca am pus long long unsigned
Poate te ajuta !

[vladut.forum]

dap. si io m-am prins de o(n) in timpul concursului dar greseam la afisarea solutie si am luat credca 10 pct... vezi sa nu fi gresit ceva la afisare. acuma pot sa spun ca problema n-a fost grea. solutia in o(n) a fost prima solutie corecta de care mi-am dat seama. dap a durat pana m-am prins (40 min credca)..naf ...

[•vladcyb1]

Ce are problema asta ca iau WA pe ultimul test si am pus int64 ?
 E ceva special la el?    

[•raduzer]

Eu iau "non-zero exit status" pe ultimul test(celelalte imi merg) si eu am pus int64. Nu prea inteleg ce trebuie sa fac. Poate ma poate ajuta cineva 

EDIT: acum iau WA. L-am facut si pe k int64 (ca uitasem), dar tot nu inteleg ce nu merge

EDIT 2: am luat 100. Am facut toate variabilele int64 (inclusiv cele cu care parcurgeam de la 1 la n) si am parcurs cu while-uri.
Chiar nu inteleg de ce nu mergea, pentru ca nu trecea de limite

[•Pepelea_Flaviu]

In articolul cu solutii scrie :

pe pozitia i, daca K ≤ (N-i)*(N-i-1)/2 putem pune cel mai mic element disponibil (pentru ca in bucata de N-i ramasa putem construi cel putin *(N-i-1)/2 inversiuni), altfel punem al K-(N-i)*(N-i-1)/2 element disponibil

Daca punem al p-lea element pe pozitia i, atunci p are I = (N-i)*(N-i-1)/2+p-1 inversiuni, iar K trebuie sa fie <= I, de unde rezulta ca trebuie sa punem al K-(N-i)*(N-i-1)/2+1 element disponibil si nu K-(N-i)*(N-i-1)/2

[•S7012MY]

E o mica greseala in enunt la date de iesire :

in care au asezate pe raft.

[•krityx]

Poate sa posteze cineva testul 1? Tot iau WA pe el.