http://acm.sgu.ru/problem.php?contest=0&problem=138Iau WA pe testul 9. Rezolvarea mea e urmatoarea si nu ii gasesc contraexemplu:
La fiecare pas iau maximul si minimul din sir. Daca ambele pozitii difera de cele luate precedent, atunci aleg maximul si maximul ales in momentul precedent. (*)
Am observat ca rezolvarea aceasta nu merge pe testul urmator si m-am gandit sa o "peticesc":
9
1 1 1 1 4 1 1 5 1
Pe acest exemplu, nu pot face (*) deoarece raman cu prea multe jocuri de 1 pe final. (Pe exemplul acesta, raman cu 4 de 1, din care nu mai pot termina de aranjat jucatorii). Astfel, m-am gandit ca daca exista prea multe jocuri de 1 ca sa pot face (*), atunci cuplez fiecare valoare >1 cu 1 si cand aceasta devine 1 o cuplez cu una >1.
Daca imi puteti da un contraexemplu, ar fi binevenit.