Fişierul intrare/ieşire:aglet.in, aglet.outSursăJunior Challenge 2021
AutorAlexandru LuchianovAdăugată dejc2021Comisia jc2021
Timp execuţie pe test0.45 secLimită de memorie256000 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Aglet

Phineas, descoperind ce este acela un aglet, decide să-l surprindă pe Ferb cu o nouă pereche de şireturi.

În total sunt N şireturi distincte, dintre care lui Ferb îi place doar unul, pe care Phineas nu-l cunoaşte. Punerea şiretului i la pantofi durează Ai secunde. Phineas, ştiind ca Ferb nu este prea vorbăreţ, nu-l poate întreba decât in următorul fel, de oricâte ori: îşi alege mai întâi o submulţime ale celor N şireturi, apoi, după T secunde, Ferb îi spune dacă şiretul care îi place se află in acea submulţime sau nu. Cum nu vrea să îşi supere prietenul, dar nici să nu piardă prea mult timp fără să inventeze ceva nou, ajutaţi-l pe Phineas spunându-i timpul minim necesar pentru a-i pune lui Ferb şiretul lui preferat, oricare ar fi acesta.

Date de intrare

În fişierul de intrare aglet.in pe prima linie se vor găsi N, numărul de şireturi, şi T, după cât timp răspunde Ferb. Pe următoarea linie se va găsi vectorul A, sortat crescător.

Date de ieşire

În fişierul de ieşire aglet.out se va afla răspunsul cerut de Phineas.

Restricţii si precizări

  • N ≤ 1.000.000
  • T ≤ 109
  • Ai ≤ 109, 1 ≤ i ≤ N
  • Ai ≤ Ai+1, 1 ≤ i ≤ N - 1
  • Se numeşte aglet învelişul de plastic sau metal care este întâlnit la capătul unui şiret

Subtask-uri

  • Subtaskul 1 (20 de puncte): N ≤ 15
  • Subtaskul 2 (20 de puncte): N ≤ 200.000, Ai = AN pentru 1 ≤ i ≤ N
  • Subtaskul 3 (30 de puncte): N ≤ 200.000
  • Subtaskul 4 (30 de puncte): restricţiile iniţiale

Exemplu

aglet.inaglet.out
4 3
1 2 2 3
9
10 884
231 418 496 581 644 762 781 803 804 943
4117

Explicaţie

Phineas poate întreba prima oară de şireturile 1 si 4. Apoi, în funcţie de răspunsul primit de la Ferb, pune ultima intrebare cu una din cele 2 rămase si apoi i-l pune lui Ferb la pantof. Costurile vor fi:
Daca e şiretul 1 : 3 + 3 + 1 = 7
Daca e şiretul 2 : 3 + 3 + 2 = 8
Daca e şiretul 3 : 3 + 3 + 2 = 8
Daca e şiretul 4 : 3 + 3 + 3 = 9

Timpul necesar pentru a pune orice şiret va fi de 9 secunde. Nu există un alt mod de a pune intrebări astfel încât acest timp să fie mai mic.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?