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

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


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

Monedele vechi aveau imprimate pe una dintre feţe figura regelui ("cap"), iar pe cealaltă un însemn al ţării care a emis moneda ("pajura").
Atunci când arbitrul cere căpitanilor de echipă să aleagă jumătatea de teren pe care vor începe jocul, el aruncă în aer o monedă. Aceasta cade pe pământ cu una dintre feţe în sus, "capul" sau "pajura". Căpitanul de echipă care a ales faţa de sus este cel care alege terenul.
Să presupunem că, în urma aruncării în sus a mai multor monede, acestea cad pe pământ într-o configuraţie de nxm monede (adica sub forma unei matrice cu n linii si m coloane), unele având "capul" pe faţa de sus, altele având "pajura". Arbitrul nostru, iubitor de probleme, doreşte să obţină toate monedele cu pajura în sus. Pentru aceasta el restricţionează operaţiile posibile doar la două:
- o întreagă linie este "inversată";
- o întreagă coloană este "inversată".
Prin "inversarea" unei linii/coloane fiecare monedă de pe linia/coloana respectivă este inversată.

Cerinţă
Date dimensiunile configuraţiei n şi m, precum şi configuraţia monedelor, să se determine dacă, folosind numai cele două operaţii permise, se poate transforma configuraţia iniţială astfel încât, la final, toate monedele să fie cu "pajura" în sus.

Date de intrare
Fişierul de intrare pajura.in conţine mai multe seturi de date. Un set de date conţine pe prima linie valorile n şi m separate printr-un spaţiu. Următoarele n linii din setul de date conţin câte m caractere C sau P, fără spaţii între ele, reprezentând configuraţia iniţială a monedelor. Seturile de date se termină cu două valori 0 separate printr-un spaţiu.

Date de ieşire
Dacă în fişierul de intrare au fost k seturi de date, atunci fişierul de ieşire pajura.out va avea k linii, pe fiecare linie fiind scrisă una dintre valorile 1 sau 0, după cum configuraţia iniţială poate fi transformată sau nu.

Restricţii şi precizări
1 <= n, m <= 1000
Numarul de seturi de date din orice fisier de intrare este <=10.

Exemplu

pajura.in pajura.out Explicatii

3 4
CPCC
PCPP
CPCC
5 2
PC
CC
CP
CC
CC
0 0

1
0
Fişierul de intrare conţine 2 seturi de date.
Pentru primul set de date o posibilă succesiune de operaţii este:

CPCC  coloana 2 CCCC   linia 1   PPPP    linia 3  PPPP
PCPP ---------> PPPP ----------> PPPP ----------> PPPP
CPCC            CCCC             CCCC             PPPP

Pentru cel de-al doilea set de date, nici o succesiune de operaţii nu conduce la un rezultat favorabil.

prof. Marinel Şerban
Liceul de Informatică "Gr. C. Moisil" Iaşi
m
arinel_serban@yahoo.com

propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la .campion 2007: perechi, teanc, index, light, copaci, teren, pizza, grupe, cod, ecran, drum, soldati, factura, palma, decript, lbd, aven, cs, h, trenuri, sort, spam, complex, parent, holo, tren2, gray, siruri, arce, pasi, cifre, mgo, firma, joc, cartonase, vikingi, anagrame, balbe, vecini, balaur, tribile, conflicte, criptmat, mesaj, maxim, magic3, desen, plimbare, cutie, patrate, party, vagoane, robot, astre, trains, numere2, friends, tricouri, furtuna, net, baby, scaune, 3d, axa, bile2, vmem, pahare, termen, sablon, zapada, cuvinte, excursie, hd, pc, sir, cadere, pioni
De acelaşi autor: premii, finala, fractii, trei, manevre, nrcuv, an, vopsea, opmat, tramvai, bipal, kpal, sarpe, replace, factori, barca, perechi, grupe, cod, reactii, factura, decript, trenuri, holo, cifre, firma, tribile, mesaj, tricouri, monede, programs, fry, repeat, red, pavaj, bacan, nrbinar, invest, cutie2, loc, depou, nr3, zid, felinare, sir3, sqr, carte, labirint, stea, count, evaluare, super, schimb, zaruri, vectori, spirala, desen1, rima, ceas1, romane, sms, bac, excursia, joc7, furnici, munte1, cezar, marcare, excursie1, culmi, sume1, schi, nr4, fractie, cod3, medii, tren3, top, sant1, imagine, ocr, perfect, pluton, reforma, alee, ceas2, paritate, borcane, aranjare, comoara1, culmi1, reactivi, submult, sablon1, sir8, sume2, dansatori, smith, tom, matriosca, asociativ, control1, calorii, immortal, concat, mat, cubinvers, mine, divizori, cheie, stelar, joct, minmax, cladire, adunscad, razboi, ore, oras1, sumprod, prisme, operatii1, lgdrum, unupatru, chibrituri, extraprime, prieten, rebus1, grindina, opmult, betisoare, antitero, clase, pagini, ornament, ordine, spioni1
Despre matrice: vopsea, harta, opmat, sarpe, light, magic2, tetris, origami, concurs, iepuras, tribile, criptmat, cutie, patrate, 3d, 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, 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