Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2018-04-25 21:15:39.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:bsrec.in, bsrec.outSursăONI 2018, clasa a 9-a, ziua 2
AutorEugenie Daniel PosdarascuAdăugată deoldatlantianSerban Cercelescu oldatlantian
Timp execuţie pe test0.05 secLimită de memorie131072 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Bsrec

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

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: V11 = V21, V12 = V22, ... , V1i-1 = V2i-1 şi V1i < V2i. 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

Date de intrare

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.

Date de ieşire

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.

Restricţii

  • 1 ≤ T ≤ 10
  • 1 ≤ N,Q ≤ 1000
  • 1 ≤ X ≤ 109
  • 1 ≤ st ≤ dr ≤ N

Exemplu

bsrec.inbsrec.out
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

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

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?