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

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


Timp maxim de execuţie / test:
0.3s
Memorie totala disponibilă / stivă:
16MB / 1MB

Zăhărel vrea să plece într-o excursie împreuna cu K dintre cei N prieteni (numerotaţi de la 1 la N) ai săi. Desigur, nu poate lua cu el orice grup de K prieteni, deoarece prezenţa anumitor prieteni este condiţionată de prezenţa altora. Fiind un bun cunoscător al interacţiunilor sociale din cadrul grupului său de prieteni, Zăhărel a făcut o listă cu toate cele M dependenţe existente în grupul său: perechi de numere i j cu semnificaţia că prietenul cu numărul i va veni în excursie, doar dacă prietenul cu numărul j vine şi el. Vom numi o astfel de relaţie dependenţă directă.
Vom spune în continuare că doi prieteni i j sunt în dependenţă indirectă dacă sunt în dependenţă directă sau dacă există un şir de T≥1 numere v1 v2 ... vT, astfel încât i depinde direct de v1, vp depinde direct de vp+1 (pentru 1≤p<T) şi vT depinde direct de j.
La o analiză atentă a celor M relaţii Zăhărel a observat ca există o proprietate interesantă în cadrul grupului său: pentru oricare trei prieteni distincţi cu numere i j k, dacă i depinde indirect de j şi i depinde indirect de k, atunci j depinde indirect de k, sau k depinde indirect de j, sau ambele.

Cerinţă

Să se scrie un program care determină în câte moduri poate alege Zăhărel K dintre cei N prieteni ai lui pentru a merge în excursie, ţinând cont de cele M relaţii de dependenţă.

Date de intrare

Fişierul de intrare dep.in va conţine pe prima linie numerele N M K. Următoarele M linii vor conţine perechi de numere i j reprezentând dependenţele directe.

Date de ieşire

Fişierul de ieşire dep.out va conţine pe prima linie un singur număr reprezentând în câte moduri poate alege Zăhărel K dintre cei N prieteni. Rezultatul se va afişa modulo 666013.

Restricţii

1 ≤ K ≤ N ≤ 256
0 ≤ M ≤ N*(N-1)/2

Pentru 20% din teste N ≤ 25
Pentru 40% din teste nu vor exista dependenţe indirecte ciclice (i depinde indirect de i)

Exemple

dep.indep.outExplicaţii
5 8 3 1 2 2 1 1 3 2 3 4 5 5 4 4 3 5 3 2 Zăhărel poate merge excursie fie cu prietenii 1 2 3, fie cu prietenii 3 4 5.



autor: Mircea Paşoi
propunător: Prof. Emanuela Cerchez
Liceul de Informatica ″Grigore Moisil″
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la ONI 2008: ab2, iepuras, palind, auto, div, teatru, pm, submat, reteta2, rezervatie, creioane, melci, mere2, felinare, joc3, 2numere, fi, tablou, borcane, mexc, tcast, dist1, stiva, banda, pavare, poarta, aranjare, bile4, subgeom, albinuta1, curent, pviz, atac2, virus
De acelaşi autor: copaci, ab2, plimbare, cuvinte, pioni, reinvent, numere3, perm, criptare, sume, gramezi, nr2, rev, paintball, matricea, emax, turism, puncte1, casute
Despre programare dinamică: vedete, fbr, tgv, zeratul, rv, comun, retea, circuit, sumdif, copaci, drum, text, palind, joc, vikingi, rafturi, balaur, plimbare, party, pc, pioni, seif, iepuri, numere3, perm, ture, bilete, prop, ro, reduceri, cuburi, invest, cutie2, stalpi, nr2, judete, strict, auto2, tree, jobs, leaves, pstring, program, datorii, senzori, farfurii, joc1, barbie, ambigram, rlcs, cub1, bio, chimie1, otilia, pasune, remi, sir23, tren1, joc5, pachete, echipe, comb, agitatie, ivv, peste, pitici, pipe, shgraf, tabara1, stop, randuri, zidar, log, sant, produs, subsir, cover, bcast, emax, dist, mesaj1, imax, avere, asmax, raft, suma2, joc12, fni, nr4, join, transport, masina3, lsort, microvirus, fat, cafea, echipe1, anticip, bsir, diamant, petrom, evantai, spion, acolor, evo, bombo, lacusta, lant, team, pitici1, numere8, stiva, subgeom, pviz, tir1, cabane, piramida1, mosia, cuvinte1, gaina, materom, sortari, turnuri, trans, politie, codul, dansatori, nkbiti, kperms, treegame, siruri2, 123, jucarii, bradut, joc15, expozitie, text3, ic, echilibru, distsir, kmax, stalpi1, gaz, triunghi2, v2d, cuiburi, mine, orientare, activ, secvbiti, kcons, pokemon, ubergraf, left, acerc, autostrazi, kdist, select, cazare, fluviu, telecomanda, parcela, pion, subs, suma4, sirmax, bdotcom, viena, sablon2, telecab, ikebana, radare, hacker, obstacole, robotel, centrala, verigi, cds, wg, minusk, radioactiv, enigma, jb, efect, maxviz, ripstick, progresii, maxtri, combcuv, blis, subsiruri, mijloc, probleme, unuzero, palindrom1, minerale, speed, zmax, spider, cntgcd, interclasare, bus, pariuri, riglef, fractii2, fall, arbsum, conuri, arbvalmax, procente, metrou
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, 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 arbori: bonuri, tgv, barfa, votare, arce, balaur, trains, bile2, vmem, plopi, caravane, mese, strict, tree, sub, kinder, firma1, albinuta, rlcs, masina, omizi, concurs1, latime, piloti, barca1, arbnr, sirag1, pikachu, arb, logn, maxq, arbore, bcast, mesaj1, traseu, asmax, salvare, tramvai1, omida, sediu, string, tv, izo, zoo, ratina, vitale, camion1, arbfind, cezar1, tcast, curent, spp, frunze, sea2, culori, color, urgenta, nori, treegame, antipatie, scanduri, minuni, arb1, activ, regat, kdtree, autostrazi, carray, trenuri1, arbgraf, war, mess, secvnumber, subs, posta, radare, arbore1, hacker, lista, codarb, subsecvente, confuzie, transform, arbsum, copaci3, arbvalmax
Despre conexitate: arce, flood, matrice, shgraf, trip, pact, echipe1, vitale, spion, bcolor, mexc, fazan, cfr, chei, teme, entries, pamant, neconex, module, drumuri2, cristal, nuclee
surse trimise | ajutor