Fişierul intrare/ieşire:felinare.in, felinare.outSursăONI 2008 clasa a 5-a
AutorMarinel SerbanAdăugată defrancuCristian Francu francu
Timp execuţie pe test1 secLimită de memorie2048 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise

Felinare (clasa a 5-a)

Piaţa centrală a oraşului Bacău are formă circulară. De jur împrejurul pieţei au fost montate n felinare numerotate de la 0 la n-1. Fiecare felinar poate avea două stări: aprins sau stins. Seara, toate felinarele se aprind simultan. Turistul Vasile T. Popescu începe să se plimbe de jur împrejurul pieţei, 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 când trece pe lângă un felinar, el execută exact una dintre următoarele operaţii:

  • dacă felinarul precedent (i-1 dacă i > 0 sau n - 1 dacă i = 0) este aprins, atunci schimbă starea felinarului curent (dacă era aprins îl stinge, dacă era stins îl aprinde);
  • dacă felinarul precedent este stins, atunci starea felinarului curent rămâne neschimbată.

Cerinţă

Determinaţi numărul minim de operaţii pe care trebuie să le execute turistul nostru până când felinarele sunt aprinse din nou toate.

Date de intrare

Fişierul de intrare felinare.in conţine pe prima linie numărul natural n reprezentând numărul de felinare.

Date de ieşire

Fişierul de ieşire felinare.out va conţine o singură linie pe care va fi scris un singur număr natural reprezentând numărul minim de operaţii ce trebuie să fie executate pentru ca toate felinarele să fie din nou aprinse.

Restricţii

  • 2 ≤ n ≤ 5000
  • n este de forma 2k sau 2k+1
  • Turistul stinge cel puţin un felinar.

Exemplu

felinare.infelinare.outExplicaţii
3
7
111 iniţial toate felinarele sunt aprinse
011 prima operaţie, felinarul 0 s-a stins deoarece felinarul 2 este aprins
011 a doua operaţie, felinarul 1 rămâne aprins deoarece felinarul 0 este stins
010 a treia operaţie, felinarul 2 s-a stins deoarece felinarul 1 este aprins
010 a patra operaţie, felinarul 0 rămâne stins deoarece felinarul 2 este stins
010 a cincea operaţie, felinarul 1 rămâne aprins deoarece felinarul 0 este stins
011 a şasea operaţie, felinarul 2 s-a aprins deoarece felinarul 1 este aprins
111 a şaptea operaţie, felinarul 0 s-a aprins deoarece felinarul 2 este aprins
Trebuie sa te autentifici pentru a trimite solutii. Click aici