1265 Gheizere

[•andrei.12]

Aici puteti discuta despre problema Gheizere.

[•veleandu]

Buna.
Am o intrebare legata de problema.
Poate am inteles gresit enuntul, totul e posibil.

Am citit si solutia oficiala, dar nu am vazut nici o referinta clara la un lucru.
Cum se poate rezolva problema cu restrictiile ca nu se poate trece prin acelasi punct de 2 ori si ca nu poate sta exploratorul.

Am facut un exemplu

Cod:

2 11 2
2 2
2 5 1 6 5
2 9 1 7 5

Ambele surse oficiale ( si cea de 80 de pct si cea de 100 pct ) dau rezultatul 17.
Dar nu ar avea solutie in realitate
Sursele oficiale ofera solutie pentru ca nu tin cont de faptul ca nu poate merge in acelasi loc de 2 ori ( daca merge in sus si in jos e echivalentul ca sta .. dar si asta e "interzis" )

pe al 2-lea exemplu e mai clar, mai ales ca este si posibil .. 

Cod:

6 10 3
6 6

4 7 2 8 1
2 2 1 1 5
4 2 1 1 5

Un desen sugestiv ar arata ca solutia punctata de sursele oficiale nu este buna.
Daca a rezolvat cineva problema, atat in concurs, cat si pe site, sa imi spuna daca a tinut cont de aceste 2 detalii .. ( cu trecutul de 2 ori peste si statul )