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

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


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

Într-o zonă dreptunghiulară cu p linii şi q coloane se află n roboţi. Celula din stânga sus se află pe linia 1 şi coloana 1. Pentru fiecare robot se cunoaşte linia şi coloana pe care se află, precum şi orientarea lui. Un robot poate fi orientat în una din cele patru direcţii: nord, sud, est sau vest, codificate cu caracterele N, S, E, respectiv V. Fiecare robot execută m comenzi. O comandă este codificată printr-un caracter L,R sau F. La o comandă de tip L, robotul se întoarce cu 90 de grade spre stânga, în sensul invers acelor de ceasornic. La o comandă de tip R, robotul se întoarce cu 90 de grade spre dreapta, în sensul acelor de ceasornic. La o comandă de tip F, robotul se deplasează cu o poziţie în sensul în care este orientat robotul.
Roboţii execută simultan prima comandă din şirul lor de comenzi, apoi a doua comandă, etc.
Dacă la un moment dat, doi sau mai mulţi roboţi ajung în aceeaşi poziţie, aceasta va conduce la dispariţia lor, iar celula din care dispar se consideră traversată de toţi cei care au dispărut.
Dacă un robot se deplasează în afara suprafeţei la execuţia unei comenzi, robotul dispare.
Se consideră trecere printr-o celulă vizitarea rezultată în urma executării unei comenzi de tip F. Dacă un robot trece de mai multe ori printr-o celulă, se contorizează fiecare trecere a sa. Celula din care pleacă fiecare robot se consideră trecere pentru robotul respectiv.

Cerinţă

Scrieţi un program care să determine:
a) numărul de roboţi rămaşi după execuţia celor m comenzi,
b) poziţia celulei din zonă prin care s-a trecut cel mai des (dacă există mai multe celule, atunci se va preciza cea cu indicele de linie cel mai mic, iar dacă există mai multe cu acest indice, cea cu indicele de coloană cel mai mic) şi numărul de treceri prin această celulă.

Date de intrare

Fişierul roboti1.in conţine pe prima linie numerele naturale p q separate printr-un spaţiu, reprezentând numărul de linii şi de coloane ale zonei. Pe a doua linie se află numărul natural n, reprezentând numărul de roboţi. Pe următoarele n linii se află câte trei valori separate prin câte un spaţiu, reprezentând linia, coloana şi orientarea fiecărui robot. Pe următoarea linie se află numărul natural m reprezentând numărul de comenzi de executat de către fiecare robot. Pe următoarele n linii se află câte m caractere reprezentând comenzile pentru fiecare robot (mai întâi cele m comenzi pentru primul robot, apoi cele m comenzi pentru al doilea robot, ş.a.m.d.). Între caracterele unei comenzi nu există nici un spaţiu.

Date de ieşire

Fişierul roboti1.out va conţine pe prima linie numărul de roboţi rămaşi în final. Pe linia a doua se va scrie poziţia celulei (linie şi coloană) prin care s-a trecut cel mai des (dacă există mai multe celule, atunci se va preciza cea cu indicele de linie cel mai mic, iar dacă există mai multe cu acest indice, cea cu indicele de coloană cel mai mic) şi numărul de treceri prin această celulă, trei valori separate prin câte un spaţiu.

Restricţii

1<= p, q, m <= 50
2<= n <= 50

Caracterele cu care se codifică orientările pot fi doar N, S, E, V, iar cele pentru comenzi L, R sau F (litere mari).
Iniţial, nu există doi sau mai mulţi roboţi în aceeaşi celulă.

Exemple

roboti1.inroboti1.outExplicaţii
4 4 3 1 1 E 1 3 V 4 4 S 2 FL FF FF 0 1 2 2 După prima comandă, roboţii 1 şi 2 ar trebui să ajungă în aceeaşi celulă, deci dispar. Al treilea robot conform primei deplasări va părăsi zona, deci dispare. În final vor fi 0 roboţi. Doi roboţi au ajuns în celula de pe linia 1 şi coloana 2, după care au dispărut. Prin celelalte celule s-a trecut maxim o singură dată.

autor: Prof. Roxana Tîmplaru
propunător: Prof. Emanuela Cerchez
Liceul de Informatică ″Grigore Moisil″
emanuela.cerchez@gmail.com
Probleme recomandate
De la ONIG 2010: control1, figura, joc14, fractie1, neuroni, raze, char, maraton1, cluburi, domino1, bila, dartz
De acelaşi autor: numere4, tablou, numar1, prieteni2, roboti, numere6, cartonas, test1, v, cuvant, asfalt, grupe2, joc17, numar5, munte3
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, 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, arrows, pseudobil, patrat1, rascoala, harta2, relatii, lasere, defrag, matcnt, ssdj, cript, ssk, teren1, fence, cifre6
surse trimise | ajutor