Lista de probleme 46

Se citesc numerele naturale n şi k şi cifrele nenule distincte c[1], c[2], …, c[n]. Să se determine câte numere de k cifre formate doar cu cifrele c[1], c[2], …, c[n] sunt divizibile cu 9. Pentru că acest număr poate fi foarte mare, rezultatul se va determina modulo 666013.

Considerăm trei numere naturale nenule: n, k şi x. Denumim o kx-descompunere a numărului n o posibilitate de a scrie numărul n ca sumă de k numere naturale nenule astfel încât diferenţa între oricare doi termeni ai sumei este cel puţin egală cu x. Fiind date trei numere naturale n, k şi x, să se determine câte kx-descompuneri distincte există. Două kx-descompuneri sunt distincte dacă diferă prin cel puţin un termen.

Se consideră numerele naturale N şi K şi cifrele nenule distincte c[1], c[2], …, c[N]. Să se determine câte numere de K cifre formate doar cu cifrele c[1], c[2], …, c[N] sunt divizibile cu 3. Pentru că acest număr poate fi foarte mare, rezultatul se va determina modulo 4001.

D şi S se pregătesc pentru primul lor concurs de dans şi ei lucreaza momentan la coregrafia de tango. Chiar dacă va fi primul lor concurs, ei deja ştiu n figuri de dans şi au calculat pentru fiecare dintre aceste figuri câţi timpi muzicali durează. Fiindcă le place foarte mult să danseze împreună, ei vor să pregătească o coregrafie frumoasă pentru o piesă care durează exact k timpi muzicali.

Se dau două numere naturale N şi K. Determinaţi numărul de şiruri de lungime N formate doar din semnele + şi – şi în care nu apar K semne – pe poziţii consecutive.

Se dă un dreptunghi cu lungimea egală cu 2N centimetri și lățimea egală cu 3 centimetri. Să se determine numărul M al pavărilor distincte cu dale dreptunghiulare care au lungimea egală cu un centimetru și lățimea egală cu 2 centimetri.

Toată lumea cunoaște modelul de deblocare a telefoanelor sub formă de o matrice cu 3 linii și 3 coloane. Se pot trasa diferite modele de deblocare având un număr N de puncte prin care trecem, din fiecare punct putând merge la oricare vecin al lui. (Sunt maximum 8 vecini de exemplu pentru punctul din mijloc și 3 vecini pentru un punct din colț).

Determinați câte variante de modele sunt posibile trecând prin N puncte. Deoarece numărul poate fi foarte mare, se va afișa numărul de variante modulo 1000003.

Avem un coridor lung de lățime k și lungime n. Avem sarcina de a-l acoperi cu bucăți de gresii de dimensiuni 1 x k, 2 x k și 3 x k. Calculați în câte moduri distincte se poate acoperi coridorul cu cele 3 tipuri de gresii. Pentru că rezultatul este un număr mare, se cere restul împărțirii la 1.000.000.007.

Să se calculeze numărul de șiruri crescătoare de lungime n, cu numere de la 1 la m, în care fiecare element apare de cel mult k ori.

Se da un vector cu n numere naturale, unde v[i] reprezintă numărul de valori egale cu i.

Să se afle numărul de submulțimi a căror sumă este multiplu de n.