criptare
Zaharel si Bronzarel se intrec adesea in criptare. De data aceasta, Zaharel a criptat un sir de N numere naturale a0, a1, ...,aN-1 astfel: a luat un numar natural M si a construit urmatorul sir: bi = ai+a(i+1) mod N+a(i+2) mod N+...+a(i+M-1) mod N; apoi, l-a intrebat pe Bronzarel daca poate sa determine sirul initial a0, a1, ..., aN-1 daca i se da acest nou sir, precum si numarul M.
Cerinta
Scrieti un program care il ajuta pe Bronzarel.
Date de intrare
Pe prima linie a fisierului de intrare criptare.in sunt scrise cele doua numere naturale N M, separate printr-un singur spatiu. Pe urmatoarea linie sunt scrise N numere naturale separate printr-un singur spatiu, reprezentand sirul b0, b1, ..., bN-1.
Date de iesire
Fisierul de iesire criptare.out va contine o singura linie pe care vor fi scrise N numere naturale separate prin cate un singur spatiu, reprezentand sirul a0, a1, ..., aN-1. Desi pot exista mai multe solutii, Bronzarel stie ca sirul criptat de Zaharel este cel minim lexicografic dintre toate solutiile posibile.
Restrictii
1 <= M, N <= 50000
0 <= bi <= 109
Prin a mod b se intelege restul
impartirii lui a la b
Se garanteaza existenta a cel putin unei solutii.
Sirul a0, a1, ...,
aN-1 trebuie sa contina numere naturale (nu neaparat
nenule).
Exemple
|
criptare.in |
criptare.out | criptare.in |
criptare.out |
| 3 2 3 5 4 |
1 2 3 |
6 4 8 13 11 13 17 10 |
2 5 0 1 7 3 |
Timp maxim de executie/test: 0.1 secunde
Mircea Paşoi
Universitatea Bucuresti, Facultatea de Matematica si Informatica
bogdanpasoi@yahoo.co