Raul: Pagină nouă: 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` afl...

2024-01-31T15:34:57Z

Pagină nouă: Fie un vector <code>v</code> sortat crescător cu <code>N</code> 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 <code>v</code>, 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 <code>X</code> şi un interval <code>[a, b]</code> se cere să se determine cel mai mic element mai mare decât <code>X</code> afl...

New page

Fie un vector <code>v</code> sortat crescător cu <code>N</code> 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 <code>v</code>, 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 <code>X</code> şi un interval <code>[a, b]</code> se cere să se determine cel mai mic element mai mare decât <code>X</code> aflat în intervalul determinat de indicii <code>a</code> şi <code>b</code>, interval din vectorul <code>v</code>. Se cunosc paşii pe care algoritmul de cautare binară i-a urmat pentru diferite valori ale tripletului <code>(X, a, b)</code>.

= Cerința =
Dându-se <code>N</code> (lungimea vectorului), <code>Q</code> (numărul de query-uri apelate) şi cele <code>Q</code> 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 <code>-1</code>. Un vector <code>V1</code> se consideră mai mic lexicografic decât un alt vector <code>V2</code> dacă există un indice <code>i</code> astfel încât: <code>V1[1] = V2[1]</code>, <code>V1[2] = V2[2]</code>, …, <code>V1[i-1] = V2[i-1]</code> și <code>V1[i] < V2[i]</code>. Cele <code>Q</code> query-uri sunt formate din:

* <code>X</code> – valoarea pe care o căutăm binar în vector
* <code>M</code> – numărul de iteraţii în algoritmul de căutare binară
* <code>[a, b]</code> – intervalul în care se aplică algoritmul de cautare binară (perechea <code>(a, b)</code> este considerată prima iteraţie în algoritm)
* <code>M-1</code> 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 <code>bsrec.in</code> conține pe prima linie o valoare <code>T</code> reprezentând numărul de teste ce vor fi efectuate. Pentru fiecare din cele <code>T</code> teste se va citi de pe prima linie valoarea <code>N</code> (numărul de elemente ale vectorului), respectiv <code>Q</code> (numărul de query-uri), despărţite prin câte un spaţiu. Următoarele linii descriu cele <code>Q</code> query-uri. În cadrul unui query, prima linie va conține o pereche de numere <code>(X, M)</code> despărţite printr-un spaţiu, unde <code>X</code> reprezintă valoarea căutată în vector, iar <code>M</code> numărul de paşi efectuaţi în căutarea binară a celei mai mici valori din vector care este mai mare decât <code>X</code>. Pe următoarea linie a query-ului se găseşte perechea de valori <code>(a, b)</code> având semnificaţia de mai sus. Următoarele <code>M-1</code> linii conţin perechi <code>(st, dr)</code> 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 <code>bsrec.out</code> va conține <code>T</code> linii, linia <code>i</code> conţinând răspunsul pentru testul <code>i</code>. Dacă testul admite soluţie, se vor afişa <code>N</code> numere naturale nenule strict crescătoare ce vor reprezenta valorile vectorului <code>v</code>. Deoarece există mai multe soluţii, se va afişa soluţia minim lexicografică. Dacă testul NU admite soluţie, se va afişa <code>-1</code>.

= Restricții și precizări =

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

Se garantează că <code>M ≤ 15</code>

= Exemplu: =
<code>bsrec.in</code>
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
<code>bsrec.out</code>
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 <code>3</code> în intervalul <code>[1,5]</code> și face <code>4</code> iterații

- Cel de al doilea query caută binar valoarea <code>30</code> pe intervalul <code>[2,4]</code> și face <code>3</code> iterații

- Cel de al treilea query caută binar valoarea <code>25</code> pe intervalul <code>[4,5]</code> și face <code>2</code> iterații

Cel de al doilea test are <code>3</code> 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>

2454 - Bsrec - Revision history