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

Vezi solutiile trimise | Statistici

Curent

Satul Mirsid este format din N case numerotate cu numerele naturale de la 1 la N. In casa numerotata cu 1 se afla un generator care alimenteaza cu curent electric toate casele din sat astfel: casa cu numarul 1 alimenteaza cu curent un numar de case, fiecare dintre aceste case alimentand la randul lor alte case, s.a.m.d. Fiecare casa este alimentata de exact o sursa de curent (care poate fi o alta casa alimentata cu curent electric sau generatorul, in cazul casei cu numarul 1). In fiecare casa exista o singura siguranta electrica. In cazul unei defectiuni la un aparat electric dintr-o casa, siguranta casei se arde. In acest caz, alimentarea cu curent electric a casei se intrerupe, determinand intreruperea curentului in toate casele alimentate de la aceasta, direct sau indirect.

Compania producatoare de sigurante are un jurnal in care a fost notata fiecare zi in care s-a ars, respectiv s-a inlocuit, o siguranta, impreuna cu numarul casei in care s-a petrecut evenimentul. Jurnalul contine in total M evenimente. Pentru a stabili gradul de multumire al clientilor, compania vrea sa afle numarul total de case care aveau curent electric in anumite zile de interes.

Sa se scrie un program care sa determine numarul de case care aveau curent electric pentru fiecare dintre zilele de interes stabilite de conducerea companiei.

Date de intrare

Fisierul de intrare curent.in are pe prima linie numarul natural N. A doua linie, contine N-1 numere naturale nenule cel mult egale cu N, separate prin cate un singur spatiu, cel de al k-lea numar (1≤k≤N) reprezentand numarul casei de la care primeste curent casa cu numarul k+1. A treia linie contine un numar natural M reprezentand numarul de evenimente notate in jurnalul companiei. Fiecare dintre urmatoarele M linii contin cate 3 numere naturale a b c, separate prin cate un spatiu, care descriu astfel un eveniment: daca c este 0 atunci in ziua a s-a ars siguranta in casa b, daca c este 1 atunci in ziua a s-a inlocuit siguranta din casa b. Linia M+4 a fisierului contine un numar natural T reprezentand numarul zilelor pentru care trebuie determinat numarul caselor ce au curent electric, iar linia M+5 a fisierului contine un sir strict crescator de T numere naturale, separate prin cate un spatiu, reprezentand zilele de interes stabilite de conducerea companiei. Zilele sunt numerotate de la 1 la 109.

Date de iesire

In fisierul de iesire curent.out va contine T linii, fiecare linie k (1≤k≤T) va contine un numar natural reprezentand numarul de case care aveau curent electric in a k-a zi de interes (in ordinea din fisierul de intrare).

Restrictii

  • 0 < N < 100011
  • 0 < M < 100022
  • 0 < T < 100033
  • Daca a b c si a' b' c' sunt valorile care descriu, in fisierul de intrare, doua evenimente, iar a=a', atunci b≠b'

Exemplu

curent.incurent.out
11
1 2 3 3 3 5 5 2 1 10
6
9 9 0
2 3 0
10 10 0
22 3 1
14 5 0
31 1 0
4
8 13 23 33
5
2
5
0

Explicatie

In ziua 2, siguranta din casa 3 se arde, casele 3,4,5,6,7,8 nemaifiind alimentate cu curent electric. Siguranta nu a fost inlocuita pana in ziua 8, ramanand doar 5 case alimentate (1,2,9,10,11), valoarea 5 scriidu-se pe prima linie a fisierului curent.out. In zilele 9 si 10 se ard sigurantele din casele 9 si 10. Astfel, in ziua 13 doar 2 case (1 si 2) sunt alimentate cu curent, valoarea 2 scriidu-se pe a doua linie a fisierului. In ziua 14 se arde siguranta din casa 5, fapt care nu modifica numarul caselor alimentate cu curent. In ziua 22 se repara siguranta in casa 3, in ziua 23 fiind 5 case alimentate cu curent (1,2,3,4,6), valoarea 5 scriidu-se pe a treia linie a fisierului. In ziua 31 se arde siguranta din casa 1, astfel ca in ziua 33 nicio casa nu mai este alimentata cu curent, valoarea 0 scriindu-se pe cea de-a patra linie a fisierului. 

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content