== include(page="template/taskheader" task_id="pitagora") ==
Poveste şi cerinţă...
Să considerăm un dreptunghi în plan cu laturile $a$ şi $b$. Conform teoremei lui Pitagora lungimea diagonalei d respectă relaţia $d^2^ = a^2^ + b^2^$. Lungimile laturilor $a$ şi $b$ pot fi alese din mulţimea numerelor naturale astfel încât lungimea diagonolei să fie tot un număr natural. De exemplu pentru un dreptunghi cu laturile $5$ şi $12$ vom avea a diagonală de lungime $13$.
Această proprietate se poate generaliza şi pentru spaţiu. Dacă avem un paralelipiped dreptunghic cu cele trei muchii $a$, $b$ şi $c$, atunci lungimea diagonalei şi lungimile muchiilor respectă relaţia: $d^2^ = a^2^ + b^2^ + c^2^$. De asemenea putem găsi lungimi din mulţimea numerelor naturale pentru muchii astfel ca şi diagonala să fie un număr natural. De exemplu dacă muchiile paralelipipedului dreptunghic sunt $4$, $4$ respectiv $2$, atunci diagonala va avea lungimea $6$.
În general, dacă avem un paralelipiped dreptunghic dintr-un spaţiu $k$-dimensional, ale cărui muchii au lungimile $a{~1~}, a{~2~}, ..., a{~k~}$ lungimea diagonalei şi lungimile muchiilor vor respecta relaţia $d^2^ = a{~1~}^2^ + a{~2~}^2^ + ... + a{~k~}^2^$
h2. Cerinţă
Cunoscând dimensiunea $k$ a spaţiului, se cere să se găsească un paralelipiped $k$-dimensional în care atât diagonala d cât şi lungimile laturilor $a{~1~}, a{~2~}, ... , a{~k~}$ sunt numere naturale.
h2. Date de intrare
Fişierul de intrare $pitagora.in$ ...
Fişierul $pitagora.in$ va conţine pe prima linie valoarea lui $k$ cu semnificaţia de mai sus.
h2. Date de ieşire
În fişierul de ieşire $pitagora.out$ ...
Fişierul $pitagora.out$ va conţine mai multe linii. Pe prima linie se va scrie valoarea lui $d$, pe linia a doua se va scrie valoarea $p$ (numărul de numere distincte din şirul $a{~1~}, a{~2~}, ... , a{~k~}$), iar pe următoarele $p$ linii câte două numere naturale separate printr-un spaţiu: pe linia $i + 2$ se vor afla numerele $f{~i~}$ şi $c{~i~}$, cu semnificaţia că, un număr de $f{~i~}$ muchii ale paralelipipedului $k$-dimensional sunt egale cu valoarea $c{~i~}$.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $2 ≤ k ≤ 100 000 000$
* $0 < d^2^ ≤ 2 000 000 000$
* $0 < c{~1~}, c{~2~}, ..., c{~p~}, f{~1~}, f{~2~}, ..., f{~p~}$
* $d^2^ = f{~1~}*c{~1~}^2^ + f{~2~}*c{~2~}^2^ + ... + f{~p~}*c{~p~}^2^$
* $k = f{~1~} + f{~2~} + ... + f{~p~}$
* Soluţia problemei nu este unică. Se acceptă orice soluţie corectă
h2. Exemplu
table(example). |_. pitagora.in |_. pitagora.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
table(example). |_. pitagora.in |_. pitagora.out |_. Explicatie |
| 4
| 2
1
4 1
| În spaţiul 4-dimensional (k=4), diagonala de lungime 2, se obţine
cu 4 laturi de lungime 1, pentru că 2^2^ = 1^2^ + 1^2^ + 1^2^ + 1^2^.
|
| 3
| 6
2
1 2
2 4
| În spaţiul tridimensional (k=3), diagonala de lungime 6 se obţine cu ajutorul unei
muchii de lungime 2 şi a altor două muchii de lungime 4. (6^2^ = 2^2^ + 4^2^ + 4^2^)
|
h3. Explicaţie
...
== include(page="template/taskfooter" task_id="pitagora") ==
