Problema Felinare

Piata 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-1spre 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. 🙂