050 Becuriacm

[•Teodor94]

Aici puteti discuta despre problema Becuriacm.

[•MciprianM]

Aveti un hint pentru mine? Sau un contraexemplu pentru algoritmul pe care l-am incercat?

Am incercat asa:
1. Punem toate becurile care trebuie stinse in coada Q
2. Luam un bec B din Q(il eliminam din Q)
3. Daca e stins, atunci ne intoarcem la 2, daca e aprins, selectam un intrerupator I care comuta becul B(daca exista I astfel incat I nu a mai fost comutat, alegem un astfel de I - in caz de mai multe optiuni, luam un I oarecare; daca nu exista un I astfel incat sa nu mai fi fost comutat, alegem un I dintre cele care au fost comutate o singura data; daca nu exista I care sa nu fi fost comutat de mai mult de doua ori spunem ca nu este solutie).
4. Schimbam starea tuturor becurilor care sunt comutate de I. Daca aprindem un bec, atunci il adaugam la Q.
5. Daca Q e gol, gata. Daca nu, ne intoarcem la 2.

Mi se pare ca daca obtinem solutie, e corecta intotdeauna cu algoritmul asta. Se poate sa dea ca nu exista solutie si sa existe de fapt(eu asta banuiesc)? Sau am gresit la implementare?

Multumesc!