138 Games of Chess

[•pauldb]

http://acm.sgu.ru/problem.php?contest=0&problem=138

Iau 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.

[•wefgef]

Greedy-ul meu e un pic diferit. Intr-adevar, e buna observatia sa cuplezi un jucator cu valoare >1 cu 1. Insa nu e bine sa cuplezi maximul si minimul din sir. Contraexemplu nu pot sa iti dau, dar sigur au gasit aia de pe SGU .