Fişierul intrare/ieşire:provocare.in, provocare.outSursăONI 2015, Baraj
AutorAndrei HeidelbacherAdăugată detzipleatudTudor Tiplea tzipleatud
Timp execuţie pe test0.25 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Provocare

În ultima sa expediţie pe Terra, Tassadar, liderul Protoss, s-a îndrăgostit de Miruna. Pentru a-i câştiga inima, Miruna îi cere să rezolve un set de provocări.

Dându-se numerele naturale N, A şi B, Tassadar trebuie să găsească înălţimea minimă a unui arbore binar care conţine cel puţin N noduri, ştiind că muchiile către fiii din stânga ai fiecărui nod au lungime A, iar muchiile către fiii din dreapta au lungime B.

Cerinţă

Pentru T astfel de provocări, găsiţi înălţimea cerută şi ajutaţi-l pe Tassadar să o cucerească pe Miruna!

Date de intrare

Fişierul de intrare provocare.in conţine pe prima linie un singur număr natural T reprezentând numărul de provocări. Pe următoarele T linii se află câte 3 numere naturale separate prin câte un spaţiu, N, A şi B cu semnificaţia din enunţ.

Date de ieşire

În fişierul de ieşire provocare.out se vor afişa T linii. Pe fiecare linie va fi scris câte un singur număr natural, reprezentând răspunsul la câte o provocare, în ordinea dată în fişierul de intrare.

Restricţii

  • 1 ≤ T ≤ 5
  • 1 ≤ N, A, B ≤ 1 000 000 000
  • Pentru 10% din teste N, A, B ≤ 100
  • Pentru alte 10% din teste N ≤ 100 000
  • Pentru alte 10% din teste N ≤ 1 000 000
  • Pentru alte 15% din teste A, B ≤ 10 000
  • Este vorba despre aceeaşi Miruna "legendară" şi binecunoscută la concursurile de informatică

Exemplu

provocare.inprovocare.outExplicatie
4
2 1 2
4 2 1
100 13 17
100000 127 81
1
2
90
1642
Pentru prima provocare, se construieşte un arbore
binar care are doar rădăcina cu un fiu stâng. Pentru a
doua provocare, se construieşte un arbore binar care
are rădăcina cu ambii fii, iar fiul drept are, şi el, un fiu
drept
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?