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

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


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

Ne amintim cu toţii jocul „avioane” pe care în jucam la şcoală, în pauze, cu colega de bancă. În problema noastră jocul se desfăşoară pe o suprafaţă cu N linii şi N coloane. Un “avion” este o piesă care ocupă poziţii de pe suprafaţa de joc dispuse exact în ordinea:

x
x x x x x
x
x x x
x

Valorile marcate cu x aparţin avionului, iar celelalte nu. Sunt acceptate şi celelalte trei configuraţii ce se obţin prin rotirea poziţiei date cu 90, 180, 270 grade. Suprafaţa de joc are unele poziţii care nu pot fi ocupate de un avion.

Cerinţă

În problema noastră se cunoaşte dimensiunea suprafeţei pătrate şi configuraţia sa şi se cere determinarea numărului maxim de avioane ce se pot aşeza, precum şi o modalitate de aşezare a acestui număr maxim.

Date de intrare

Fişierul avioane.in are pe prima linie un număr natural N, dimensiunea suprafeţei. Pe fiecare dintre următoarele N linii sunt câte N valori întregi din mulţimea {0,-2} separate prin câte un spaţiu. Valoarea 0 reprezintă poziţie ce poate fi ocupată de un avion, iar valoarea -2 o poziţie ce nu poate fi ocupată.

Date de ieşire

În fişierul avioane.out, pe prima linie se va scrie numărul maxim de avioane ce se pot aşeza, notat cu M. Pe următoarele N linii se găsesc câte N numere întregi separate prin câte un spaţiu ce pot avea valorile: -2, 0, 1, 2, …, M. Valoarea i (1<=i<=M) se găseşte exact pe poziţiile ocupate de avionul i. Elementele de pe poziţiile neocupate de avioane au exact valorile corepunzătoare poziţiei respective din fişierul de intrare.

Restricţii

  • 5 <= N <= 10
  • avioanele trebuie aşezate complet în interiorul suprafeţei;
  • o poziţie de pe suprafaţă poate fi ocupată de cel mult un avion;
  • dacă sunt mai multe aşezări posibile cu număr maxim de avioane se poate afişa configuraţia corespunzătoare oricăreia dintre ele;
  • valorile scrise pe aceeaşi linie in fişierele de intrare/ieşire sunt separate prin spaţii.

Exemplu

avioane.in avioane.out
8
0 0 0 0 0 0 0 0
0 0 0 0 0 0 -2 0
0 0 0 0 0 0 0 0
0 0 0 0 -2 0 0 0
0 0 0 -2 0 0 0 0
0 0 0 0 0 0 0 0
0 -2 0 0 0 0 0 0
-2 0 0 0 0 0 0 0
2
0 0 0 0 0 1 0 0
0 0 0 1 0 1 -2 0
0 0 1 1 1 1 1 0
0 0 2 1 -2 1 0 0
0 0 2 -2 2 1 0 0
0 2 2 2 2 2 0 0
0 -2 2 0 2 0 0 0
-2 0 2 0 0 0 0 0
prof. Marius Nicoli
Colegiul Naţional „Fraţii Buzeşti” Craiova
mariusnicoli@yahoo.com
propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la Finala .campion 2011: cos, monoton, obstacole, echilibru1, dag, robotel, punctfix, broscute
De acelaşi autor: secvente1, raze, bile5, 235, dreptunghiuri, triunghi2, albine1, puteri35, miere, left, arbgraf, reuniune, cazare, atletism, fluviu, stele, zar1, poteci, obstacole, liste, acoperire1, minusk, efect, b2k, progresii, reconst, mijloc, romb, alune, patru, galbeni, schi1, restaurare, sort2dist
Despre backtracking: acop, bipal, magic2, vagoane, friends, tricouri, festival, numar, pento, ro, jobs, onu2, sir3, cai1, labirint, dans, ham, sudoku, caramele, linie, puncte, castel, excursia, joc7, pattern, avere, paianjen, medii, monkey, scara1, numere8, banda1, spirala1, cofetar, gradina, placa, smin, jucarii, immortal, concat, cubinvers, codif, izvor, jb, prisme, triburi1, genab, dineu, antitero, ornament, virgule
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, 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