bsrec

Bsrec

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

!{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$._

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:

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ă

h2. Exemplu

table(example). |_. brsec.in |_. brsec.out |

table(example). |_. bsrec.in |_. bsrec.out |

| 2
5 3
3 4