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

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


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

Şeful meu a plecat, pentru prima oară în viaţă, la New York. În timp ce aştepta un taxi într-o intersecţie, el a fost răpit. Răpitorii l-au urcat într-o maşină cu scopul de a-l duce către ascunzătoarea lor secretă. Fiind evident că şeful nu cunoaşte oraşul, ei nu l-au legat la ochi, aşa că el a reuşit să memoreze drumul urmat de maşină.
Oraşul arată ca o matrice formată din blocuri foarte înalte (zgârie-nori), între oricare două blocuri alăturate existând o stradă. Eu am o hartă pe care străzile sunt numerotate de la 1 începând de sus în jos şi respectiv de la stânga la dreapta. Pe hartă este marcată înălţimea fiecărui bloc.
Şeful meu îmi trimite prin SMS înălţimile blocurilor pe lângă care trece (cel din stânga şi cel din dreapta).
Când ajunge într-o intersecţie şoferul poate să o ia la dreapta, la stânga, înainte sau înapoi.
Când ajunge la ascunzătoarea răpitorilor, şeful meu îmi scrie un ultim mesaj în care îmi cere să determin locaţia intersecţiei de străzi în care se află ascunzătoarea răpitorilor şi să o comunic poliţiei.

Cerinţă

Scrieţi un program care, analizând harta oraşului şi indicaţiile şefului să determine toate posibilele locaţii ale ascunzătorii răpitorilor.

Date de intrare

Fişierul de intrare ny.in conţine pe prima linie două numere naturale separate prin spaţii, N şi M reprezentând numărul de linii şi respectiv numărul de coloane din matricea care reprezintă harta oraşului. Pe fiecare dintre următoarele N linii se află câte M numere naturale nenule, reprezentând înălţimile zgârie-norilor din oraş.
Pe următoarea linie este scris un număr natural Lg, reprezentând lungimea traseului străbătut.
Pe următoarea linie sunt scrise Lg numere naturale nenule separate prin spaţii, reprezentând înălţimile blocurilor de pe traseu, aflate în stânga şefului.
Pe ultima linie sunt scrise Lg numere naturale nenule separate prin spaţii, reprezentând înălţimile blocurilor de pe traseu, aflate în dreapta şefului.

Date de ieşire

Fişierul de ieşire ny.out va conţine locaţiile posibile ale ascunzătorii răpitorilor, câte o locaţie pe linie. Acestea vor fi afişate în ordinea crescătoare a liniilor şi, dacă există mai multe locaţii cu aceeaşi linie, în ordinea crescătoare a coloanelor. Pentru fiecare locaţie sunt scrise două numere naturale separate printr-un spaţiu L şi C, reprezentând linia (strada orizontală) şi coloana (strada verticală) intersecţiei în care se află ascunzătoarea.

Restricţii

  • 3 ≤ N, M ≤ 100
  • 1<=Lg<=10000
  • Înălţimea oricărui bloc este ≤ 10000 de etaje.
  • Locatiile intersectiilor in care se poate afla ascunzatoarea au linia cuprinsa intre 1 si N, respectiv coloana cuprinsa intre 1 si M.

Exemple

ny.in ny.out
3 3
1 2 3
4 5 6
7 8 9
3
4 2 6
5 5 5


2 2
ny.in ny.out
4 4
1 2 2 1
2 1 1 2
1 2 1 2
2 1 1 2
5
1 1 1 1 1
2 2 1 2 2


1 2
1 3
1 4
2 1
3 1

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, chei, stelar, atelier, secv9, 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, chei, 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 coada: balanta, inginer, camp, rebus, harta, insule, volei, lbd, magic3, axa, cadere, reinvent, ocean14, iepuras2, sah, balls, cd, toys, radio, caini, subperm, castel, excursia, casute, soricel2, masina2, salvare, paianjen, suma2, garaj, alee, lanterna, rj, caraibe, taxe1, sotron1, lanturi, tom, k1, dreptunghiuri, sokoban, oldest, drumuri1, alpinist, tsunami, robot3, joc19, valet, oras1, gheizere, zone, taxa, abq, cartite, joc21, traseu3, panda, expand
Despre Lee: inginer, insule, lbd, ocean14, iepuras2, sah, radio, lacuri, castel, excursia, soricel2, masina2, paianjen, suma2, soricel3, cub2, alee, rj, taxe1, sotron1, tom, ai, robot3, pixy, valet, oras1, maxtri, lgdrum, gheizere, abq, cartite, joc21, traseu3, wow, panda
Software recomandat
surse trimise | ajutor