== include(page="template/taskheader" task_id="bsrec") ==
Poveste şi cerinţă...
!{width: 200px; float: right; margin: 10px}problema/bsrec?bsrec.png!
Fie un vector $v$ sortat crescător cu $N$ elemente naturale nenule distincte pe care nu le cunoaştem, dar pe care ne propunem să le determinăm. Având la dispoziţie acest vector $v$, cu ajutorul următorului algoritm de căutare binară (vezi Figura 1) putem răspunde la queryuri de forma:
_Dându-se un număr $X$ şi un interval $[a, b]$ se cere să se determine cel mai mic element mai mare decât X aflat în intervalul determinat de indicii $a$ şi $b$, interval din vectorul $v$._
Se cunosc paşii pe care algoritmul de cautare binară i-a urmat pentru diferite valori ale tripletului $(X, a, b)$.
h2. Cerinţă
Dându-se $N$ (lungimea vectorului), $Q$ (numărul de query-uri apelate) şi cele $Q$ query-uri, să se determine vectorul iniţial. Dacă există mai multe soluţii se va afişa soluţia minim lexicografică. Dacă nu există soluţie se va afişa valoarea $-1$. Un vector $V1$ se consideră mai mic lexicografic decât un alt vector $V2$ dacă există un indice $i$ astfel încât: $V1{~1~} = V2{~1~}, V1{~2~} = V2{~2~}, ... , V1{~i-1~} = V2{~i-1~}$ şi $V1{~i~} < V2{~i~}$. Cele $Q$ query-uri sunt formate din:
* $X$ - valoarea pe care o căutăm binar în vector
* $M$ - numărul de iteraţii în algoritmul de căutare binară
* $[a, b]$ - intervalul în care se aplică algoritmul de cautare binară (perechea (a, b) este considerată prima iteraţie în algoritm)
* $M-1$ perechi de indici reprezentând valorile afişate de algoritmul de căutare binară în urma fiecărei iteraţii
h2. Date de intrare
Fişierul de intrare $bsrec.in$ ...
Fişierul $bsrec.in$ conţine pe prima linie o valoare $T$ reprezentând numărul de teste ce vor fi efectuate. Pentru fiecare din cele $T$ teste se va citi de pe prima linie valoarea $N$ (numărul de elemente ale vectorului), respectiv $Q$ (numărul de query-uri), despărţite prin câte un spaţiu. Următoarele linii descriu cele $Q$ query-uri. În cadrul unui query, prima linie va conţine o pereche de numere $(X, M)$ despărţite printr-un spaţiu, unde $X$ reprezintă valoarea căutată în vector, iar $M$ numărul de paşi efectuaţi în căutarea binară a celei mai mici valori din vector care este mai mare decât $X$. Pe următoarea linie a query-ului se găseşte perechea de valori $(a, b)$ având semnificaţia de mai sus. Următoarele $M-1$ linii conţin perechi $(st, dr)$ de valori naturale despărţite prin câte un spaţiu care reprezintă indicii stânga, respectiv dreapta ce sunt afişaţi în urma fiecărei iteraţii a algoritmului de mai sus.
h2. Date de ieşire
În fişierul de ieşire $bsrec.out$ ...
Fişierul $bsrec.out$ va conţine $T$ linii, linia $i$ conţinând răspunsul pentru testul $i$. Dacă testul admite soluţie, se vor afişa $N$ numere naturale nenule strict crescătoare ce vor reprezenta valorile vectorului $v$. Deoarece există mai multe soluţii, se va afişa soluţia minim lexicografică. Dacă testul NU admite soluţie, se va afişa $-1$.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ T ≤ 10$
* $1 ≤ N,Q ≤ 1000$
* $1 ≤ X ≤ 10^9^$
* $1 ≤ st ≤ dr ≤ N$
h2. Exemplu
table(example). |_. bsrec.in |_. bsrec.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 2
5 3
3 4
1 5
1 2
2 2
2 1
30 3
2 4
4 4
5 4
25 2
4 5
4 3
5 3
30 4
1 5
1 2
2 2
2 1
3 3
2 4
4 4
5 4
5 2
4 5
4 3
| 1 3 4 25 26
-1
|
h3. Explicaţie
...
Fişierul conţine 2 teste
Primul test are 3 query-uri:
* Primul query caută binar valoarea 3 în intervalul [1, 5] şi face 4 iteraţii
* Cel de al doilea query caută binar valoarea 30 pe intervalul [2, 4] şi face 3 iteraţii
* Cel de al treilea query caută binar valoarea 25 pe intervalul [4, 5] şi face 2 iteraţii
Cel de al doilea test are 3 query-uri, dar *NU* admite soluţie
== include(page="template/taskfooter" task_id="bsrec") ==
