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

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


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

În acest episod din Tom&Jerry cele două personaje se urmăresc într-o peşteră. Peştera este formată din N camere (numerotate de la 1 la N), conectate între ele prin M culoare (numerotate de la 1 la M). Fiecare culoar conectează exact două camere. Între două camere este posibil să existe mai multe culoare.
Tom patrulează prin peşteră, parcurgând mereu acelaşi traseu. Traseul lui Tom începe în camera 1 şi se sfârşeşte în camera N. Jerry cunoaşte deja culoarele prin care trece Tom pe traseul său, precum şi timpul necesar lui Tom pentru a parcurge culoarele de pe traseu (mereu acelaşi). Tom nu zăboveşte în camerele peşterii.
Jerry se află iniţial în camera 1 şi doreşte să ajungă în camera N, bineînţeles fără a fi prins de Tom. Jerry se poate deplasa numai pe culoare, el ştiind care este timpul minim în care el poate să parcurgă fiecare culoar. Dacă este necesar, Jerry poate să parcurgă culoarul şi într-un timp mai îndelungat decât timpul minim necesar. În plus, când ajunge într-o cameră, Jerry se poate ascunde şi poate aştepta oricât timp doreşte.
Jerry va fi prins de Tom dacă:
- se află în acelaşi timp pe acelaşi culoar (Jerry va fi prins chiar dacă el intră pe culoar în momentul în care Tom părăseşte culoarul sau, invers, dacă el părăseşte culoarul în momentul în care Tom intră pe culoar);
- dacă intră într-o cameră în momentul în care Tom părăseşte camera sau invers, dacă părăseşte camera în momentul în care Tom ajunge în ea; dacă Jerry este deja în cameră (ascuns) când Tom intră/iese din cameră atunci el nu va fi prins.
Pentru ca Jerry să ajungă în siguranţă în camera N el trebuie prin urmare să nu fie prins de Tom pe traseu şi să ajungă în camera N înaintea lui Tom (pentru a se putea ascunde).

Cerinţă

Scrieţi un program care să verifice dacă Jerry poate ajunge din camera 1 în camera N a peşterii, fără să fie prins de Tom şi dacă da, ce traseu trebuie să urmeze el.

Date de intrare

Fişierul de intrare pestera.in conţine pe prima linie 3 numere naturale separate prin spaţii N M T, reprezentând numărul de camere din peşteră, numărul de culoare din peşteră şi respectiv numărul de culoare de pe traseul parcurs de Tom.
Pe următoarele M linii sunt descrise culoarele peşterii, câte un culoar pe o linie. Pe linia i+1 se află 3 numere naturale separate prin spaţiu X Y S, cu semnificaţia că prin culoarul i Jerry ajunge de la camera X la camera Y în minim S secunde.
Pe următoarele T linii este descris traseul lui Tom, specificând în ordinea parcurgerii culoarele parcurse de Tom, câte un culoar pe o linie. Mai exact, pe fiecare linie dintre cele T sunt scrise două numere naturale separate prin spaţiu C ST, cu semnificaţia că Tom va parcurge întotdeauna culoarul C în ST secunde.

Date de ieşire

Fişierul de ieşire pestera.out va conţine pe prima linie valoarea 1 dacă Jerry poate ajunge din camera 1 în camera N fără a fi prins de Tom, sau valoarea 0, în caz contrar. Dacă pe prima linie a fost scrisă valoarea 1, pe cea de a doua linie va fi scris un număr natural NR, reprezentând numărul de culoare parcurse de către Jerry pe traseul său de la camera 1 la camera N, iar in continuare vor fi scrise NR numere cuprinse între 1 şi M, separate prin spaţii, reprezentând culoarele parcurse de Jerry, în ordinea parcurgerii lor.

Restricţii

  • 2 ≤ N ≤ 2000
  • 1 ≤ M ≤ 100000
  • 1 ≤ T ≤ 100000
  • 1 ≤ S, ST ≤ 10000
  • Culoarele peşterii pot fi parcurse în ambele sensuri.

Exemple

pestera.in pestera.out
4 4 5
1 3 6
1 2 2
2 3 2
3 4 1
2 1
2 2
2 1
3 4
4 1


1
2 1 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, partitie, sokoban, pitag, porumb, cheie, conferinta, chei, 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, 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, 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, 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 drum minim: miniasm, robot, furtuna, excursie, arthur, bete, zmeu, trafic, masina1, bomboane, traseu, litoral, lover, trip, scara2, team, gard, pitici1, base3, coach, lanturi, trmv, fluviu, ubuntzei, razboi, benzina2, kubus2, megascoala, dragoni
Software recomandat
surse trimise | ajutor