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

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


Timp maxim de executie/test:
0.2 secunde
Memorie totala disponibila/stiva:
16 MB/1 MB

Tabla de joc a unui foarte popular joc de pe Internet consta dintr-o zona dreptunghiulara de pe ecran, zona impartita in celule, organizate in M linii si N coloane. Liniile sunt numerotate de la 1 la M, incepand de la linia de sus, iar coloanele sunt numerotate de la 1 la N incepand de la coloana din stanga.
Fiecare celula contine o piesa de o anumita culoare. Culorile sunt codificate prin litere mare ale alfabetului englez.

Scopul jocului este de a obtine grupuri de cel putin 3 piese de aceeasi culoare. Un grup este format din cel putin trei piese de aceeasi culoare aflate in celule alaturate situate pe o aceeasi linie sau situate pe o aceeasi coloana. In figura urmatoare piesele de culoare R formeaza un grup de 4 piese, piesele de culoare V formeaza un grup de 3 piese, insa piesele de culoare A NU formeaza un grup:

T
B
C
C
E
F
G
H
V
N
R
R
R
R
U
P
V
X
A
B
C
D
E
L
V
A
A
M
N
U
P
T

In scopul crearii grupurilor de piese sunt permise doua tipuri de mutari si anume:
1. Se selecteaza o linie a tablei si se permuta circular spre dreapta cu un anumit numar de pozitii, bilele care "ies" prin partea din dreapta a tablei fiind mutate la inceputul liniei. De exemplu pentru urmatoarea configuratie a tablei:
ABAD
BADC
ABCD
permutarea liniei a doua cu o pozitie la dreapta conduce la configuratia:
ABAD
CBAD
ABCD

si astfel s-au format doua grupuri de cate trei piese (una pe coloana a doua si una pe coloana a patra)
2. Asemanator se poate selecteaza o coloana a tablei care se permuta circular in jos cu un anumit numar de pozitii, piesele ce "ies" prin partea de jos a tablei fiind mutate la inceputul coloanei respective.
O mutare este permisa doar daca in urma ei se formeaza cel putin un grup de piese care vor fi eliminate.
Doua mutari sunt diferite daca nu implica aceeasi linie sau aceeasi coloana, sau in cazul in care implica aceeasi linie sau aceeasi coloana, difera numarul de pozitii permutate circular la cele doua mutari.

Cerinta

a) Sa se determine numarul de posibilitati de a realiza prima mutare pentru o tabla de joc data.
b) Sa se determine numarul maxim de piese ce se pot elimina in urma primei mutari, numar ce este egal cu suma numarului de piese din toate grupurile ce se formeaza in urma mutarii respective.
c) Sa se determine prima mutare ce trebuie sa fie executata, astfel incat numarul de piese ce se pot elimina sa fie maxim posibil. Daca exista mai multe solutii, este preferata cea care executa permutarea unei linii. Daca si in acest caz exista mai multe solutii se alege varianta cu indicele de linie minim, iar pentru aceeasi linie, cea cu numarul de pozitii pe care se executa permutarea minim.

Date de intrare

Pe prima linie a fisierului de intrare game.in sunt scrise doua numere naturale M si N, separate printr-un singur spatiu, reprezentand numarul de linii si de coloane ale tablei de joc. Fiecare dintre urmatoarele M linii contine cate N litere mari ale alfabetului englez, reprezentand culorile pieselor de pe tabla de joc.

Date de iesire

Prima linie a fisierului game.out va contine un singur numar natural reprezentand numarul de posibilitati de a realiza prima mutare. Linia a doua a fisierului va contine un singur numar natural reprezentand numarul maxim de piese ce se pot elimina in urma efectuarii primei mutari. Pe linia a treia se scrie o mutare care duce la eliminarea unui numar maxim de piese de pe tabla de joc. O mutare este codificata prin trei numere naturale x, y, z separate prin cate un spatiu avand urmatoarele semnificatii:
- x are valoarea 1 daca se permuta o linie, respectiv 2 daca se permuta o coloana;
- y reprezinta numarul de ordine al liniei sau al coloanei care se permuta;
- z reprezinta numarul de pozitii cu care se face permutarea circulara.

Restrictii

  • 3 <= M, N <= 50
  • Pentru toate datele de test va exista cel putin o mutare posibila.
  • Initial tabla nu contine grupuri.
  • 1<=z<=N-1.

Exemplu

game.in game.out game.in game.out
3 4
DBAD
AADA
DBCA
4
6
1 2 2
3 4
ABAD
BADC
ABCA
3
3
1 2 1

prof. Popescu Carmen
Colegiul National "Gheorghe Lazar" Sibiu
Contact: carmen_cngl@yahoo.com

propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Probleme recomandate
De la .campion 2005: cuc, prime, radio, text2, honest, police, comori, patrate3, fisc, ref, pcod, zmeu, loc, nr01, scor2, judete, strict, convert, bile3, cod2, depou, auto2, tree, cat, nr3, chimie2, compress, jobs, leaves, zid, politics, onu2, ploaia, grazing, pstring, cartonase2, exp, cartoane, sir3, program, scoici, playlist, sqr, cai1, farfurii, joc1, trafic, carte, set, barbie, labirint, firma1, vile, donald, ambigram, dans, albinuta, rlcs, stea, submatrix, cub1, ham, sponsori, young, jokes, pizza1, albine, lot, atac1, monede1, count, exam, herbert, sudoku, bio, metro
De acelaşi autor: light, sort, iepuras, pahare, turist, arthur, pento, cod2, ambigram, jokes, trecere, paianjen, zumzi, cifru3, pamant, pixy, triburi, culori1, cifre5, arc
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, 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, arrows, pseudobil, patrat1, rascoala, harta2, relatii, lasere, defrag, matcnt, ssdj, cript, ssk, teren1, fence, cifre6
surse trimise | ajutor