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

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


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

″Arrows″ este un joc care se joacă pe o tablă dreptunghiulară a cărei suprafaţă este împărţită în NxM celule, aranjate pe N linii şi M coloane. În fiecare celulă se află o săgeată (sus, jos, stânga sau dreapta), ca în figura de mai jos:



Când este la mutare, un jucător poate alege o poziţie de start pe care plasează un jeton, apoi deplasează jetonul la celula învecinată în sensul indicat de săgeată. Deplasarea continuă până când jetonul părăseşte tabla de joc, caz în care jucătorul obţine un punctaj egal cu numărul de celule parcurse de jetonul său.
Există însă poziţii de start denumite favorabile, pentru care jetonul nu va părăsi niciodată tabla de joc. De exemplu, toate poziţiile din figură cu fundal gri sunt favorabile. Jucătorul care alege o poziţie de start favorabilă obţine un punctaj egal cu numărul de celule distincte vizitate înmulţit cu 1000.

Cerinţă

Scrieţi un program care, cunoscând configuraţia tablei de joc, rezolvă una dintre următoarele cerinţe:
1. determină punctajul pe care îl obţine un jucător care plasează jetonul său pe o poziţie de start specificată;
2. determină numărul de celule favorabile de pe tabla de joc;
3. determină punctajul maxim pe care jucătorul îl poate obţine la o mutare, alegând convenabil poziţia de start.

Date de intrare

Fişierul de intrare arrows.in conţine pe prima linie cerinţa care trebuie să fie rezolvată (1, 2 sau 3). Pe a doua linie se află numerele naturale N M, care reprezintă numărul de linii şi respectiv de coloane de pe tabla de joc. Pe următoarele N linii se află câte M numere din mulţimea {1,2,3,4} reprezentând săgeţile aflate în celulele de pe tabla de joc (1 semnificând săgeata la dreapta, 2 săgeata în sus, 3 săgeata la stânga şi 4 săgeata în jos). Pe ultima linie sunt scrise numerele naturale lin col, reprezentând linia şi coloana pe care se află poziţia de start specificată. Valorile scrise pe aceeaşi linie în fişierul de intrare sunt separate prin spaţii.

Date de ieşire

Fişierul de ieşire arrows.out va conţine o singură linie pe care va fi scris un număr natural reprezentând răspunsul pentru cerinţa specificată pe prima linie a fişierului de intrare.

Restricţii

1 ≤ N, M ≤ 500
• Liniile sunt numerotate de la 1 la N, iar coloanele de la 1 la M.
• Punctaj. Pentru teste valorând 20 de puncte cerinţa este 1. Pentru teste valorând 40 de puncte cerinţa este 2. Pentru celelalte teste, valorând de asemenea 40 de puncte, cerinţa este 3.

Exemple

arrows.inarrows.outExplicaţii
1 6 5 3 1 1 4 2 1 2 4 3 1 4 2 1 1 4 1 2 3 3 3 3 1 4 4 4 2 2 3 4 2 5 5 2000 Exemplul corespunde tablei de joc din figură.
Punctajele pentru fiecare poziţie sunt:
1 14000 14000 14000 1
15000 14000 14000 14000 1
16000 14000 14000 14000 14000
15000 14000 14000 14000 14000
1 4000 4000 2 2000
2 4000 4000 1 2000

Cerinţa este 1: punctajul care se obţine plecând din poziţia de start aflată pe linia 5 şi coloana 5 este 2000.
2 6 5 3 1 1 4 2 1 2 4 3 1 4 2 1 1 4 1 2 3 3 3 3 1 4 4 4 2 2 3 4 2 5 5 23 Cerinţa este 2: există 23 de poziţii favorabile.
3 6 5 3 1 1 4 2 1 2 4 3 1 4 2 1 1 4 1 2 3 3 3 3 1 4 4 4 2 2 3 4 2 5 5 16000 Cerinţa este 3: punctajul maxim se poate obţine plasând jetonul în punctul de start de pe linia 3 şi coloana 1.

autor: Prof. Emanuela Cerchez
propunător: Prof. Emanuela Cerchez
Colegiul Naţional ″Emil Racoviţă″
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la OJI 2014: tcif, imprimanta, munte3, ferma1, triunghi6, cartite, fractii2, cool, pseudobil, martisoare, piramide, patrat1, schi1
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, 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, tdrept, agenda, reziston, vot2, tema, smiley, relatii, ech, scadere, nebuni, castig, expand, wb, prime2, virgule, b210
Despre matrice: vopsea, harta, opmat, sarpe, light, magic2, tetris, origami, concurs, iepuras, tribile, criptmat, cutie, patrate, 3d, pajura, perspic, vecini2, livada, matrice3, kafka, erdos, grup, scor2, reteta2, rezervatie, scoici, tablou, game, stea, submatrix, cifru, jokes, oua, trecere, na, dotnet, renju, ghici, mere1, agitatie, lacuri, sotron, desen1, camion, ceas1, fibo, parc, excursia, matricea, zidar, joc6, log, concurs2, cladiri, dist, centru, robinson, cuburi2, joc8, joc9, romeo, adevar, soricel2, avere, joc11, vizibil, sah1, blockout, masina3, lsort, anticip, matrice1, evantai, spion, pereti, zumzi, roboti, placare, tabel, ocr, numere7, lacusta, becuri, sir5, flori, cartele, furnica, pavare, poarta, rj, peri, poligon2, sablon1, gradina, matrice4, poartas, balcon, submdisj, v, matrx, figura, neuroni, raze, roboti1, bila, iepurasi, colorare, mat, submatrix1, simetric1, plaja, xor2, guess, albine1, joct, alfabetar, stele, tablou1, alpinist, cladire, cri, grupe2, el, mahjong, sir9, acces, tort1, joc17, mesaj3, zar1, xy, poteci, avioane, broscute, safeu, acoperire1, radioactiv, robot4, lcdr, jb, slide, maxtri, dame, triunghi4, elicop, compresie, mijloc, cubulete, romb, 2ndesc, medalion, bile6, zigzag, puncte5, intersectii, matd3, matrixdel, speed, seif1, traseu2, incadrare, betasah, zona, latin, zmax, amestec, sudoku1, gradina1, spider, zone, bemo, rombul, interclasare, rebus1, tabla, pseudobil, patrat1, rascoala, harta2, relatii, lasere, defrag, matcnt, ssdj, cript, ssk, teren1, fence, cifre6
Software recomandat
surse trimise | ajutor