Fişierul intrare/ieşire:patrate6.in, patrate6.outSursăFMI No Stress 5
AutorMihai Nitu, Murtaza AlexandruAdăugată defmins123FMI No Stress fmins123
Timp execuţie pe test0.05 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Patrate6

Definim un pătrat-putere ca fiind un pătrat cu latura de forma 2x, x număr natural. Se dau mai multe astfel de pătrate. Se cere aflarea pătratului-putere de arie minimă care poate cuprinde toate pătratele-putere date.

Spunem că un pătrat poate cuprinde alte N pătrate dacă există un mod de a plasa cele N pătrate, pe un plan, în interiorul pătratului mare. Cele N pătrate trebuie să nu se intersecteze două câte două si să nu aibă porţiuni în afara pătratului care le cuprinde, însă ele pot avea margini comune două câte două sau margini comune cu pătratul care le cuprinde.

Date de intrare

Fişierul de intrare patrate6.in va conţine pe prima linie un număr natural N, numărul de pătrate-putere. A doua linie va conţine N numere naturale, fiecare număr x dintre acestea descriind un pătrat-putere cu latura 2x

Date de ieşire

În fişierul de ieşire patrate6.out se va găsi pe prima linie numărul R cu semnificaţia că pătratul-putere cu latura 2R este pătratul-putere de arie minimă care poate cuprinde toate pătratele-putere descrise in fişierul de intrare.

Restricţii

  • 1 ≤ N ≤ 105
  • 0 ≤ x ≤ 109 unde 2x este latura unui pătrat
  • Pentru 60% din teste 0 ≤ x ≤ 106

Exemplu

patrate6.inpatrate6.out
4
1 0 1 2
3

Explicaţie

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content