Page 14 - MATINF Nr.2

14 D.A. Popescu, C. B˘alc˘au, D. Constantin

eliminarea perechii din vˆarful stivei. Rezultatul va fi determinat folosind perechea din vˆarful
stivei (dac˘a exist˘a), sau va fi 0 dac˘a stiva este vid˘a.

Pentru a doua cerint , ˘a vom precalcula folosind metoda program˘arii dinamice o matrice
next[c][poz], care ne spune care este cea mai din stˆanga pozit , ie, aflat˘a la dreapta pozit , iei poz,
pe care se afl˘a un caracter c. Dac˘a nu exist˘a un caracter c pe o pozit , ie >= poz, vom ret , ine ˆın
next valoarea n + 1 (n fiind lungimea lui s). De asemenea, vom folosi s , i o stiv˘a ˆın care salv˘am
dup˘a fiecare operat , ie primul index (din s) la care se termin˘a o aparit , ie a lui t ca substring ˆın s
(sau n + 1 dac˘a t nu se g˘ases , te ca substring ˆın s). La fiecare operat , ie ”push c” verific˘am vˆarful
stivei s , i inser˘am ˆın stiv˘a valoarea next[c][vf], unde vf este elementul din vˆarful stivei. La fiecare
operat , ie ”pop” elimin˘am vˆarful stivei (dac˘a stiva nu e vid˘a). Rezultatul dup˘a fiecare operat , ie se
determin˘a comparˆand elementul din vˆarful stivei cu n: dac˘a este <= n, ˆınseamn˘a c˘a exist˘a o
aparit , ie a lui t ca subs , ir ˆın s care se termin˘a la pozit , ia respectiv˘a, altfel t nu se reg˘ases , te ˆın s.

Problema 2 – insule
Un arhipelag este alc˘atuit din mai multe insule, codificate prin numerele 1, 2, . . . , w. Pe unele
insule se g˘asesc localit˘at , i. Localit˘at , ile arhipelagului sunt codificate prin numere naturale nenule.
ˆ
Nu exist˘a dou˘a localit˘at , i codificate cu acelas , i num˘ar. Intre localit˘at , ile aceleias , i insule pot exista
s , osele (leg˘aturi directe), num˘arul total de s , osele din arhipelag este m.

Centrul de statistic˘a al arhipelagului realizeaz˘a cˆateva studii s , i pe baza informat , iilor de la
ministerul de transport obt , ine informat , iile:

1. num˘arul de leg˘aturi directe ˆıntre localit˘at , ile fiec˘arei insule i, 1 ≤ i ≤ w;
2. codurile insulelor (ˆın ordine cresc˘atoare) care cont , in un num˘ar maxim de grupuri de
localit˘at , i ˆıntre care se poate circula direct sau folosind localit˘at , i intermediare.

Cerint , ˘a

Cunoscˆand w, codurile localit˘at , ilor de pe fiecare insul˘a s , i cele m perechi de localit˘at , i din
arhipelag ˆıntre care exist˘a leg˘aturi directe prin s , osele se cere s˘a determinat , i:

1. num˘arul de leg˘aturi directe ˆıntre localit˘at , ile fiec˘arei insule i, 1 ≤ i ≤ w;
2. codurile insulelor (ˆın ordine cresc˘atoare) care cont , in un num˘ar maxim de grupuri de
localit˘at , i ˆıntre care se poate circula direct pe s , osele sau folosind localit˘at , i intermediare.

Date de intrare

Fis , ierul de intrare insule.in cont , ine pe prima linie un num˘ar natural p. Pentru toate
testele de intrare, num˘arul p poate avea doar valoarea 1 sau 2. Pe a doua linie a fis , ierului se
afl˘a w s , i m separate ˆıntre ele printr-un spat , iu. Urmeaz˘a w linii cu localit˘at , ile fiec˘arei insule ˆın
formatul: k x 1 x 2 ... x k , unde k este num˘arul de localit˘at , i, iar x 1 x 2 ... x k localit˘at , ile aflate pe
insula respectiv˘a. Apoi urmeaz˘a m perechi cu leg˘aturile directe prin s , osele ˆıntre localit˘at , i, cˆate
o pereche pe o linie, codurile localit˘at , ilor fiind separate prin cˆate un spat , iu.
Date de ies , ire

ˆ
Dac˘a valoarea lui p este 1, se va rezolva numai punctul 1) din cerint , ˘a. In acest caz, ˆın
fis , ierul de ies , ire insule.out se vor scrie w numere separate prin cˆate un spat , iu, reprezentˆand
num˘arul de leg˘aturi directe ˆıntre localit˘at , ile fiec˘arei insule i, 1 ≤ i ≤ w.
ˆ
Dac˘a valoarea lui p este 2, se va rezolva numai punctul 2) din cerint , ˘a. In acest caz, ˆın
fis , ierul de ies , ire insule.out se vor scrie codurile insulelor (ˆın ordine cresc˘atoare) care cont , in