Fişierul intrare/ieşire:pitagora.in, pitagora.outSursăLot Arad 2011
AutorZoltan SzaboAdăugată deGavrilaVladGavrila Vlad GavrilaVlad
Timp execuţie pe test0.25 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultateN/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.inpitagora.outExplicatie
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)
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content