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

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


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

Avem o placă pătrată cu latura de N unităţi (N - par). Ea este împărţită în N*N pătrate cu latura 1. De pe al doilea şi penultimul rând lipsesc cele două pătrate de la mijloc. De pe al treilea şi antepenultimul rând lipsesc cele 4 pătrate din mijloc, şi aşa mai departe. Iată cum arată placa de dimensiune 8 (pătratele marcate cu x lipsesc).

Cerinţă

Dorim să plasăm în pătratele rămase cât mai multe dominouri de dimensiuni 2X1 (sau 1X2, adică dominourile pot fi rotite).

Date de intrare

Fişierul de intrare romb.in are pe prima linie un singur număr natural N, dimensiunea plăcii.

Date de ieşire

Pe prima linie a fişierului romb.out se va găsi un singur număr M care reprezintă numărul maxim de dominouri ce pot fi plasate pe placă. Pe fiecare dintre următoarele N linii se găsesc câte N numere naturale, separate prin câte un spaţiu, reprezentând configuraţia plăcii acoperite. În pătratele lipsă se va scrie -1. În pătratele rămase neacoperite se va scrie 0. În pătratele ocupate de dominoul plasat primul se va scrie 1, în cele ocupate de dominoul plasat al doilea se va scrie 2, şi asa mai departe până la scrierea valorii M (în pătratele ocupate de ultimul domino plasat).

Restricţii

  • 4 <= N <= 200, N par
  • Dominourile nu se pot suprapune parţial sau total
  • Dominourile trebuie plasate strict în interiorul plăcii
  • Este acceptată orice configuraţie corectă
  • Pentru afişarea corectă doar a numărului maxim de dominouri se acordă 20% din punctaj

Exemplu

romb.in romb.out
4

6
1 1 2 2
3 -1 -1 4
3 -1 -1 4
5 5 6 6

prof. Marius Nicoli
Colegiul Naţional „Fraţii Buzeşti” Craiova
mariusnicoli@yahoo.com
propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Probleme recomandate
De la .campion 2011: ore, pegals, valet, xpn, efect, nrperm, b2k, sumdivprod, nr0, maxviz, oneton, oras1, ksecv, ripstick, antic, oak, nor, nrpomi, sumprod, paisprezece, cover1, prisme, gxor, progresii, anagramabil, zuma, nrpal, sdmin, lista, operatii1, codarb, codpatrat, adprod, puncte4, qtri, reconst, gsm, subsiruri, mijloc, trifoi, cubulete, maxbin, albine2, probleme, triburi1, megascoala
De acelaşi autor: secvente1, raze, bile5, 235, dreptunghiuri, triunghi2, albine1, puteri35, miere, left, arbgraf, reuniune, cazare, atletism, fluviu, stele, zar1, poteci, avioane, obstacole, liste, acoperire1, minusk, efect, b2k, progresii, reconst, mijloc, alune, patru, galbeni, schi1, restaurare, sort2dist
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, 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