Zlatograd


Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type
Allowed languages
C, C++, haskell, pypy, Python

Grad Zlatograd dobio je novog gradonačelnika koji voli brojeve. Gradonačelnik je odlučio da kućni brojevi u ulicama moraju biti Fibonaccijevi brojevi. Svaki kućni broj mora biti iz skupa kod kojeg su prva dva člana 1 i 2, a svaki slijedeći se dobije kao zbroj prethodna dva (početak skupa je: {1, 2, 3, 5, 8, 13, 21, ...}). Kao i u drugim gradovima, na jednoj strani ulice se nalaze kuće s parnim brojevima, a na drugoj one čiji su kućni brojevi neparni. Ako znate da je za numeriranje kuća neke ulice bilo potrebno \(n\) brojeva, izračunajte koliko kuća se nalazi na svakoj strani ulice.

Ulaz

U jedinom retku dan je broj \(n\), \((1 \leq n \leq 10^{18})\), broj kuća u ulici.

Izlaz

U jedini redak ispišite dva broja, prvo broj kuća s parne strane ulice, a zatim broj kuća s neparne strane ulice.

U 20% primjera će vrijediti \(n \leq 15\),
U 50% primjera će vrijediti \(n \leq 10^5\).

Primjer ulaza

3

Primjer izlaza

1 2

Primjer ulaza

5

Primjer izlaza

2 3

Pojašnjenje

S lijeve strane ulice se nalaze brojevi 1, 3 i 5, a s desne 2 i 8.


Comments

There are no comments at the moment.