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.