ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
|
.campion
| matcnt |
|
Timp maxim de execuţie/test: |
0.2 secunde |
|
Memorie totală disponibilă/stivă: |
64 MB/8 MB |
|
Considerăm matricele pătratice cu N linii şi N coloane care memorează numai valori 0 şi 1 şi care îndeplinesc următoarele condiţii:
- au pe fiecare linie exact două valori egale cu 1;
- au pe fiecare coloană exact două valori egale cu 1;
- nu există în matrice patru valori de 1 care să fie colţurile unei submatrice.
În exemplele de mai jos, prima matrice îndeplineşte cele trei condiţii, dar a doua matrice nu satisface condiţia a treia:
| 1 |
0 |
1 |
0 |
|
1 |
0 |
0 |
1 |
| 1 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
| 0 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
| 0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
Cerinţă
Să se determine numărul acestor matrice. Pentru că acest număr poate fi foarte mare, se va afişa rezultatul modulo 200003.
Date de intrare
Fişierul de intrare ssdj.in conţine pe prima linie numărul natural N.
Date de ieşire
Fişierul de ieşire ssdj.out va conţine pe prima linie un număr natural reprezentând numărul matricelor, modulo 200003.
Restricţii
- 3 <= N <= 100 000
- Pentru 30% din teste, N <= 50
- Pentru alte 30% din teste, N <= 1000
Exemplu
| matcnt.in |
matcnt.out |
Explicaţii |
|
3 |
6
|
Cele 6 matrice sunt:
|
011
101
110 |
011
110
101 |
101
011
110 |
101
110
011 |
110
011
101 |
110
101
011 |
|
|
Articole recomandate
Probleme recomandate
| De acelaşi autor: | cai, rebus, harta, comun, axa, sir, ocean14, reduceri, div3, patrate6, vot, reziduu, accesibil, predecesor, permutari, scanduri, ordonare, xor1, paltrei, triunghi1, 123, traseu1, parbit, petrecere, secvbiti, subm, triunghi3, cmmdcsecv, drumuri1, fillmat, secvb, siruri3, acces, segmente, echilibru1, broscute, ksecv, paisprezece, proddiv, perechi2, expeval, maxtri, combcuv, dfs, qtri, blis, maxbin, probleme, divider, eliminare, minm, genab, grafxy, matd3, azeval, matrixdel, speed, maxp, split, binremove, sminus, subsets, tcif, sprime, sir2dif, ecp, arbsum, robotzi, permtr, unudoi, ssdj, dominant | | 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, sudoku1, gradina1, spider, zone, bemo, rombul, interclasare, rebus1, tabla, arrows, pseudobil, patrat1, rascoala, harta2, relatii, lasere, defrag, 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, sudoku1, flori2, xnumere, showroom, cntgcd, subsets, nkd, nrgraf, spion1, puteri, stiva1, permtr, relatii, 2sah, magic7, nmult, roua | | Despre recurenţă: | nrbun2, nrbun, grupe, palind, siruri, vecini, net, pioni, sir2, perm, red, sume3, pavaj, div3, descfib, robot1, soldati1, expresii, agitatie, aparitii, apel, randuri, zidar, log, maxq, cover, dist, munte1, sir1, vizibil, csir, puncte2, aranjari, numere5, anticip, bsir, evantai, sg1, zumzi, lant, perfect, cifru2, numere8, poarta, pviz, poli, desert, echitabil, patrate6, kperms, jump, petrecere, rege, triunghi3, sir9, arbore1, fibgcd, cds, wg, module, nr0, cover1, culori1, flori2, cntgcd, 2sah, nmult |
|