Lista de probleme 2

Regele Rufus dorește să stabilească moștenitorul averii sale, adică să ofere parola de la seif celui mai deștept dintre fiii săi. Inițial, regele a avut parola X formată din N cifre nenule și un cod cheie Q (număr natural cu exact nouă cifre, distincte, toate nenule). În fiecare an din cei K ani de domnie, folosind codul cheie Q, Rufus a modificat câte o secvență de cifre din parolă ajungând la parola finală P.Pentru fiecare secvență se cunoaște poziția S a primei cifre din secvență și poziția D a ultimei cifre din secvență. Astfel, secvența este formată din cifrele situate pe pozițiile S, S+1, S+2,…, D în parola X.

Modificarea unei secvențe din X constă în înlocuirea fiecărei apariții a cifrei 1 cu prima cifră a lui Q, apoi a fiecărei apariții a cifrei 2 cu a doua cifră a lui Q,…, a fiecărei apariții a cifrei 9 cu ultima cifră a lui Q.

Pentru a decide moștenitorul, regele le dă fiilor parola finală P, codul cheie Q, numărul K de ani de domnie și cele K secvențe de cifre care au fost modificate și le cere să găsească: parola inițială X, poziția minimă Z din parola X care a apărut în cele mai multe secvențe dintre cele modificate de rege de-a lungul celor K ani de domnie și cifrele distincte care au ocupat poziția Z în cei K ani.

Scrieți un program care citește numerele Q, N, K, cele N cifre ale parolei finale P și cele K perechi de poziții S și D, și care rezolvă următoarele două cerințe:

1. determină parola inițială X;
2. determină poziția minimă Z și cifrele distincte care au ocupat această poziție în cei K ani de domnie.

Fie k, n și y trei numere naturale. Fie X un șir format din n numere naturale: \( x_1, x_2, x_3, …, x_n \). Fie P produsul numerelor \( y, x_1, x_2, x_3, …, x_n \), adică \( P = y\times x_1\times x_2 \times x_3 \times … \times x_n \). Numărul P este o “k-putere” dacă există un număr natural z astfel încât \( P=z^k \).

Scrieți un program care să citească numerele \( k, n, x_1, x_2, x_3, …, x_n \) și care să determine:

• 1. cel mai mic și cel mai mare număr din șirul X ce sunt formate doar din cifre identice;
• 2. descompunerea în factori primi a celui mai mic număr natural y (y ≥ 2) cu proprietatea că numărul \( P = y\times x_1\times x_2 \times x_3 \times … \times x_n \) este o “k-putere”.