Ciąg
Limit pamięci: 32 MB
Jaś niedawno usłyszał w szkole o ciągach liczbowych.
Bardzo mu się one spodobały i szybko zaczął tworzyć swoje własne, długie
sekwencje liczb.
Jego najnowszym wymysłem jest ciąg -
niemalejąca sekwencja liczb naturalnych
o następującej własności: dla każdej liczby naturalnej
zawiera ona dokładnie wystąpień liczby .
(Zakładamy przy tym, że nie jest liczbą naturalną).
Innymi słowy, dla każdego dokładnie spośród liczb
jest równe .
Pierwszych kilka wyrazów ciągu udało się Jasiowi wypisać, ale kartka
i długopis okazały się niewystarczające, aby wygenerować jakiś dłuższy
początkowy fragment ciągu.
Pomóż Jasiowi uporać się z tym problemem.
Zadanie
Napisz program, który:
-
wczyta ze standardowego wejścia liczbę naturalną ,
-
wyznaczy -ty wyraz ciągu ,
-
wypisze wynik na standardowe wyjście.
Wejście
Pierwszy i jedyny wiersz wejścia zawiera jedną liczbę naturalną
() - numer szukanego wyrazu ciągu.
Wyjście
Pierwszy i jedyny wiersz wyjścia powinien zawierać jedną liczbę naturalną
.
Przykład
Dla danych wejściowych:
5
poprawną odpowiedzią jest:
3
Wyjaśnienie do przykładu: oznacza, że w ciągu liczba
występuje dokładnie razy; dokładniej, .
Uwaga: Możesz założyć, że w co najmniej 40% testów jest spełniony
warunek , a w co najmniej 70% testów - warunek
.
Autor zadania: Wojciech Tyczyński.