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

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


Timp maxim de execuţie/test:
0.2 secunde
Memorie totala disponibilă/stivă:
16 MB/8 MB

Vasile îşi păstrează economiile în N purceluşi-puşculiţă de ceramică neagră. Purceluşii sunt numerotaţi de la 1 la N. Fiecare purceluş are un capac care poate fi deschis cu cheia corespunzătoare.
În purceluşi Vasile a pus bani, dar şi cheile de la purceluşi. Desigur, Vasile ţine minte în care purceluşi a pus cheile.
Fiindcă vrea să-şi cumpere o maşină nouă, Vasile are nevoie de toţi banii din purceluşi. Pentru a obţine banii dintr-un purceluş el poate sparge purceluşul sau poate deschide capacul cu cheia (dacă o are).

Cerinţă

Cunoscând distribuţia cheilor în purceluşi, să se determine numărul minim de purceluşi pe care trebuie să îi spargă Vasile astfel încât să poată obţine toţi banii.

Date de intrare

Fişierul de intrare chei.in conţine pe prima linie un număr natural N, reprezentând numărul de purceluşi. Pe fiecare dintre următoarele N linii este scris câte un număr natural cuprins între 1 şi N; numărul de pe linia i+1 reprezintă numărul purceluşului în care este plasată cheia de la purceluşul i.

Date de ieşire

Fişierul de ieşire chei.out va conţine o singură linie pe care va fi scris un singur număr natural reprezentând numărul minim de purceluşi ce trebuie să fie sparţi pentru a obţine toţi banii.

Restricţii

  • 1<=N<=100000

Exemple

chei.in chei.out Explicatie
4
2
1
2
4

2
Cheile de la purceluşii 1 şi 3 se află în purceluşul 2.
Cheia de la purceluşul 2 se află în purceluşul 1
Cheia de la purceluşul 4 se află în purceluşul 4.
Numărul minim de purceluşi ce trebuie să fie sparţi este 2 (spargem purceluşul 2 şi purceluşul 4).
chei.in chei.out Explicatie
4
1
2
3
4

4
Numărul minim de purceluşi ce trebuie să fie sparţi este 4.
prof. Emanuela Cerchez
Colegiul Naţional "Emil Racoviţă" Iaşi
emanuela.cerchez@gmail.com
propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la .campion 2010: greiere, divizori, kdist, pestera, partitie, sokoban, pitag, porumb, cheie, conferinta, stelar, atelier, secv9, ny, radical, arbgraf, select, divk, bileprime, nx, reuniune, cazare, proiect, taler, atletism, echipa, ghinion, oldest, war, aliniere, sumb, cavaleri, joct, fluviu, camera616, aritm, stele, covor, subm, mess, secvnumber, cladire, ssmax, parcela, pion, subs, universitate, el, mahjong, rotund, sirmax, bdotcom, pack
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, honest, 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, 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, honest, 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, 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 conexitate: arce, flood, matrice, shgraf, trip, pact, echipe1, vitale, spion, bcolor, mexc, dep, fazan, cfr, teme, entries, pamant, neconex, module, drumuri2, cristal, nuclee
Software recomandat
surse trimise | ajutor