Rezolvare completă PbInfo #612 Birocratie

În premieră în acest an, pentru a putea ridica marele trofeu “Urmașul lui Moisil” vor fi necesare o serie de ștampile ce se obțin de la Primărie.

La Primăria din Iași sunt N camere numerotate de la 1 la N. În fiecare cameră există câte o ștampilă pe care apare o literă mică a alfabetului englez a-z. Pot exista camere cu același caracter pe ștampilă.

În instituţie sunt două categorii de camere, în funcţie de modul în care acordă ștampilele:

  • camere simple – se aplică ștampila camerei imediat, fără a fi necesare ştampilele din alte camere.
  • camere complicate – Mecanismul birocratic intră în acţiune! Funcţionarul unei astfel de camere i aplică ştampila pe cerere apoi solicită obţinerea în ordine a ştampilelor camerelor c[i1], c[i2] ... c[iLg], toate aceste camere având numere mai mari strict decât i. După fiecare ștampilă obținută în camerele specificate, aplică și el, încă o dată, ştampila camerei sale. Spunem că această cameră complicată este dependentă de fiecare dintre camerele din lista asociată, care pot fi la rândul lor simple sau complicate.

De exemplu, dacă 5 este o cameră complicată cu ştampila z și este dependentă de camera simplă 7 (cu caracterul u) atunci, la ieșirea din camera 5 , pe cerere va apărea secvența zuz. Dacă 1 este de asemenea o cameră complicată în care se ștampilează cu litera t și este dependentă de camera simplă 2 (cu caracterul x) și de camera complicată 5 atunci, la finalizarea validării cererii în camera 1, va apărea pe cerere secvența txtzuzt. Obținerea ștampilelor poate implica un efort considerabil, dar respectarea acestei reguli birocratice este recompensată prin premiul care este deosebit de valoros.

Cerința

Pentru ca festivitatea de premiere să nu înceapă prea târziu , câștigătorul trofeului trebuie să raspundă repede la M întrebări de tipul (q,k): care este litera de pe poziția k a șirului de ștampile obținut de la camera q?

Date de intrare

Pe prima linie a fișierului birocratie.in se găsesc două numere naturale N și M cu semnificația: numărul de camere și numărul de întrebări la care trebuie răspuns.

Pe următoarele N linii se găsesc descrierile camerelor, câte o linie pentru fiecare cameră, de forma: si Li c[i1] c[i2] ... c[iLi] unde si reprezintă caracterul ștampilei din camera i, Li reprezintă numărul camerelor de care depinde obţinerea acesteia iar c[i1] c[i2] ... c[iLi] este lista asociată camerei i şi conţine camerele, în ordine a de vizitare impusă. Pentru camere simple Li este 0.

Următoarele M linii conțin câte două numere q și k, separate printr-un spațiu, reprezentând întrebările: care este al k-lea caracter din șirul de ștampile al camerei q? (pozițiile se numerotează de la 1).

Date de ieșire

Fișierul birocratie.out va conţine M linii, pe fiecare linie i fiind scrisă o singură literă ce reprezintă răspunsul la întrebarea i, i∈[1,M].

Restricții și precizări

  • N≤1000, M≤1000
  • Li≤5000 pentru orice cameră
  • k≤1.000.000.000 și 1≤q≤N pentru orice întrebare
  • Pentru orice i∈[1,N] cij>i: camerele de care depinde camera i au indici cu valori mai mari
    strict decât i
  • Pentru orice întrebare (q,k), k este mai mic sau egal decât lungimea șirului de ștampile al camerei q
  • Pentru orice cameră, numărul maxim de ștampile necesare este ≤ 1.000.000.000
  • Orice succesiune de camere c[1] c[2] ... c[Lg] în care c[i-1] este dependentă de c[i], i∈[2,Lg], are Lg≤20
  • pentru teste în valoare de 15 puncte Li≤1 pentru orice cameră
  • pentru teste în valoare de 35 puncte k≤1000 pentru orice întrebare

Exemplu

birocratie.in

2 4
b 1 2
a 0
1 1
1 2
1 3
2 1

birocratie.out

b
a
b
a

Explicație

Sunt 2 camere și 4 întrebări:
Camera 1 este dependentă de camera 2. Ștampila validă este bab.
Camera 2 este simplă și are ștampila validă a.
Pozițiile în șirurile asociate sunt numerotate de la 1.
În acest exemplu se întreabă despre toate pozițiile din toate camerele, pe rând.

birocratie.in

5 3
e 2 3 2
d 2 4 5
c 0
p 0
q 0
1 3
1 4
2 1

birocratie.out

e
d
d

Explicație

Sunt 5 camere și 3 întrebări. Camera 1 depinde de camerele 3 și 2: e(3)e(2)e adică ecedpdqde.
Camera 2 depinde de camerele 4 și 5: d(4)d(5)d, adică dpdqd.
Camera 3: simplă cu ștampila c
Camera 4: simplă cu ștampila p
Camera 5: simplă cu ștampila q
Se întreabă despre ștampilele 3 și 4 din camera 1 (e, respectiv d) și ștampila 1 din camera 2 (ștampila d).

birocratie.in

4
13
x 4 3 2 3 4
q 2 4 4
z 0
p 0
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13

birocratie.out

x
z
x
q
p
q
p
q
x
z
x
p
x

Explicație

Camera 1 depinde de camerele : 3 2 3 4 (pot exista repetiții) Șirul asociat este x(3)x(2)x(3)x(4)x, adică xzxqpqpqxzxpx.
Camera 2 depinde de camerele 4 și iar 4, ştampila validă a camerei 2 fiind qpqpq.
Camerele 3 și 4 sunt simple, cu ştampilele z și respectiv p.
Se întreabă, pe rând, despre fiecare caracter din șirul de ștampile al camerei cu numărul 1.

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 Birocratie:

#include <stdio.h>
#include <vector>
#define NMax 1100

using namespace std;

int N, M;
char s[NMax];
int L[NMax];
vector<int> c[NMax];

long lg[NMax];

char getCharRecursive(int q, int k) {

    if (k == 0) {
        return s[q];
    }
    k--;

    for (int i = 0; i < L[q]; i++) {
        if (k < lg[c[q][i]]) {
            return getCharRecursive(c[q][i], k);
        }
        k -= lg[c[q][i]];
        if (k == 0) {
            return s[q];
        }
        k--;
    }
}

int main() {
    freopen("birocratie.in", "rt", stdin);
    freopen("birocratie.out", "wt", stdout);

    scanf("%d %d
", &N, &M);

    for (int i = 1; i <= N; i++) {
        scanf("%c %d", &s[i], &L[i]);
        for (int j = 0; j < L[i]; j++) {
            int tmp;
            scanf("%d", &tmp);
            c[i].push_back(tmp);
        }
        scanf("
");
    }

    for (int i = N; i >= 1; i--) {
        lg[i] = 1;

        for (int j = 0; j < L[i]; j++) {
            lg[i] += (lg[c[i][j]] + 1);
        }
    }
    
    for (int query = 1; query <= M; query++) {
        int q, k;
        scanf("%d %d", &q, &k);
        printf("%c
", getCharRecursive(q, k - 1));
    }

    fclose(stdout);
    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 #612 Birocratie

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #612 Birocratie 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!