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 avatar spatarel Spatarel Dan-Constantin spatarel
Timp de execuție pe test 0.35 sec Limită de memorie 16384 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

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.

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 4 categorii