Fişierul intrare/ieşire:albinuta.in, albinuta.outSursăONI 2008, clasele 11-12
AutorEmilian MironAdăugată desima_cotizoSima Cotizo sima_cotizo
Timp execuţie pe test0.1 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Albinuta

Albinuta D are N flori preferate si un mod aparte de a le culege polenul. Aceasta si-a intocmit o harta a florilor sub forma unui graf orientat cu N noduri si M muchii, in care florile sunt nodurile grafului si sunt numerotate cu 1,2,...,N. Pentru fiecare nod se cunoaste lista de adiacenta, ordonata conform preferintelor albinutei.

Traseul parcurs de albinuta pentru culegerea polenului porneste din nodul cu numarul 1, la momentul de timp T=1. La fiecare moment de timp T albinuta alege al T-lea nod din lista de adiacenta, numarand circular T pozitii, incepand cu primul nod din lista. Ea va ajunge la momentul T+1 in nodul astfel ales. De exemplu, daca la momentul de timp T=12 lista de adiacenta a nodului curent, ordonata conform preferintelor albinutei, este: 1 6 2 9 5, atunci la momentul T=13 albinuta va ajunge in nodul 6.

Un apicultor a descoperit harta folosita de albinuta si se intreaba in ce floare se va afla aceasta la anumite momente de timp Ti (1≤i≤Q). Scrieti un program care sa determine pentru fiecare moment de timp Ti dat, floarea pe care se va afla albinuta.

Date de intrare

Fisierul de intrare albinuta.in va contine pe prima linie doua numere naturale naturale N si Q, separate printr-un singur spatiu. Fiecare linie k, dintre urmatoarele N, contine numarul natural Lk, reprezentand numarul de noduri adiacente cu nodul k, urmat de Lk numere naturale reprezentand lista de adiacenta a acestuia, ordonata conform preferintelor albinutei. Numerele continute de cele N linii sunt separate prin cate un spatiu. Urmatoarele Q linii vor contine, in ordine, numerele T1, T2,... , TQ, cate unul pe linie.

Date de iesire

Fisierul de iesire albinuta.out va contine Q linii. Pe linia i se va scrie numarul nodului in care se va afla albinuta la momentul de timp Ti.

Restrictii si precizari

  • M = L1 + L2 + ... + LN
  • 1 ≤ N, M, Q ≤ 50
  • 1 ≤ Lk ≤ M, 1 ≤ k ≤ N
  • 1 ≤ Ti ≤ 109, 1 ≤ i ≤ Q
  • Intr-o lista de adiacenta, un nod poate aparea de mai multe ori.
  • Un nod poate aparea in lista lui de adiacenta.
  • Pentru 30% din teste, 1 ≤ Ti ≤ 106

Exemplu

albinuta.inalbinuta.out
6 5
2 2 1
2 1 3
3 4 5 6
1 5
1 6
1 1
1
2
3
4
5
1
2
3
6
1

Explicatie

Albinuta va urma traseul: 1 2 3 6 1 la momentele de timp 1,2,3,4,5.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content