[UVa] 10254 - The Priest Mathematician

題目網址: http://goo.gl/v9zQ2y

題意:
(from luckycat)


解 法:
假設 f(n) 是以 4 根木棒的解法，求解 f(n) ，先把 k 塊圓板移到第四根木棒上，接著以 3 根木棒的方法移動 n-k 塊圓板至目標木棒，接著再以 4 根木棒的解法移動 k 塊圓板至目標木棒，由於以 3 根木棒的方法移動 k 個圓板會等於 (2^k)-1，所以 f(n) = min{ 2*f(k) + 2^(n-k) -1, 1 <= k < n }，先嘗試跑前幾個答案。

 f[0] = 0
f[1] = 1 = f[0] + 2^0
f[2] = 3 = f[1] + 2^1
f[3] = 5 = f[2] + 2^1
f[4] = 9 = f[3] + 2^2
f[5] = 13 = f[4] + 2^2
f[6] = 17 = f[5] + 2^2
f[7] = 25 = f[6] + 2^3
f[8] = 33 = f[7] + 2^3
f[9] = 41 = f[8] + 2^3
f[10] = 49 = f[9] + 2^3
f[11] = 65
f[12] = 81
f[13] = 97
f[14] = 113
f[15] = 129
f[16] = 161
f[17] = 193
f[18] = 225
f[19] = 257
f[20] = 289

會發現規律 f[i] = f[i-1] + 2^k, i > 0 & k 是第一個滿足 (k*(k+1))/2 >= i 的值。
由於 141*142/2 >= 10000 ，k 會到達 141，所以需要用大數。

TAG: Math, BigNum,

注意:

程式碼:

	/**
	* Tittle: 10254 - The Priest Mathematician
	* Author: Cheng-Shih, Wong
	* Date: 2015/05/27
	*/
	import java.util.*;
	import java.math.*;
	public class Main {
	public static void main( String[] args ) {
	int n = 0;
	BigInteger[] f = new BigInteger[10005];
	int cnt = 0;;
	Scanner input = new Scanner(System.in);
	// init
	f[0] = BigInteger.ZERO;
	cnt = 1;
	for( int i=1; i<=10000; ) {
	int j = cnt;
	BigInteger op = BigInteger.ONE.shiftLeft(cnt-1);
	while( (j--)>0 && i<=10000 ) {
	f[i] = f[i-1].add( op );
	++i;
	}
	++cnt;
	}
	// input
	while( input.hasNext() ) {
	n = input.nextInt();
	// output
	System.out.println(f[n]);
	}
	input.close();
	}
	}

view raw Main.java hosted with ❤ by GitHub