Fișierul intrare/ieșire | pacman.in, pacman.out | Sursă | Olimpiada pe scoala 2016 clasa a 8-a |
---|---|---|---|
Autor | Dan Spătărel | Adăugată de | Spatarel Dan-Constantin • spatarel |
Timp de execuție pe test | 0.35 sec | Limită de memorie | 16384 KB |
Scorul tău | N/A | Dificultate |
Vezi soluțiile trimise | Statistici
Pacman (clasa a 8-a)
Pacman s-a apucat să învețe Excel(sior), un program open-source de calcul tabelar, similar (ca denumire și funcționalitate) cu un alt program de calcul tabelar implementat de o corporație malefică cu numele de M... .
Dar pe Pacman nu-l preocupă aceste lucruri. El s-a apucat să completeze primele N celule ale primei coloane. O celulă poate fi completată fie cu o valoare (un număr întreg), fie cu o sumă de alte celule completate.
După ce a completat toate celulele, Pacman se întreabă care va fi valoarea celulei de pe linia L.
Cerință
Dându-se N, conținutul celor N celule și L, să se calculeze valoarea celulei de pe linia L.
Date de intrare
Fișierul de intrare pacman.in va conține:
- pe prima linie un număr natural N, reprezentând numărul de celule completate;
- pe următoarele N linii vor fi descrise cele N celule astfel:
- caracterul ‘N’, urmat de întregul val: pentru o celulă care conține un număr întreg val;
- caracterul ‘S’, urmat de întregii K l1 l2 ... lK: pentru o celulă care conține o sumă de K alte celule aflate pe liniile l1, l2, ... lK;
- pe ultima linie un număr natural L, reprezentând linia celulei de interes pentru Pacman.
Date de ieșire
În fișierul de ieșire pacman.out se va găsi valoarea celulei de pe linia L.
Restricții
- 1 ≤ L ≤ N ≤ 100 000
- 1 ≤ K ≤ 10, pentru toate celulele care conțin o sumă.
- 1 ≤ l1, l2, ..., lK ≤ N
- 1 ≤ val ≤ 100 000 000, pentru orice valoare a unei celule – fie dată direct de Pacman, fie obținută ca sumă.
- Pentru o celulă completată cu o sumă, valorile sale l1, l2, ..., lK nu sunt neapărat distincte două câte două. Altfel spus, într-o sumă termenii se pot repeta.
- O celulă nu depinde de ea însăși direct sau indirect. Altfel spus, orice celulă poate fi calculată pe baza valorilor altor celule calculate anterior.
- Pentru 50% din teste N ≤ 1 000
- Pentru 50% din teste toate celulele fie conțin valori fie depind de celule aflate deasupra lor.
Exemplu
pacman.in | pacman.out |
---|---|
5 N 1 N 1 S 2 1 2 S 2 5 3 S 2 2 3 4 |
5 |
Explicație
Valorile celulelor sunt, în ordine, de sus în jos, 1, 1, 2, 5 și 3. De interes pentru Pacman este doar a 4-a. Deci răspunsul este 5.