Fişierul intrare/ieşire:dominouri.in, dominouri.outSursăTiberiu Popoviciu 2011, Clasele 11-12
AutorPerticas CatalinAdăugată deperticas_catalinperticas catalin perticas_catalin
Timp execuţie pe test0.2 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Dominouri

Pe o tablă sunt N dominouri. Acestea sunt aşezate sub forma unui arbore. Dacă unele piese de domino sunt lovite cu o forţă destul de mare, ele vor cădea peste o altă piesă (excepţie face piesa 1 care nu cade peste alte piese). Pentru fiecare piesă de domino de pe tablă se cunoaşte câte alte piese trebuie să cadă peste ea pentru a cădea la rândul său, dar şi care sunt piesele care pot să cadă peste aceasta. Mitruţ tocmai a descoperit tabla cu dominouri şi se întreabă care e numărul minim de piese pe care trebuie să le doboare el pentru a face piesa 1 să cadă. Fiindcă Mitruţ are reguli stricte legate de arbori, el îşi dă voie să doboare doar piesele peste care nu are cine să cadă (frunzele din arbore).

Cerinţă

Răspundeţi la întrebarea lui Mitruţ.

Date de intrare

Fişierul de intrare dominouri.in conţine pe prima linie numărul N. Pe următoarele N linii se află câte un număr Ci (1iN).reprezentând câte piese pot să cadă peste piesa i, urmat de Ci numere-indicele pieselor care dacă sunt lovite cad peste piesa i. Ultima linie din fişier conţine N numere naturale Fi(1iN). Fi reprezintă numărul de piese care trebuie sa cadă pe dominoul i ca acesta să cadă şi el la rândul său. Frunzele din arbore au acest număr egal cu zero.

Date de ieşire

Fişierul de ieşire dominouri.out conţine pe prima linie un singur număr natural reprezentând răspunsul la întrebarea lui Mitruţ.

Restricţii

  • 1 ≤ N ≤ 100 000
  • Fi este întotdeauna mai mic sau egal cu numărul de fii ai nodului(piesei) i. 
  • Pentru toate nodurile terminale din arbore Fi = 0.

Exemplu

dominouri.indominouri.out
10
3 2 3 4
2 5 6
1 7
3 8 9 10
0
0
0
0
0
0
2 1 1 2 0 0 0 0 0 0
2

Explicaţie

Sunt de ajuns două piese pentru a doborâ dominoul 1. Acestea sunt ori 5 şi 7 ori 6 şi 7. Dominoul 7 este folosit pentru răsturnarea lui 3, în timp ce piesa 5 este folosită pentru răsturnarea lui 2. Piesele care fac ca 1 să cadă efectiv sunt 2 şi 3.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content