Directorul
scolii doreste sa afle despre fiecare elev din scoala daca este cinstit (nu
minte niciodata) sau este mincinos. El stie cu siguranta ca cel putin jumatate
dintre elevi sunt cinstiti, dar ar dori sa afle cu exactitate caracterul fiecarui
elev.
În
acest scop, numeroteaza elevii de la 1
la n, aseaza elevii in
rand, intr-o ordine oarecare, apoi solicita
fiecare elev sa isi exprime parerea despre colegii situati in rand dupa el.
Un elev cinstit va spune întotdeauna adevarul: întrebat care e parerea
lui despre un mincinos, va raspunde neîndoielnic ca acesta minte, iar
despre un elev cinstit, ca nu minte niciodata. În schimb, un mincinos
va minti întotdeauna: va spune despre un elev cinstit ca minte, iar despre
unul asemenea lui, ca este cinstit.
Cum scoala este foarte mare, este posibil ca un elev sa nu îsi cunoasca
toti colegii, dar din afirmatiile elevilor se poate deduce in mod unic ordinea
in care acestia au fost asezati in rand.
Cerinta
Scrieti un program care sa determine pentru fiecare elev daca minte sau este daca cinstit.
Date de intrare
Fisierul de intrare honest.in contine pe prima linie doua numere naturale separate printr-un spatiu n m, reprezentând numarul de elevi, respectiv numarul de pareri exprimate. Pe fiecare dintre urmatoarele m linii sunt scrise triplete de forma: x c y unde x si y sunt numere întregi, (1 <= x, y <= n); x reprezinta numarul de ordine al elevului care este interogat referitor la elevul cu numarul de ordine y; c este un caracter si poate fi: 'c', semnificând faptul ca x spune despre y ca acesta este cinstit, respectiv 'm' daca x spune despre y ca acesta este mincinos; cele trei valori sunt despartite prin câte un spatiu.
Date de iesire
Fisierul de iesire honest.out va contine n linii, cate una pentru fiecare supus. Pe linia i se va scrie cifra 1 daca elevul i este cinstit, respectiv cifra 0 daca elevul i este mincinos.
Restrictii si precizari
0
< m <= 200 000
honest.in | honest.out |
5 8 |
1 |
Timp maxim de executie/test: 0.6 secunde
prof. Emanuela
Cerchez
Liceul de Informatica
"Grigore Moisil" Iasi
Contact:emanuela.cerchez@gmail.com