Diferențe pentru problema/ruine între reviziile #13 si #8

Ruine

ruine

Într-o regiune turistică sunt $N$ sate dispuse în linie. Inițial, oricare două sate vecine sunt unite printr-un drum. Cu timpul, drumurile se surpă și nimeni nu le repară. În fiecare sat $i$ sunt [$T$][~i~] obiective turistice de vizitat. Biroul de Turism din regiune primește mesaje de două tipuri:
* primăriile anunță când un drum se surpă

* turiștii pun întrebări de forma: „Câte obiective pot fi vizitate în satul $q$ și în satele la care se mai poate ajunge din $q$ ”?

* turiștii pun întrebări de forma: „Câte obiective pot fi vizitate în satul $i$ și în satele la care se mai poate ajunge din $i$ ”?

h2. Date de intrare
Fișierul de intrare $ruine.in$ conține pe prima linie numerele $N$ și [$M$], reprezentând numărul de sate și numărul de mesaje primite de Biroul de Turism. Pe a doua linie se află $N$ numere [$T$][~1~], [$T$][~2~], ..., [$T$][~N~]. Pe următoarele $M$ linii sunt mesajele primite de Biroul de Turism, sub formele:

* S $q$ -- mesajul indică că drumul între satele $q$ și $q$ + 1 s-a surpat (1 &le; $q$ < [$N$]);
* T $q$ -- mesajul întreabă numărul total de obiective în satul $q$ și în satele accesibile din $q$ (1 &le; $q$ &le; [$N$]).

* S $i$ -- mesajul indică că drumul între satele $i$ și $i$ + 1 s-a surpat (1 &le; $i$ < [$N$]);
* T $i$ -- mesajul întreabă numărul total de obiective în satul $i$ și în satele accesibile din $i$ (1 &le; $i$ &le; [$N$]).

h2. Date de ieșire

h2. Exemplu
table(example).

|_. ruine.in |_. ruine.out |

|_. ruine.in |_. ruine.out |_. Explicații |

| 6 7

2 8 5 4 3 4
T 4
S 2
T 4
T 1
S 5
T 2
T 6

  2 8 5 4 3 4
  T 4
  S 2
  T 4
  T 1
  S 5
  T 2
  T 6

| 26

16
10
10
4

  16
  10
  10
  4
| Inițial, din satul 4 se poate ajunge în toate satele. Se surpă drumul 2-3.
  Din satul 4 se poate ajunge în satele 3, 5 și 6.
  Din satul 1 se poate ajunge în satul 2. Se surpă drumul 5-6.
  Din satul 2 se poate ajunge în satul 1.
  Satul 6 este izolat.

|

h3. Explicație
 
Inițial, din satul 4 se poate ajunge în toate satele.
Se surpă drumul 2-3.
Din satul 4 se poate ajunge în satele 3, 5 și 6.
Din satul 1 se poate ajunge în satul 2.
Se surpă drumul 5-6.
Din satul 2 se poate ajunge în satul 1.
Satul 6 este izolat.
 
 

== include(page="template/taskfooter" task_id="ruine") ==