Link

传送门

Problem

Robodevil likes to do some mathematics between rehearsals of his orchestra. Today he invented devilish sequence No. 1729:

  • x0 = 0,
  • x1 = 1,
  • xn = (xn − 1 + xn − 2) / 2.

For example, x10 = 0.666015625. Robodevil became interested at once how many sixes there were at the beginning of an arbitrary xn. In 6 nanoseconds, he had a formula. Can you do the same?

Mean

给定一个递推数列,求数列中第n个数,小数点后面有几个连续0

Analysis

分数打表可以用Python,from fractions import Fraction一下,Fraction写起来很方便

打表可以发现数列趋近于2/3,然后我们可以计算出每个数和2/3的差值,发现差值为1/(6*(2^(N-2))),那就好办了,交给java的BigDecimal算吧。

Code

import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.Scanner;

public class Main {

    final static int scalc = 102400;

    void solve() {
        Scanner cin = new Scanner(System.in);
        int N = cin.nextInt();
        BigInteger t = new BigInteger("6").shiftLeft(N-2);
        BigDecimal var = new BigDecimal("2");
        var = var.divide(BigDecimal.valueOf(3), scalc, BigDecimal.ROUND_DOWN);
        BigDecimal sub = BigDecimal.ONE.divide(new BigDecimal(t), scalc, BigDecimal.ROUND_DOWN);
        BigDecimal ans;
        if((N % 2) == 0) ans = var.subtract(sub);
        else ans = var.add(sub);
        String res = ans.toString();
        int cnt = 0;
        for(int i = 2; i < res.length(); ++i) {
            if(res.charAt(i) == '6') ++cnt;
            else break;
        }
        System.out.println(cnt);
    }

    public static void main(String[] args) {
        new Main().solve();
    }
}

欢迎留言