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

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


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

O tablă de şah de dimensiune nxn conţine pe toate pătrăţelele câte o piesă cu una dintre culorile: alb, negru, roşu, verde sau albastru. Pe tablă nu există 3 piese consecutive de aceeaşi culoare situate pe aceeaşi linie sau coloană.
O mutare presupune interschimbarea a două piese alăturate, fie pe o linie, fie pe o coloană. După mutare se acordă punctaj dacă se obţin următoarele situaţii şi nu numai:
• 3 piese de aceeaşi culoare consecutive pe o linie sau o coloană = 1 punct;
• 3 piese de aceeaşi culoare consecutive pe o linie şi o coloană = 5 puncte;
La orice situaţie de mai sus, o piesă în plus de aceeaşi culoare mai contribuie cu încă 1 la punctaj. De exemplu, 4 piese de aceeaşi culoare consecutive pe o linie sau o coloană = 2 puncte.
Punctajele obţinute de piesele interschimbate se adună.
Punctajul este 0 dacă nu se obţin măcar 3 piese consecutive de aceeaşi culoare.

Cerinţă

Găsiţi cel mai mare punctaj obţinut în urma unei singure mutări.

Date de intrare

Fişierul de intrare tabla.in conţine, pe prima linie, numărul natural n, ce reprezintă dimensiunea tablei. Pe fiecare dintre următoarele n linii se află câte n valori separate prin spaţii. Valorile posibile pot fi: 1, 2, 3, 4 şi 5. Valoarea 1 reprezintă piesa de culoare albă, 2 piesa de culoare neagră etc.

Date de ieşire

Fişierul de ieşire tabla.out va conţine o singură linie pe care va fi scris cel mai mare punctaj obţinut.

Restricţii

3 <= n <= 20

Exemple

tabla.intabla.outExplicaţii
3 1 1 2 2 2 1 3 4 5 2 prin interschimbarea elementului (1,3) cu (2,3) se obţine:
1 1 1
2 2 2
3 4 5
şi am 1 punct din prima linie şi 1 punct din a doua linie
6 1 2 4 2 1 5 1 2 4 2 4 4 4 4 3 4 4 1 3 3 4 3 3 5 1 1 3 1 1 2 1 1 3 1 1 2 14 prin interschimbarea elementului (3,3) cu (4,3) se obtine:
1 2 4 2 1 5
1 2 4 2 4 4
4 4 4 4 4 1
3 3 3 3 3 5
1 1 3 1 1 2
1 1 3 1 1 2
şi am 7 (5+2) puncte de la piesele codificate cu 4 şi 7 puncte de la piesele codificate cu 3.

autor: Prof. Constantin Creţu
propunător: Prof. Emanuela Cerchez
Colegiul Naţional ″Emil Racoviţă″
emanuela.cerchez@gmail.com
Probleme recomandate
De la OMI Iaşi 2014: prize, conturi, colina, nrdiv, doitrei, rebus1, cristal, grindina, foto, numere12, daruri
De acelaşi autor: meteo, siruri2, cuvinte2, subtitrare, diferenta, cifre6
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, arrows, pseudobil, patrat1, rascoala, harta2, relatii, lasere, defrag, matcnt, ssdj, cript, ssk, teren1, fence, cifre6
surse trimise | ajutor