악마의 수열

시간 제한0.5초메모리 제한64 MB

요약

x_0=0, x_1=1, x_n=(x_{n-1}+x_{n-2})/2로 정의된 수열에서 x_n의 소수점 아래 첫 자리부터 연속하는 6의 개수를 구한다.

문제

악마의 수열 $x$ 는 다음과 같이 정의한다.

$x_0 = 0, \qquad x_1 = 1, \qquad x_n = \frac{x_{n-1} + x_{n-2}}{2} \quad (n \ge 2)$

예를 들어 $x_{10} = 0.666015625$ 이고, 소수점 아래 첫째 자리부터 6이 3개 연속된다.

$n$ 이 주어졌을 때, $x_n$ 을 소수로 적으면 소수점 아래 첫째 자리부터 6이 몇 개 연속되는지 구하는 프로그램을 작성하시오.

첫째 줄에 정수 $n$ 이 주어진다. ( $2 \le n \le 100000$ )

첫째 줄에 $x_n$ 의 소수점 아래 첫째 자리부터 연속되는 6의 개수를 출력한다. 첫째 자리가 6이 아니면 0을 출력한다.