当前位置:首页 » Project Euler » 详细页

Non-bouncy numbers 题号:113 难度: 30 中英对照

Working from left-to-right if no digit is exceeded by the digit to its left it is called an increasing number; for example, 134468.

Similarly if no digit is exceeded by the digit to its right it is called a decreasing number; for example, 66420.

We shall call a positive integer that is neither increasing nor decreasing a "bouncy" number; for example, 155349.

As n increases, the proportion of bouncy numbers below n increases such that there are only 12951 numbers below one-million that are not bouncy and only 277032 non-bouncy numbers below 1010.

How many numbers below a googol (10100) are not bouncy?

Solution

本题用到组合数学中的一些知识。 设$n$是数字的位数,用组合数,来计算 *increasing or decreasing numbers*,首先将每个数字表示为一个数字槽序列和增量操作序列。 例如, $n=5$,*increasing number* 是 $23667$,可以用 "+ + # + # + + + # # + # + +“来表示,其中 \# 表示数字,\+ 表示增加的量(即相比前一个数增大的数字,特别的,第一位数字与0比较计算增量,最后的加号是9与最后一位比较计算增量),同理对于减数用 \- 表示。 - 对于increasing *number* ,每个数字有n 个数字槽和9(首位不为0)个增量的任意定位(即对于一个n位的increasing *number*,表示成上面形式一定有n个 \# 号和 9个 \+ 号),每个递增的数字也是与它相对应,可以生成一个唯一的数字槽与增量序列。所以用二项式 $C(n+9,9) -1$ 来安排他们(减1是排除其中的0); - 同理,对于*decreasing numbers*,每个数字有n 个数字槽和10(末位可为0)个增量的任意定位,用二项式 $C(n+10,10)$表示,但是其中0 可以在两个数字槽间产生,有 $n+1$ 种,即*decreasing numbers* 数个数为$C(n+10,10)- (n+1)$ ; - 其中有类数同时满足”increasing“ 和 ”decreasing”, 即各位数字相同的数,序列个数为 $9n$个; 综合上面的情况, 可知满足条件的 *non-bouncy numbers* 个数为: $$ (C(n+9,9) -1) + (C(n+10,10)- (n+1)) -9n $$

Code

import java.math.BigInteger;

public final class p113{

    public static void main(String[] args) {
        long start=System.nanoTime();
        String result = run();
        long end=System.nanoTime();
        System.out.println(result);
        System.out.println( (end-start)/1000000 + "ms" );
    }


	/*
	 * Let n be the number of digits. To count the number of increasing or decreasing numbers using combinatorics,
	 * let's view each number as a sequence of digit readout slots and operations. For example, suppose n=5 and
	 * we examine the increasing number 23667. We can express it as the sequence "+ + # + # + + + # # + # + +",
	 * where # is a digit and + means increment. This way of thinking will be useful, as we will see.
	 *
	 * For the set of increasing numbers, each number has n readout slots and 9 increments, positioned arbitrarily.
	 * Using this construction, the number is guaranteed to be increasing. Note that leading zeros can be produced.
	 * Conversely, for each increasing number, we can generate a (unique) sequence of slots and increments that represents it
	 * (putting all unused increments after the rightmost digit). Hence there are n+9 objects to arrange in sequence,
	 * so there are binomial(n + 9, 9) ways to arrange them. Finally we subtract 1 because 0 can be formed with this scheme,
	 * which must be excluded from the set of increasing numbers.
	 *
	 * For the set of decreasing numbers, each number has n readout slots and 10 operations. Of the 10 operations,
	 * the leading one must be "increment to 9", and the rest must be decrements. Similar to the increasing case,
	 * each sequence of slots and decrements produces a decreasing number, and conversely each decreasing number
	 * corresponds to a unique sequence of slots and decrements. However, 0 can be formed in n+1 ways, by concentrating
	 * all 10 operations between some pair of slots, e.g. "+9 -9 # # # #", "# +9 -9 # # #", ..., "# # # # +9 -9".
	 *
	 * There are 9n "flat" numbers, for example: 1, 2, ..., 9; 11, 22, ..., 99; 111, 222, ..., 999; ... (note that 0 is excluded).
	 * Since they are double-counted in the increasing and decreasing numbers, we subtract the size of this set.
	 *
	 * In conclusion, the number of non-bouncy numbers is (binomial(n+9,9) - 1) + (binomial(n+10,10) - (n+1)) - 9n.
	 *
	 * (Technically, in the problem statement and this solution, "increasing" actually means "nondecreasing" and "decreasing" means "nonincreasing".)
	 */

    private static final int DIGITS = 100;

    public static String run() {
        BigInteger increasing = binomial(DIGITS + 9, 9).subtract(BigInteger.ONE);
        BigInteger decreasing = binomial(DIGITS + 10, 10).subtract(BigInteger.valueOf(DIGITS + 1));
        BigInteger flat = BigInteger.valueOf(DIGITS * 9);
        return increasing.add(decreasing).subtract(flat).toString();
    }

    // Returns n choose k.
    private static BigInteger binomial(int n, int k) {
        if (k < 0 || k > n)
            throw new IllegalArgumentException();
        BigInteger product = BigInteger.ONE;
        for (int i = 0; i < k; i++)
            product = product.multiply(BigInteger.valueOf(n - i));
        return product.divide(factorial(k));
    }

    // Returns n!.
    private static BigInteger factorial(int n) {
        if (n < 0)
            throw new IllegalArgumentException("Factorial of negative number");
        BigInteger prod = BigInteger.ONE;
        for (int i = 2; i <= n; i++)
            prod = prod.multiply(BigInteger.valueOf(i));
        return prod;
    }

}
51161058134250
1ms