Fişierul intrare/ieşire:pacman.in, pacman.outSursăOlimpiada pe scoala 2016 clasa a 8-a
AutorDan SpatarelAdăugată despatarelSpatarel Dan-Constantin spatarel
Timp execuţie pe test0.35 secLimită de memorie16384 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

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.inpacman.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici