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

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


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

Un mare împărat chinez a ajuns la un număr impresionant de victorii, notat cu m. Pentru a cinsti cum se cuvine acest eveniment ordonă consilierului său fabricarea unui covor lung de k metri şi lat de 2 metri pe care să-l pună de la intrarea în cetate până la intrarea în castel. Pentru că împăratul este un împătimit al calculelor matematice doreşte ca acest covor să fie alcătuit din pătrăţele de latură 1 metru, având diferite culori. Pentru k=10 covorul are forma:

Culorile sunt codificate cu diverse numere naturale şi trebuie să fie alese astfel încât să cinstească victoriile împăratului, adică numerele folosite la codificarea culorilor pătratelor de pe aceeaşi coloană trebuie să aibă cel mai mic multiplu comun egal cu m şi nu trebuie să existe două coloane colorate la fel.
Dacă notăm cu a1, a2, ..., ak codurile culorilor de pe linia de sus, respectiv cu b1, b2, ..., bk codurile culorilor de pe linia de jos a covorului, atunci condiţiile de mai sus se pot scrie astfel:

  • pentru i=1,2,...,k, cel mai mic multiplu comun pentru ai şi bi este m;
  • pentru i<j, i,j=1,2,…,k, (ai,bi)≠(aj,bj 

Covorul pus de la intrarea în cetate până la castel trebuie să fie mereu curat şi de aceea se doreşte fabricarea unui număr cât mai mare de covoare diferite care să respecte condiţiile împăratului.
Două covoare sunt considerate diferite dacă există o poziţie (i, j) (1≤i≤2 şi 1≤j≤k) astfel încât culoarea pătratului de pe linia i şi coloana j în primul covor este diferită de culoarea pătratului de pe linia i şi culoarea j în al doilea covor.

Cerinţă

Să se scrie un program care, cunoscând m şi k, determină numărul maxim de covoare diferite care pot fi fabricate în condiţiile din enunţ.

Date de intrare

Fişierul de intrare covor.in conţine pe prima linie numerele naturale m şi k separate printr-un spaţiu.

Date de ieşire

Fişierul de ieşire covor.out va conţine o singură linie  pe care va fi scris numărul maxim de covoare diferite ce se pot fabrica, modulo 9901.

Restricţii

  • 1 ≤ m,k ≤ 2000000000
  • Pentru codificarea culorilor se poate folosi orice număr natural.
  • p modulo h reprezintă restul împărţirii lui p la h.
Exemple
covor.in covor.out Explicaţie
6 4 3024

Iată 4 covoare dintre cele posibile:

În fiecare pătrăţel este scris codul unei culori.


prof. Doru Popescu Anastasiu
C.N. "Radu Greceanu", Slatina
dopopan@yahoo.com
propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la .campion 2010: greiere, divizori, kdist, pestera, partitie, sokoban, pitag, porumb, cheie, conferinta, chei, stelar, atelier, secv9, ny, radical, arbgraf, select, divk, bileprime, nx, reuniune, cazare, proiect, taler, atletism, echipa, ghinion, oldest, war, aliniere, sumb, cavaleri, joct, fluviu, camera616, aritm, stele, subm, mess, secvnumber, cladire, ssmax, parcela, pion, subs, universitate, el, mahjong, rotund, sirmax, bdotcom, pack
De acelaşi autor: degrade, hora, noroc, test, tren, grad, palma, cs, h, vagoane, scaune, tir, nrcuv2, piata, vocale, prop, poligon, text2, onu2, creioane, exp, donald, young, albine, turn, linie, tub, suma1, triunghi, cod1, pic, zuzu, pav, prieteni1, banda10, numar2, prime1, ziduri, puncte2, texan, part, ucif, numere7, mare, furnica, pavare, cifre3, domino, exp1, coduri, efort, prodmax, char, dartz, operatii, jucarii, cd1, codif, bileprime, echipa, pavari, parcela, grad1, ec, stalpi2, grad2, testament, nrpomi, elicop, triburi1, showroom, cartite
Despre divizibilitate: celule, cai, trei, ruleta, an, factori, perechi, anagrame, axa, perspic, 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, 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 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, 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, matcnt, magic7, nmult, roua
Chestionare recomandate
surse trimise | ajutor