Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | pitagora.in, pitagora.out | Sursă | Lot Arad 2011 |
| Autor | Zoltan Szabo | Adăugată de |  Gavrila Vlad •GavrilaVlad |
| Timp execuţie pe test | 0.125 sec | Limită de memorie | 36864 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Pitagora
Să considerăm un dreptunghi în plan cu laturile a şi b. Conform teoremei lui Pitagora lungimea diagonalei d respectă relaţia d2 = a2 + b2. 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: d2 = a2 + b2 + c2. 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 a1, a2, ..., ak lungimea diagonalei şi lungimile muchiilor vor respecta relaţia d2 = a12 + a22 + ... + ak2
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 a1, a2, ... , ak sunt numere naturale.
Date de intrare
Fişierul pitagora.in va conţine pe prima linie valoarea lui k cu semnificaţia de mai sus.
Date de ieşire
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 a1, a2, ... , ak), iar pe următoarele p linii câte două numere naturale separate printr-un spaţiu: pe linia i + 2 se vor afla numerele fi şi ci, cu semnificaţia că, un număr de fi muchii ale paralelipipedului k-dimensional sunt egale cu valoarea ci.
Restricţii
- 2 ≤ k ≤ 100 000 000
- 0 < d2 ≤ 2 000 000 000
- 0 < c1, c2, ..., cp, f1, f2, ..., fp
- d2 = f1*c12 + f2*c22 + ... + fp*cp2
- k = f1 + f2 + ... + fp
- Soluţia problemei nu este unică. Se acceptă orice soluţie corectă
Exemplu
| 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ă 22 = 12 + 12 + 12 + 12. |
| 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. (62 = 22 + 42 + 42) |
