Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: 138 Games of Chess  (Citit de 7302 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
pauldb
Nu mai tace
*****

Karma: 821
Deconectat Deconectat

Mesaje: 1.901



Vezi Profilul
« : 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. Smile
Memorat

Am zis Mr. Green
wefgef
Nu mai tace
*****

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« Răspunde #1 : 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 Tongue.
Memorat

omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines