Fiind date două numere naturale n şi p se cere să se găsească un număr natural m ≤ 350000 cu proprietatea că el poate fi scris atât ca sumă de p pătrate perfecte nenule, cât şi ca sumă de p+1 pătrate perfecte nenule, …, cât şi ca sumă de n pătrate perfecte nenule.

Cerinţă

Prima linie a fişierului de intrare patrate1.in conţine două numere naturale n şi p separate printr-un spaţiu, având semnificaţia de mai sus.

Date de intrare

Prima linie a fişierului de ieşire patrate1.out va conţine numărul natural m căutat.
Urmează n-p+1 linii. Linia i a fişierului, pentru i=2, 3, …, n-p+2, va conţine p+i-2 numere naturale separate prin câte un spaţiu, cu proprietatea că suma pătratelor acestora este m.

Date de ieşire

2 ≤ n ≤ 1000
2 ≤ p ≤ n
Soluţia nu este unică, se va accepta orice soluţie corectă;
Un program corect, care se încadrează în timp pentru n ≤ 30, va obţine cel puţin 30 de puncte.
Un program corect, care se încadrează în timp pentru n ≤ 150, va obţine cel puţin 70 de puncte.

Restricţii

2 ≤ n ≤ 1000
2 ≤ p ≤ n
Soluţia nu este unică, se va accepta orice soluţie corectă;
Un program corect, care se încadrează în timp pentru n ≤ 30, va obţine cel puţin 30 de puncte.
Un program corect, care se încadrează în timp pentru n ≤ 150, va obţine cel puţin 70 de puncte.

Exemple

patrate1.in	patrate1.out	Explicaţii
4 3	18 1 1 4 2 1 2 3	18 = 12+12+42 18 = 22+12+22+32

autor: Prof. Ciprian Cheşcă

propunător: Prof. Emanuela Cerchez

Liceul de Informatica ″Grigore Moisil″

emanuela.cerchez@gmail.com