Lista de probleme 238

Dat n, un număr natural nenul, să se determine numărul de posibilități de a-l scrie pe n ca sumă de divizori ai săi. Pentru că acest număr poate fi foarte mare, se va determina modulo 123457.

Gioni este un elev foarte pasionat de informatică și îndrăgește în special problemele care se rezolvă cu tehnica programării dinamice. El are un număr natural n și vrea să știe pentru fiecare numar i de la 1 la n câte numere cu i cifre nu sunt palindromuri. Fiindcă acest număr poate să fie foarte mare, se cere afișarea lui modulo 666013.

Se dau două șiruri de caractere, litere mici ale alfabetului englez. Să se determine lungimea celui mai lung subșir comun.

Se consideră un număr natural nenul N. Vom considera mulțimea A(N) a numerelor de N cifre nenule care au proprietatea că orice două cifre alăturate sunt de parități diferite. De exemplu 1472 este un număr din mulțimea A(4), dar 1567 nu este pentru că are cifrele alăturate 1 și 5 de aceeași paritate. Să se determine numărul de elemente ale mulțimii A(N). Pentru că acest număr poate fi foarte mare, se va determina modulo 30103.

De-a lungul principalei străzi din orașul nostru există n plopi, pentru fiecare cunoscându-se înălțimea. Primarul orașului dorește să taie anumiți plopi, astfel încât înălțimile celor rămași să fie în ordine strict descrescătoare.

Determinați numărul minim de plopi care trebuie tăiați astfel încât înălțimile celor rămași să fie în ordine strict descrescătoare.

Se dă un număr natural nenul n. Se construiește mulțimea numerelor formate din n cifre care au proprietatea că nu au două cifre alăturate care să fie prime. De exemplu 1476 este un număr corect format, dar 1537 nu este pentru că are cifrele alăturate 5 și 3 sau 3 și 7 cu proprietatea că sunt prime.
Să se determine câte numere formate din n cifre au proprietatea că nu au două cifre alăturate care să fie prime. Pentru că acest număr poate fi foarte mare, se va determina modulo 666013.

Se dă un șir de N numere întregi indexat de la 1. Să se afle suma maximă a unui subșir format din T elemente astfel încât oricare 2 elemente consecutive ale acestuia să se afle la distanță cel mult K în șirul dat (distanța dintre elementele de pe pozițiile i și j, i < j, este j - i).

Se consideră un număr natural nenul N. Să se determine numărul de cuvinte de lungime N formate doar din litere mici și cu proprietatea că nu pot exista trei litere alăturate identice. Pentru că acest număr poate fi foarte mare, se va determina modulo 777013.

După ce în problema #Plata şi-a cumpărat biscuiţi, iar în problema #Maraton şi-a făcut temele, Costy s-a hotărât să meargă în vizită la prietenul său Paul. Și pentru că Paul este prietenul său cel mai bun, bineînţeles că nu se va duce cu mâna goala. Va trece pe la magazin şi îi va cumpăra un pachet de biscuiţi. Marea problemă a eroului nostru este oraşul rău famat, la fiecare intersecţie existând pericole. Oraşul are forma de două triunghiuri dreptunghice isoscele cu un vârf comun, ca în figura următoare:

C 
X X
X X X
X X X B
      X X
      X X X
      X X X P 

C – reprezintă poziţia iniţială a lui Costy, care se va afla mereu în colţul din stânga sus.
B – reprezintă poziţia magazinului, care se va afla mereu în vârful comun al celor 2
triunghiuri.
P – reprezintă poziţia lui Paul, care se va afla mereu în colţul din dreapta jos.

Cum spuneam, la fiecare intersecţie există pericole. O intersecţie X[i][j] reprezintă intersecţia străzii orizontale i, cu strada verticală j. Gradul de periculozitate al unei intersecţii este un număr întreg X[i][j]. Definim gradul unui drum ca fiind suma gradelor intersecţiilor ce compun acel drum.

Costy poate merge de la o intersecţie X[i][j], doar la o intersecţie X[i][j + 1] (în dreapta) sau X[i + 1][j](în jos).

Spunem că un cuvânt este valid dacă el este format doar cu litere din mulțimea {a,b,c,d} și literele a și b nu sunt alăturate. De exemplu, cuvintele aaaa, acdca sunt valide, dar abbc și baabd nu sunt. Să se determine numărul cuvintelor valide de lungime n. Pentru că acest număr este foarte mare, se va afișa rezultatul modulo 777013.