.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » honest

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
.campion
honest


Timp maxim de executie/test:
0.65 secunde
Memorie totala disponibila/stiva:
16 MB/1 MB

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

  • 1 < n <= 1000
  • 0 < m <= 200 000

Exemplu

honest.in honest.out

5 9
1 c 2
2 c 3
1 m 4
2 m 4
5 c 4
3 m 4
1 m 5
2 m 5
5 m 3

1
1
1
0
0

prof. Emanuela Cerchez
Liceul de Informatica "Grigore Moisil" Iasi
Contact:emanuela.cerchez@gmail.com

propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la .campion 2005: cuc, prime, radio, text2, police, comori, patrate3, fisc, ref, pcod, zmeu, loc, nr01, scor2, judete, strict, convert, bile3, cod2, depou, auto2, tree, cat, nr3, chimie2, compress, jobs, leaves, zid, politics, onu2, ploaia, grazing, pstring, cartonase2, exp, cartoane, sir3, program, scoici, playlist, sqr, cai1, farfurii, joc1, trafic, carte, set, barbie, labirint, firma1, vile, game, donald, ambigram, dans, albinuta, rlcs, stea, submatrix, cub1, ham, sponsori, young, jokes, pizza1, albine, lot, atac1, monede1, count, exam, herbert, sudoku, bio, metro
De acelaşi autor: celule, scp, vedete, film, ab, supertri, inginer, camp, sl, detinut, simetric, egal, gropi, ruleta, carti, tgv, uscat, afise, dezbateri, bunici, rv, onu, nspecial, secvop, cadou, chimie, reteta, piticot, petrol, checkin, teanc, index, teren, pizza, ecran, drum, text, lbd, aven, spam, pluricex, tren2, gray, pasi, mgo, joc, anagrame, vecini, criptmat, maxim, cutie, party, friends, net, sablon, hd, pc, sir2, aztec, scara, nr, robot2, sah, formule, ed, bilete, hanoig, flood, matrice3, erdos, grup, cd, kfactor, np, cuc, radio, ref, nr01, scor2, convert, auto2, compress, politics, pm, playlist, barbie, firma1, submatrix, ham, pizza1, exam, ants, teatru1, cifre1, bile1, caini, secvreg, pasune, remi, m01, sir23, tren1, joc5, pachete, aedaro, windows, renju, latime, mere1, piloti, peste, pitici, sirag1, stive, turn1, carti1, program1, spioni, kgb, lift, apel, lex, oras, homeless, subsir, dist, harta1, adevar, joc10, bare, zapezi, masina2, perechi1, raft, joc11, joc12, ferma, fni, tunel, lover, pepsi, transport, avion, monkey, premii1, garaj, carti2, tv, pact, fat, cafea, echipe1, secvente, petrom, peg, scara1, lant, ecuatii, stiva, bile4, jungla, rj, poli, text1, compus1, rez, politie, anag, codul, coment, muzeu, seti, basm, timer, secvsir, dp, placa, prod3, bursa, submdisj, sotron1, fazan, secvpar, joker, lego, medalii, cfr, antipatie, figura, links, segm, colorare, brazi, mobil, distsir, guess, greiere, pestera, conferinta, chei, ny, nx, ghinion, sumb, drenaj, telecomanda, grupuri, mahjong, rotund, viena, sport2, cos, monoton, micro, valet, nr0, maxviz, anagramabil, nrpal, lista, dame, consiliu, adprod, arme, deal, prodnr, compar, latin, interviu, vintage, prize, nrdiv, arrows, tdrept, agenda, reziston, vot2, tema, smiley, relatii, ech, scadere, nebuni, castig, expand, wb, prime2, virgule, b210
Despre graf: gropi, tgv, matrice2, miniasm, picnic, mere, circuit, soldati, arce, conflicte, desen, robot, furtuna, net, cuvinte, excursie, cadere, pioni, reinvent, kreg, flood, croco, johnie, matrice, arthur, kimberley, ro, sol, caravane, bete, police, pcod, zmeu, auto2, grazing, datorii, trafic, sponsori, monede1, apm, bile1, caini, masina1, bomboane, turn1, shgraf, paintball, program1, tgraf, kgb, algola, felinar, joc6, tric, homeless, promo, turism, casute, joc10, prieteni1, traseu, zapezi, litoral, lover, trip, garaj, ziduri, tv, pact, echipe1, vitale, spion, trasee, bcolor, scara2, lant, ab3, soc, team, gard, rsp, graf, mexc, dep, albinuta1, atac2, cabane, drumuri, tj, grade, jungla, lanterna, magic5, coment, urgenta, fazan, lanturi, cfr, site, traseu1, trmv, graphgame, minuni, telefon, ubergraf, carray, pestera, chei, arbgraf, war, fluviu, drumuri1, entries, ubuntzei, pack, fotbal1, pamant, dag, razboi, benzina2, wg, neconex, asfalt1, kubus2, module, progresii, dfs, prieteni3, megascoala, grafxy, dineu, vot1, biperm, drumuri2, nrgraf, cristal, cartite, copaci3, dragoni, nuclee
Despre Sortare topologică: dezbateri, pitici1, drumuri2
Software recomandat
surse trimise | ajutor