Clasa a X-a
Ziua 1
Problema 3
Algebra si problemele ei
Se considera un numar natural n (2<=n<=30) si un sir de m (m?60) numere
naturale
mai mici decat n.
Se definesc trei operatii asupra a doua numere naturale a si b
(0<=a,b<n):
a*b = (a*b) mod n
a^b = (ab*ba) mod n
a+b = (a2+(a+1)2+...+b2) mod n daca b>a sau
(b2+(b+1)2+...+a2) mod n
altfel.
Operatiile * si ^ au prioritatea 1, adica se evalueaza primele, iar + are
prioritatea 2. Evaluarea se face de la stanga la dreapta.
Numim expresie un sir de caractere care contine numai operanzi (numere
naturale) si operatori dintre cei definiti mai sus. In plus, operanzii trebuie
sa fie cele m numere date in fisierul de intrare, in ordinea in care apar in
fisier.
1. Sa se afle pentru cate dintre numerele 0,1,...,n-1 exista cel putin o
expresie avand valoarea egala cu numarul respectiv.
2. Pentru numerele care indeplinesc conditia de la punctul 1. sa se determine
cate o expresie avand valoarea numarului respectiv.
Date de intrare:
Fisierul de intrare ALGEBRA.IN are urmatorul continut:
- Pe prima linie sunt scrise cele doua numere n si m despartite printr-un
spatiu.
- Pe linia urmatoare este scris sirul celor m numere naturale mai mici decat n,
despartite prin cate un spatiu..
Observatie:
Datele sunt corecte, nu necesita validare.
Date de iesire:
Rezultatele se vor scrie in fisierul text ALGEBRA.OUT sub urmatoarea
forma:
- pe prima linie se va scrie numarul k obtinut la punctul 1.;
- pe urmatoarele k linii vor fi scrise expresiile cerute la punctul 2. sub
forma:
val=expresie, unde val este valoarea expresiei (in cazul in care exista mai
multe solutii, se va furniza una singura).
Exemplu:
ALGEBRA.IN
4 6
1 2 3 1 0 3
ALGEBRA.OUT
3
0=1^2*3^1^0^3
1=1^2+3^1+0^3
2=1^2*3^1^0+3
Timp maxim de executare/test: o secunda.
Punctaj maxim: 50 puncte