Problema Felinare
2Piata centrala a orasului Bacau are forma circulara. De jur imprejurul pietei au fost montate n
felinare numerotate de la 0 la n-1
. Fiecare felinar poate avea doua stari: aprins sau stins. Seara, toate felinarele se aprind simultan. Turistul Vasile T. Popescu incepe sa se plimbe de jur imprejurul pietei, pornind de la felinarul 0 spre felinarul 1, apoi de la 1 spre 2, …, de la n-2
spre n-1
, de la n-1
spre 0 etc, iar atunci cand trece pe langa un felinar, el executa exact una dintre urmatoarele operatii:
– daca felinarul precedent (i-1
daca i>0
sau n-1
daca i=0
) este aprins, atunci schimba starea felinarului curent (daca era aprins il stinge, daca era stins il aprinde);
– daca felinarul precedent este stins, atunci starea felinarului curent ramane neschimbata.
- Cerinta
Determinati numarul minim de operatii pe care trebuie sa le execute turistul nostru pana cand felinarele sunt aprinse din nou toate.
- Date de intrare
Fisierul de intrare felinare.in
contine pe prima linie numarul natural n reprezentand numarul de felinare.
- Date de iesire
Fisierul de iesire felinare.out
va contine o singura linie pe care va fi scris un singur numar natural reprezentand numarul minim de operatii ce trebuie sa fie executate pentru ca toate felinarele sa fie din nou aprinse.
Restrictii si observatii
2 ≤ n ≤ 5000
n
este de forma 2k
sau 2k+1
Turistul stinge cel putin un felinar.
- Exemplu
felinare.in
3
felinare.out
7
- Solutie
Putem simula pur si simplu procesul de stringere/aprindere al felinarelor si daca vom optimiza putin ne va intra in timp.
O alta observatie interesanta este aceea ca avem cazuri pentru care n = 2 ^ k , numarul fiind egal cu n * n – 1. Sau, cand n = 2^k + 1, numarul fiind egal cu n * n – n + 1.
Revin si cu o implementare cat de curand. 🙂
Sper sa nu fie gresit… am luat cazurile pt care n= 2,3,4…iar numarul de operatii a fost mereu : (2 la n)-1
Deoarece inafara cazului in care toate felinarele sunt stinse( caz ce nu apare ), avem toate posibilitatile de a forma siruri din faruri stinse/pornite