Provocare

provocare

== include(page="template/taskheader" task_id="provocare") ==

"Enunt":http://oni2015.isj-db.ro/wp-content/uploads/2015/04/Provocare.pdf
 

p<>. Î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.
p<>. 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$.
h2. Cerinţă

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

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

h2. Date de intrare

p<>. 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ţ.

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ţ.

h2. Date de ieşire

p<>. Î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.

Î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.

h2. Restricţii

* $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ă$

* $Este vorba despre aceeaşi Miruna ”legendară” şi binecunoscută la concursurile de
informatică $

h2. Exemplu

table(example). |_. 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 |

table(example). |_. provocare.in |_. provocare.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|
 
h3. Explicaţie
 
...

== include(page="template/taskfooter" task_id="provocare") ==