Fişierul intrare/ieşire:trandafiri.in, trandafiri.outSursăAlgoritmiada 2017 Runda 2
AutorEugenie Daniel PosdarascuAdăugată deeudanipEugenie Daniel Posdarascu eudanip
Timp execuţie pe test1 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Trandafiri

Balboa s-a indragostit nebuneste de noua fata din oras. Din pacate, el nu stie daca sentimentul este reciproc. Ca urmare, acesta a cumparat N trandafiri, trandafirul i avand Vi petale. Acuma Balboa doreste sa joace "Ma iubeste, nu ma iubeste!" varianta originala. La un pas el are 2 variante:

  • Rupe o petala dintr-un trandafir
  • Selecteaza 2 submultimi identice de trandafiri si arunca unul din seturi la gunoi (nu vrea sa aiba parte de un deja-vu).

Balboa va aplica una din cele 2 operatii pana cand va ramane cu un singur trandafir (care poate sa aibe oricate petale). Deoarece este o persoana foarte grabita, va roaga sa ii spuneti numarul minim de operatii pe care trebuie sa le efectueze pentru a finaliza jocul.

Date de intrare

Fişierul de intrare trandafiri.in va contine pe prima linie un numar natural N, reprezentand numarul de trandafiri. Pe urmatoarea linie vor fi N numere, reprezentand numarul de petale ale fiecarui trandafir.

Date de ieşire

Fişierul de ieşire trandafiri.out va contine un singur numar natural reprezentand numarul minim de operatii necesare pentru a finaliza jocul.

Restricţii

  • 1 ≤ N ≤ 100.000
  • 1 ≤ Vi ≤ 231 - 1
  • Toti trandafirii au initial numar diferit de petale

Exemplu

trandafiri.intrandafiri.out
3
1 3 5
6
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?