422 Dist

[•DITzoneC]

Aici puteţi discuta despre problema Dist.

[•bogdan2412]

am inceput sa ma uit pe sursa mea de acu un an sa vad de ce-mi da numaru prost de mutari pe 3 teste

Pe exemplul

Cod:

AA
A A A

e clar ca in solutia optima propozitia a doua ar arata asa "AA A".

Sursa de la lot dadea "1 1" si sursa mea dadea "1 2" care mi se parea bine. Din "A", "A", "A" ajungeam in "AA", "", "A" si dup-aia in "AA", "A", "". Scria in enunt ca nu pot exista cuvinte goale in mijlocul propozitiei.

Am presupus ca atunci cand aplici operatia asupra unui cuvant de o singura litera dupa aceea se considera ca nu mai exista cuvantul acela. Dar atunci pe

Cod:

AAA
A A A A

sursa oficiala ar fi trebuit sa dea "1 2", in timp ce ea da "1 3".

[Later edit]
Sursa mea da "1 5" pt "AAA" si "A A A A".

[•bogdan2412]

*BUMP*

Sunt 2 persoane care au luat 100 de puncte la problema asta si nu au copiat sursa oficiala: Florin Ghesu si Mircea Pasoi. Pentru ambii testele de mai sus dau la fel ca sursa oficiala.

Mie mi se pare clar ca nu e bine sa dea asa si as schimba testele astfel incat sa dea la fel ca sursa mea. Pe testele de mai sus sursa mea da "1 2" si "1 5" cum mi se pare corect.

Daca cei care au luat 100 de puncte considera ca nu e bine cum zic eu ii rog sa-mi explice aici de ce Saptamana viitoare probabil voi schimba testele, daca nu e nimeni care zice ca e incorect ce zic eu.

[•floringh06]

m-am mai uitat si eu peste sursa Bogdan... e intr-adevar putin ciudat.  Eu am considerat chiar ce ai presupus tu mai sus, un cuvant dispare  daca termin literele din el. Am folosit restrictia lor exact la calcularea costului.
Nu ar trebui totusi pe exemplul AAA sa dea 1 3 (cu presupunerea ca nu avem cuvinte vide). Cu o mutare cuplezi A-urile din mijloc si cu inca 2 mutari le duci la primul A. Sper sa nu gresesc.

[•bogdan2412]

Nu ar trebui totusi pe exemplul AAA sa dea 1 3 (cu presupunerea ca nu avem cuvinte vide). Cu o mutare cuplezi A-urile din mijloc si cu inca 2 mutari le duci la primul A. Sper sa nu gresesc.

Din 2 mutari mi se pare ca poti face asa (presupunand ca nu exista cuvinte vide):

Din "A A A A" mutam al doilea A la sfarsitul primului si obtinem "AA A A" si acum mutam al treilea A (al doilea cuvant) la sfarsitul primului cuvant si obtinem "AAA A".

Sper sa nu-mi scape mie vreo restrictie si sa zic prostii.

Dupa cum vad eu problema, orice varianta am alege: cand un cuvant ramane fara litere dispare sau continua sa existe, trebuie precizat asta clar in enunt si tb refacute testele Eu tind catre varianta un cuvant din mijloc care ramane fara litere nu se opreste din existat, pentru ca e mai usor de implementat asa .

PS: Sursa mea de la dist din concurs avea cateva buguri si nu era buna Vorbesc acum de cea din arhiva: http://infoarena.ro/job_detail/54692 care nu cred ca ai cum sa o vezi. Poti sa ti-o dau pe PM daca vrei.

[•floringh06]

mda..  ai dreptate cu 1 2.. Ar fi mai bine sa schimbam testele dupa ideea ta, asa ar deveni si enuntul mai clar, nu ar mai fi interpretabil. O sa incerc cat pot de repede [eu am bacu acum  ] sa modific in sursa mea. Trimite-mi te rog si implementarea ta. Am acelasi id ca pe arena si pe yahoo. Mersi

[•bogdan2412]

Am schimbat testele si am reevaluat. Sper ca sursa mea e ok, cand mai ia cineva 100 de puncte putem fi siguri Este o sursa a lui Marius Stroe care ia 90 de puncte acum si pica pe un test pe care eu stiu ca-l picam pentru ca primul meu cuvant putea avea lungime > 20. Numarul de mutari ii da la fel insa pe celelalte teste, deci cred ca e ok.

[•wefgef]

Mai schimba marmota testele ca sa ia 100

[•bogdan2412]

Mai schimba marmota testele ca sa ia 100

Pai daca nu erau bune... Pare destul de argumentata schimbarea.

[•Marius]

Testul 3 se pică dacă se adaugă cuvinte de lungime 0 la începutul propoziţiei.

Acum iau şi eu 100.