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

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


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

Numim tablou Sudoku o matrice cu nxn elemente ce conţine doar cifrele 1, 2 şi 3 astfel încât în fiecare pătrat format din 2 x 2 elemente alăturate să existe toate cele 3 cifre şi oricare două elemente alăturate pe linie sau pe coloană să fie distincte. Fiecărui tablou Sudoku i se asociază un număr obţinut prin scrierea cifrelor în ordine, începând cu prima linie.
De exemplu, tabloul Sudoku din imaginea alăturată are asociat numărul: 2132132132213211321321321.



Se defineşte şirul S(n) ca fiind un şir ordonat, format din toate tablourile Sudoku cu nxn elemente, {s1,s2,s3,…}. Pentru orice pereche ( si,sj ) din S(n) cu i<j, numărul asociat tabloului Sudoku si este strict mai mic decât numărul asociat tabloului Sudoku sj.
Pentru n=2, şirul S(2) conţine, în ordine, tablourile Sudoku:


Cerinţă

Date fiind două numere naturale n şi k să se determine:
a) numărul tablourilor Sudoku din şirul S(n);
b) tabloul Sudoku aflat pe poziţia k în şirul S(n).

Date de intrare

Fişierul sudoku1.in conţine pe prima sa linie două numere naturale n şi k separate prin câte un spaţiu.

Date de ieşire

Fişierul de ieşire sudoku1.out va conţine:
• pe prima linie un număr natural ce reprezintă numărul tablourilor Sudoku din şirul S(n);
• pe următoarele n linii se găsesc câte n cifre, separate prin câte un spaţiu, ce reprezintă, în ordine, liniile tabloului Sudoku aflat pe poziţia k în şirul S(n).

Restricţii

• 2 ≤ n ≤ 32
• 1 ≤ k <1019

Exemple

sudoku1.insudoku1.outExplicaţii
2 6 12 2 1 3 2 Şirul S(2) conţine 12 tablouri Sudoku, pe poziţia 6 în şir aflându-se tabloul:
2 1
3 2


autor: Prof. Cristina Sichim
propunător: Prof. Emanuela Cerchez
Colegiul Naţional ″Emil Racoviţă″
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la ONIGIM 2013: cursa1, patrate7, secvp, latin, swap, zmax, extraprime, greieri, onigim, divizori1, remi1, tetris3, amestec, eoliene
De acelaşi autor: ruleta2, tetris, oua, tren4, pesti, plaja, carte1, xy, porumb1, plus, covor1
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, medalion, bile6, zigzag, puncte5, intersectii, matd3, matrixdel, speed, seif1, traseu2, incadrare, betasah, zona, latin, zmax, amestec, gradina1, spider, zone, bemo, rombul, interclasare, rebus1, tabla, arrows, pseudobil, patrat1, rascoala, harta2, relatii, lasere, defrag, matcnt, ssdj, cript, ssk, teren1, fence, cifre6
Despre combinatorică: manevre, carti, bonuri, test, cub, nspecial, circuit, numere, cs, pluricex, parent, gray, siruri, anagrame, party, net, scaune, sir, monede, aztec, nrcuv2, perm, race, hanoig, red, grup, hperm, depou, grazing, pm, reteta2, playlist, young, pizza1, albine, caramele, teatru1, tub, robot1, sir23, soldati1, concurs1, comb, expresii, arbnr, cod1, munte, shgraf, desc, lex, munte1, maxperm, role, avere, vizibil, prime1, hexa, patrat, carti2, puncte2, pact, aranjari, numere5, borg, acolor, sg1, perfect, cifru2, bile4, pviz, culmi1, piramida1, trapez, frunze, sir7, logic, coduri, jetoane, kperms, tablite, secvpar, lego, permutari, binperm, multiplu1, operatii, fotbal, kbiti, jucarii, bradut, expozitie, parbit, kmax, petrecere, tango, rege, cd1, cifru3, kcons, bubblesort, hawaii, randomizare, kdist, reuniune, echipa, ghinion, cavaleri, camera616, covor, subm, grupuri, pavari, asfalt, adunscad, rotund, sport2, arbore1, lant1, module, nrperm, oneton, nrpomi, cover1, nrpal, probleme, optim, poly, vot1, flori2, xnumere, showroom, cntgcd, subsets, nkd, nrgraf, spion1, puteri, stiva1, permtr, relatii, 2sah, matcnt, magic7, nmult, roua
surse trimise | ajutor