ms mult bogdan!

nush daca e ceva evident si sunt eu neatent, dar nu inteleg de ce iau SIGSEV. am luat cateva teste si acasa imi merg. e ceva cu evaluatorul sau e de la mine? 

am observat ca multe surse care iau 100 p pe infoarena au afisaje defectuoase, cum ar fi faptul ca printeaa un ' ' inainte de '\n', ceea ce in mod normal nu ar fi corect la olimpiadele de info.

S-au schimbat cumva testele la problema asta? pe o sursa mai veche pe care luam 100 am luat acum 5 p 

shtiu ca e tarziu.. dar.. post-ul asta nu e o intrebare. Pur shi simplu sunt curios de cum ati gandit problema. Mie, pe examplul 2, daca doboara popice de la stanga la dreapta castiga afumatu' ala.. dar de la dreapta la stanga, cashtiga cel care loveste primul. Acuma.. daca iau 0 la problema asta, il invit pe Mircea sa joce un astfel de bowling ( eu cu un program care il simuleaza pe Nargy, el cu un program care simuleaza pe Fumeanu.. ) pe datele de test shi sa vedem care cashtiga .

Camd o sa aiba forumul shi imagini .gif? Unele sunt super distractive 

inca mai e timp sa modificati... preONI Runda 1, preONI Runda 2, preONI runda 3, preONI Runda 4, postONI Finala. 

Vad ca nimeni nu s-a incumetat sa raspunda intrebarii cu demonstratia. Cosmin are dreptate totusi. Citind forumul (nu am cartea, shi ma indoiesc sa fie pierduta prin vreo biblioteca din Ploiesti ) mi-am dat seama de "demonstratia intuitiva" la care se referea Cosmin.
Defapt, rezolvarea in O(1) porneste din rezolvarea logaritmica. Si iata cum:

"simetriile" despre care s-a vorbit (si de care banuiesc ca s-au prins toti care au implementat logaritmic) se bazeaza pe faptul ca, daca la un pas, una din coordonate era mai mare sau egala cu 2^k, atunci ea se decrementa cu 2^k, iar daca ambele erau mai mari decat 2^k, atunci se decrementau ambele. Ideea este ca, tabela de dimensiune 2^k+1X2^k+1 se imparte in 4 cadrane de latura 2^k. (consideram cadranele in ordine trigonometrica) Daca ne aflam in cadranul 4 , atunci solutia este identica ca si cand ne-am situa in cadranul 2, pe coordonate cu 2^k mai mici. In cadranele 1 , respectiv 3, solutia este tot ca si cand am translata cadranul in cadranul 2 ( micsorand coordonata mai mare cu 2^k ) , numai ca este ca valoare cu 2^k mai mare. Acum, dupa ce am facut reducerea la cadranul 2, aplicam recursiv pentru acesta. Suma valorilor din translatarile cadranelor 1 si 3 in cadranul 2 reprezinta solutia problemei.

Acum, varianta cu xor, care este surprinzator de asemanatoare.
Considerand reprezentarea pe biti a cordonatelor. In matricea de mai sus despre care vorbeam, pasul k ( cand dimensiunile sunt 2^k+1 ) reprezinta, defapt, perechea de biti de pe pozitia k din coordonata liniei si respectiv coloanei. ( mentionez ca prin "coordonate" ma refer la linia/coloana curenta, si acestea fiind decrementate cu 1 fata de input-ul problemei, deci primul element al tabelei se afla pe pozitia (0;0) )

Astfel, cele 4 cadrane vor fi date de perechile:
(0;0) - cadranul 2 ( ambele coordonate mai mici decat 2^k )
(0;1) - cadranul 1 ( coordonata coloanei mai mare sau egala cu 2^k )
(1;0) - cadranul 3 ( coordonata liniei mai mare sau egala cu 2^k )
(1;1) - cadranul 4 ( ambele coordonate mai mari sau egale cu 2^k )

acum, bitul k al rezultatului va trebui sa fie (dupa cum am spus la prima varianta) 0 daca ne aflam in cadranele 2 sau 4 si 1 daca ne aflam in cadranele 1 sau 3 ( adica numai in cazul translatarii din 1 sau 3 in 2 se aduna 2^k ). Iata ca , bitul k din rezultat este , defapt dat de operatia xor intre perechea de biti k descrisa mai sus:

cadranul 2 : 0 xor 0 = 0
cadranul 1 : 0 xor 1 = 1
cadranul 3 : 1 xor 0 = 1
cadranul 4 : 0 xor 0 = 0

sper ca demonstratia este suficienta si nu foarte dificil de urmarit. (daca este, va rog sa mai postati)

Nu . Face sqrt(nr_citit). credeam k net-zero e numai pt c atunci cand nu pu ireturn 0 

pey sunt km 2 chestiuni :
1) lucreaza in Pascal
2) e vb de problema chiftea, asa ca nu foloseste decat longint , un amarat de for shi sqrt().

Un prieten de-al meu a primit non-zero exit status. Imi puiteti spune ce reprezinta, va rog?

Cate teste sunt maxim intr-un input?

[d]

pey...eu am ordonat crescator, am luat-o de la cel mai mare la cel mai mic. Daca mai trebuia sa adun d ca sa obtin suma ceruta shi eram pe elementul a(i) atunci elementului a(i) ii minimul dintre d div i si b-a(i); apoi din d scadeam cat am pus lui a(i) shi treceam la a(i+1);
dupa aceea le ordonam la loc cum erau la inceput

Gresesc eu undeva la problema asta de iau 0. Primesc WA pe unele teste, dar unele fac shi TLE. Nu pricep cum iau TLE pe o rezolvara O(n*log(n))... Pot posta ideea mea de rezolvare ca sa imi spuneti macar daca merita sa mai incerc sau nu?

shi eu ce spuneam???!!! E back! E back!    ^

nu shtiu cum faci U parcurgerea, dar dak porneshti sa spunem din 000 pt. n=3 ar trebui sa treci prin drumul:
000>001>010>101>011>111>110>100
cum fiecare nod din graph are exact 2 fii, poti retine ushor in care din ei te-ai dus la un moment dat, codificand fiul mai mic al unui nod cu 0 shi pe celalalt cu 1. pt. ex de mai sus ai avea:
(radacina : 000)>1>0>1>1>1>0>0
dak il citeshti asha, vei vedea k e raspunsul corect . Oricum, secventa se genereaza back, in maxim 2^n (2^20 ~ 1 000 000). Pornind cu radacina in 0..000 (sau maxim in 0..001) vei avea minim lexicografic.

______________
Rog moderatorii Infoarena sa stearga acest post daca nu corespunde cerintelor forumului

Iti multumesc mult! Cred k am o greseala pe undeva.Raspunsul meu nu era minim lexicografic after all.. 

Am vazut k evaluarea se face pe 20 de teste (f. probabil pt. toate cele 20 de valori ale lui n). Am rezolvat problema, iar mie, acasa , pt. testele cu n=(1, 2, 3, 4) imi da corect (cel putin pt. aceste teste.. tind sa cred k shi celelalte raspunsuri sunt tot corecte  ). Oricum, iau doar 5 p. Nu primesc TLE, ci WA (timpul maxim e de 0.14 s/ test).

  Va rog, daca se poate, sa imi dati un exemplu de output corect pt n intre 4 shi 6 k sa ma asigur k am facut bine... Chiar nu inteleg unde pot sa greshesc. Am tinut cont shi de prioritatea lexicografica.

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

un subsir format dintr-un singur element nu este maximal si de lungime minima?