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

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


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

Se dă o matrice cu n linii şi n coloane. Coloanele şi liniile sunt etichetate cu numere de la 1 la 2n, folosind fiecare număr câte o singură dată (fig. 1 – exemplu pentru n=3). Vom nota şirul etichetelor asociat liniilor matricei o1,o2,...,on, iar şirul etichetelor asociat coloanelor matricei cu v1,v2,...,vn (fig. 4).
Trebuie să se completeze fiecare element al matricei cu una dintre cifrele 1 sau 9 (fig. 2). Prin concatenarea cifrelor de pe o linie sau o coloană obţinem un număr de n cifre. În total se obţin 2n numere. Aceste numere trebuie să fie distincte două câte două şi aranjându-le în ordinea etichetelor asociate liniilor şi coloanelor trebuie să fie în ordine crescătoare (fig. 3). Vom concatena cele 2n numere în ordinea etichetelor şi obţinem un singur număr de 2n2 cifre. Acest număr îl vom denumi cheie magică. Pentru exemplul din fig. 3 obţinem cheia magică




Cerinţă

Se dau x un număr natural, dimensiunea n a matricei şi cele două şiruri de etichete o1,o2,...,on respectiv v1,v2,...,vn. Să se tipărească numărul de chei magice distincte (dacă x=1) sau cea mai mică cheie magică ce se poate asocia matricei (dacă x=2).

Date de intrare

Fişierul de intrare magic2.in conţine patru linii. Pe prima linie se află numărul natural x (1 sau 2). Pe a doua linie se află numărul natural n. Pe a treia linie se află n numere naturale distincte separate prin câte un spaţiu reprezentând şirul o1,o2,...,on iar pe linia a patra n numere naturale distincte separate prin câte un spaţiu reprezentând şirul v1,v2,...,vn.

Date de ieşire

Fişierul de ieşire magic2.out va conţine o singură linie pe care va fi scris un număr natural care reprezintă:
- dacă x=1, numărul cheilor magice distincte;
- dacă x=2, cea mai mică cheie magică.

Restricţii

3 <= n <= 5
Pentru fiecare fişier test există cel puţin o soluţie.
Pentru 50% dintre teste x=1 (aflarea numărului de chei magice), iar pentru 50% x=2 (aflarea celei mai mici chei magice)
Pentru 20% dintre teste n=3, 30% dintre teste n=4 şi pentru 50% dintre teste n=5.

Exemple

magic2.inmagic2.outExplicaţii
1 3 2 4 6 3 5 1 2 Avem două soluţii
1 9 1
9 1 1
9 9 1

1 9 1
9 1 1
9 9 9

Numerele obţinute în ordinea etichetărilor:
(111, 191, 199, 911, 919, 991) respectiv
(119, 191, 199, 911, 919, 999).
Cele două chei magice sunt 111191199911919991 respectiv 119191199911919999, dintre care prima e mai mică.
2 3 2 4 6 3 5 1 111191199911919991

autor: Prof. Zoltan Szabo
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, sirag, taste, tetris, origami, rafturi, joc2, br, reinvent, perspic, tir, patrate2, nrcuv2, matrice, patrate1, pikachu, taxe, cartonas, case, desen2
De acelaşi autor: balanta, bonuri, cub, magic, munte, euclid, banda, biliard, fractie1, fotbal, arctir, orientare, rege, fibo1, piatra, war, aritm, ssmax, sirmax, ikebana, punctfix, domino2, lant1, parc1, cubulete, biperm, triunghi6, stiva1
Despre backtracking: acop, bipal, vagoane, friends, tricouri, festival, numar, pento, ro, jobs, onu2, sir3, cai1, labirint, dans, ham, sudoku, caramele, linie, puncte, castel, excursia, joc7, pattern, avere, paianjen, medii, monkey, scara1, numere8, banda1, spirala1, cofetar, gradina, placa, smin, jucarii, immortal, concat, cubinvers, codif, izvor, avioane, jb, prisme, triburi1, genab, dineu, antitero, ornament, virgule
Despre matrice: vopsea, harta, opmat, sarpe, light, 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, tabla, arrows, pseudobil, patrat1, rascoala, harta2, relatii, lasere, defrag, matcnt, ssdj, cript, ssk, teren1, fence, cifre6
surse trimise | ajutor