== include(page="template/taskheader" task_id="fibo2") ==
Poveste şi cerinţă...
Maria este pasionată de matematică. Ea este interesată în special elementele şirului Fibonacci şi vrea să studieze proprietăţile elementelor acestui şir. De curând a scris elementele Fibonacci: $1, 1, 2, 3, 5, 8, 13, ...$ şi a observat că un element, numărul $5$, poate fi scris ca sumă de alte două numere Fibonacci ridicate la pătrat, $5 = 1^2^ + 2^2^$, iar alt număr Fibonacci, numărul $144$, poate fi scris ca diferenţă a altor două numere Fibonacci ridicate la pătrat, $144 = 13^2^ - 5^2^$.
Maria a fost încântată de rezultatele pe care le-a obţinut şi ar dori să mai găsească şi alte elemente ale şirului care se pot scrie ca sumă sau ca diferenţă de alte două numere Fibonacci ridicate la pătrat.
h2. Cerinţă
Ajutaţi-o pe Maria, să decidă despre un element Fibonacci oarecare dacă se poate scrie ca sumă sau diferenţă de două numere Fibonacci distincte ridicate la pătrat. Datorită valorilor mari ale numerelor Fibonacci se cere restul împărţirii lor la *$46337$*.
h2. Date de intrare
Fişierul de intrare $fibo2.in$ ...
Fişierul de intrare $fibo2.in$ conţine un singur număr natural $N$, ce reprezintă numărul de ordine al celui de al $N$-lea număr Fibonacci.
h2. Date de ieşire
În fişierul de ieşire $fibo2.out$ ...
În cazul în care problema are soluţie, fişierul $fibo2.out$ va conţine $5$ rânduri:
{*} prima linie a fişierului va conţine valoarea $1$ sau $0$, după cum cel de al n-lea număr Fibonacci poate fi scris ca sumă, respectiv ca diferenţă a altor două numere Fibonacci ridicate la pătrat.
{*} a doua linie a fişierului de ieşire va conţine două numere naturale $i$ şi $j$ ({$0 < i < j$}) separate printr-un spaţiu, reprezentând numerele de ordine a celor două elemente Fibonacci cerute în enunţ $(f{~n~} = f{~j~}^2^ ± f{~i~}^2^)$.
{*} a treia linie a fişierului de ieşire va conţine restul împărţirii celui de al $i$-lea număr Fibonacci la $46337$,
{*} a patra linie a fişierului de ieşire va conţine restul împărţirii celui de al $j$-lea număr Fibonacci la $46337$
{*} a cincea linie a fişierului de ieşire va conţine restul împărţirii celui de al $N$-lea număr Fibonacci la $46337$.
În cazul în care problema nu are soluţie, fişierul de ieşire va conţine pe prima linie valoarea $-1$.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $4 ≤ n ≤ 25 000$
* Indicii numerelor Fibonacci pornesc de la 1: f{~1~} = 1; f{~2~} = 1; f{~3~} = 2, ...
* Pot exista mai multe soluţii, în acest caz se acceptă oricare dintre ele.
h2. Exemplu
table(example). |_. fibo2.in |_. fibo2.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicaţie
...
table(example). |_. fibo2.in |_. fibo2.out |_. Explicatie |
| 5
| 1
1 3
1
2
5
| 1 - este vorba de o sumă
se folosesc elementele f{~1~} şi f{~3~}
$f{~1~} mod 46337 = 1$
$f{~3~} mod 46337 = 2$
$f{~5~} mod 46337 = 5$
fiindcă $f{~5~} = f{~1~}^2^ + f{~3~}^2^ = 1^2^ + 2^2^ = 1 + 4 = 5$
|
| 5
| 0
3 4
2
3
5
| 0 - este vorba de o diferenţă
se folosesc elementele f{~3~} şi f{~4~}
$f{~3~} mod 46337 = 2$
$f{~4~} mod 46337 = 3$
$f{~5~} mod 46337 = 5$
fiindcă $f{~5~} = f{~4~}^2^ - f{~3~}^2^ = 3^2^ - 2^2^ = 9 - 4 = 5$
|
| 12
| 0
5 7
5
13
144
| 0 - este vorba de o diferenţă
se folosesc elementele f{~5~} şi f{~7~}
$f{~5~} mod 46337 = 5$
$f{~7~} mod 46337 = 13$
$f{~12~} mod 46337 = 144$
fiindcă $f{~12~} = f{~7~}^2^ - f{~5~}^2^ = 13^2^ - 5^2^ = 169 - 35 = 144$
|
== include(page="template/taskfooter" task_id="fibo2") ==
