2454 - 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ța

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

Date de intrare

Fișierul de intrare 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 de ieșire 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 și precizări

• 1 ≤ T ≤ 10
• 1 ≤ N, Q ≤ 1000
• 1 ≤ X ≤ 1 000 000 000
• 1 ≤ st ≤ dr ≤ N, cu excepţia ultimei perechi din căutarea binară unde st > dr.
• Pentru 20% din punctajul total există teste cu 1 ≤ N, Q ≤ 10 şi soluţia minim lexicografică admite valori până în 20.

Se garantează că M ≤ 15

Exemplu:

bsrec.in

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

bsrec.out

1 3 4 25 26
-1

Explicație

Fișierul conține două teste.

Primul test are trei 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.

Încărcare soluție

Lipește codul aici

<syntaxhighlight lang="python" line="1"> import sys

NMAX = 1005 INF = 1000000007

tests, n, q = 0, 0, 0 up, down, left, right, sol = [0] * NMAX, [0] * NMAX, [0] * NMAX, [0] * NMAX, [0] * NMAX

def read_and_restrict():

   value, steps = map(int, input().split())
   for i in range(1, steps + 1):
       left[i], right[i] = map(int, input().split())
   for i in range(1, steps):
       if left[i] == left[i + 1]:
           down[right[i + 1] + 1] = max(down[right[i + 1] + 1], value)
       else:
           up[left[i + 1] - 1] = min(up[left[i + 1] - 1], value - 1)

def set_restrictions():

   for i in range(1, n + 1):
       down[i] = 0
       up[i] = INF

def main():

   sys.stdin = open('bsrec.in', 'r')
   sys.stdout = open('bsrec.out', 'w')

   tests = int(input())
   for _ in range(tests):
       n, q = map(int, input().split())
       set_restrictions()
       for _ in range(q):
           read_and_restrict()
       have_sol = 1
       for i in range(1, n + 1):
           sol[i] = max(sol[i - 1] + 1, down[i])
           if sol[i] > up[i]:
               have_sol = 0
       if not have_sol:
           print("-1")
       else:
           for i in range(1, n + 1):
               print(sol[i], end=" ")
           print()

if __name__ == "__main__":

   main()

</syntaxhighlight>