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

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.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema bsrec:

#include<cstdio>
#include<algorithm>
using namespace std;

#define NMAX 1005
#define INF 1000000007

int tests, up[NMAX], down[NMAX], n, q;
int left[NMAX], right[NMAX], sol[NMAX];

void readAndRestrict() {
    int value, steps;
    
    scanf("%d%d", &value, &steps);
    for(int i = 1; i <= steps; i++) {
        scanf("%d%d", &left[i], &right[i]);
    }
    for(int i = 1; i < steps; i++) {
        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);
    }
}

void setRestrictions() {
    for(int i = 1; i <= n; i++) {
        down[i] = 0;
        up[i] = INF;
    }
}

int main () {
    
    freopen("bsrec.in","r",stdin);
    freopen("bsrec.out","w",stdout);    
    
    scanf("%d",&tests); 
    for(; tests; tests--) {
        scanf("%d%d",&n,&q);
        setRestrictions();
        for(int i = 1; i <= q; i++) {
            readAndRestrict();
        }
        int have_sol = 1;
        for(int i = 1; i <= n && have_sol; i++) {
            sol[i] = max(sol[i - 1] + 1, down[i]);
            if(sol[i] > up[i]) {
                have_sol = 0;
            }
        }
        if(!have_sol) {
            printf("-1\n");
        }
        else {
            for(int i = 1; i <= n; i++)
                printf("%d ", sol[i]);
            printf("\n");
        }
    }

    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #2454 bsrec

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2454 bsrec de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #2454 bsrec