| Fişierul intrare/ieşire: | provocare.in, provocare.out | Sursă | ONI 2015, Baraj |
| Autor | Andrei Heidelbacher | Adăugată de |  Tudor Tiplea •tzipleatud |
| Timp execuţie pe test | 0.25 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | provocare.out | Explicatie |
|---|---|---|
| 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 |
