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

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


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

Se consideră o matrice pătratică cu N linii şi N coloane ce conţine toate numerele naturale de la 1 la N*N.
Asupra matricei se definesc trei tipuri de operaţii codificate astfel:
C i j – interschimbarea coloanelor i şi j ale matricei
R i j – interschimbarea liniilor i şi j ale matricei
E i j x y – interschimbarea elementului de pe linia i şi coloana j cu elementul de pe linia x şi coloana y.
Asupra matricei se efectuează un set de M astfel de operaţii.

Cerinţă

Se cere să se determine numărul minim de aplicări complete ale acestui set de operaţii după care se ajunge din nou în starea iniţială. În cadrul setului operaţiile se efectuează mereu în aceeaşi ordine şi nu se poate sări peste o operaţie. Deoarece numărul acesta poate fi foarte mare se cere restul împărţirii sale la 13007.

Date de intrare

Fişierul perspic.in conţine pe prima linie numerele naturale N M, separate printr-un spaţiu, reprezentând dimensiunea matricei şi respectiv numărul de operaţii dintr-un set. Pe următoarele M linii se descriu operaţiile setului.

Date de ieşire

Fişierul perspic.out va conţine restul împărţirii la 13007 al numărului minim determinat.

Restricţii

1 ≤ N ≤ 100
1 ≤ M ≤ 10000

Pentru 60% din teste numărul minim de aplicări ale setului de operaţii necesare va fi mai mic ca 2000000000.

Exemple

perspic.inperspic.outExplicaţii
2 2 C 1 2 R 1 2 2 Matricea iniţială:
1 2
3 4

Matricea după prima operaţie:
2 1
4 3

Matricea după a doua operaţie(terminarea primului set):
4 3
2 1

Matricea după a treia operaţie:
3 4
1 2

Matricea după a patra operaţie(terminarea celui de al doilea set):
1 2
3 4

autor: Stud. Adrian Diaconu
propunător: Prof. Emanuela Cerchez
Liceul de Informatica ″Grigore Moisil″
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la ONI 2009: bile, checkin, numere, text, reactii, volei, magic2, sirag, taste, tetris, origami, rafturi, joc2, br, reinvent, tir, patrate2, nrcuv2, matrice, patrate1, pikachu, taxe, cartonas, case, desen2
De acelaşi autor: nrbun2, nrbun, siruri, ture, toys, secv, arb, sir1, mexc, pviz
Despre divizibilitate: celule, cai, trei, ruleta, an, factori, perechi, anagrame, axa, scara, programs, iepuras2, fry, policefm, turist, kfactor, cuc, prime, sqr, evaluare, factk, div3, divizor, euclid, stop, matricea, mutare, viteza, ingerasi, prieteni, robinson, romeo, perechi1, sume1, fact, tzigla, cifru2, elfi, vraji, desen2, exponent, trapez, resturi, exp1, ron, spirala1, gardul, tort, poligon3, sume2, smith, biliard, printesa, secvente1, ultime4, padure, multiplu1, 235, iepurasi, numar3, cmmmc, randomizare, divizori, pitag, bileprime, pin, canguri, numar4, jocprim, covor, nivfractie, cmmdcsecv, ai, grupe2, numerus, sport2, fagure, grad2, sumdivprod, oak, sumprod, paisprezece, numere10, proddiv, puncte4, trifoi, cartier, alune, intersectii, divider, minm, numere11, prodnr, boltz, vistiernic, secvp, extraprime, divizori1, cumpanit, cntgcd, nrdiv, numere12, daruri, imprimanta, puteri, reflex, tg, sprime, diferenta, concurs4, vapoare, inventie, prime2
Despre matrice: vopsea, harta, opmat, sarpe, light, magic2, tetris, origami, concurs, iepuras, tribile, criptmat, cutie, patrate, 3d, pajura, 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, tabla, arrows, pseudobil, patrat1, rascoala, harta2, relatii, lasere, defrag, matcnt, ssdj, cript, ssk, teren1, fence, cifre6
Chestionare recomandate
surse trimise | ajutor