Titlul: 138 Games of Chess Scris de: Paul-Dan Baltescu din Iulie 28, 2007, 09:32:18 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. :) Titlul: Răspuns: 138 Games of Chess Scris de: Andrei Grigorean din Iulie 28, 2007, 11:29:39 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 :P.
|