UVa 10254 The Priest Mathematician(数学&法則発見&高精度の組み合わせ)

10254 - The Priest Mathematician
Time limit: 3.000 seconds
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=34&page=show_problem&problem=1195
The ancient folklore behind the "Towers of Hanoi" puzzle invented by E. Lucas in 1883 is quite well known to us. One more recent legend tells us that the Brahmin monks from Benares never believed that the world could vanish at the moment they finished to transfer the 64 discs from the needle on which they were to one of the other needles, and they decided to finish the task as soon as possible.
 
Fig: The Four Needle (Peg) Tower of Hanoi
 
One of the priests at the Benares temple (who loved the mathematics) assured their colleagues to achieve the transfer in the afternoon (the rhythm they had thought was a disc-per-second) by using an additional needle. They couldn't believe him, but he proposed them the following strategy:
 
-- First move the topmost discs (say the top k discs) to one of the spare needles.
 
-- Then use the standard three needles strategy to move the remaining n-k discs (for a general case with n discs) to their destination.
 
-- Finally, move the top k discs into their final destination using the four needles.
 
He calculated the value to k in order to minimize the number of movements and get a total of 18433 transfers, so they spent just 5 hours, 7minutes and 13 seconds against the more than 500000 millions years without the additional needle (as they would have to do 2^64-1 disc transfers. Can you believe it?)
 
Try to follow the clever priest's strategy and calculate the number of transfer using four needles but according with the fixed and immutable laws of Brahma, which require that the priest on duty must not move more than one disc at a time and that he must place this disc on a needle so that there is no smaller disc below it. Of course, the main goal is to calculate the k that minimize the number of transfers (even thought it is not know for sure that this is always the optimal number of movements).
 
Input
The input file contains several lines of input. Each line contains a single integer N, which is the number of disks to be transferred. Here0<=N<=10000. Input is terminated by end of file.
 
Output
For each line of input produce one line of output which indicates the number of movements required to transfer the N disks to the final needle.
 
Sample Input:
1
2
28
64
 
Sample Output:
1
3
769
18433
考え方:
テーマによって与えられた戦略:
f(1)=1, f(n)=min{2*f(k)+2^(n-k)-1} (1<=k<=n-1)
印刷前の項目:1,3,5,9,13,17,25,33,41,49,65,...
1次差分シーケンスの計算Δf(n):2,2,4,4,4,8,8,8,8,16,...
発見2^mは(m+1)回出現し,m>=0
これに基づいてすべての解を前処理する.
もっと多くの討論:《具体的な数学》P 16第17題、第25題
C++:

/*0.029s*/

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 50;

char numstr[maxn];

struct bign
{
	int len, s[maxn];

	bign()
	{
		memset(s, 0, sizeof(s));
		len = 1;
	}

	bign(int num)
	{
		*this = num;
	}

	bign(const char* num)
	{
		*this = num;
	}

	bign operator = (const int num)
	{
		char s[maxn];
		sprintf(s, "%d", num);
		*this = s;
		return *this;
	}

	bign operator = (const char* num)
	{
		len = strlen(num);
		for (int i = 0; i < len; i++) s[i] = num[len - i - 1] & 15;
		return *this;
	}

	///  
	const char* str() const
	{
		if (len)
		{
			for (int i = 0; i < len; i++)
				numstr[i] = '0' + s[len - i - 1];
			numstr[len] = '\0';
		}
		else strcpy(numstr, "0");
		return numstr;
	}

	///    
	void clean()
	{
		while (len > 1 && !s[len - 1]) len--;
	}

	/// 
	bign operator + (const bign& b) const
	{
		bign c;
		c.len = 0;
		for (int i = 0, g = 0; g || i < max(len, b.len); i++)
		{
			int x = g;
			if (i < len) x += s[i];
			if (i < b.len) x += b.s[i];
			c.s[c.len++] = x % 10;
			g = x / 10;
		}
		return c;
	}

	/// 
	bign operator - (const bign& b) const
	{
		bign c;
		c.len = 0;
		for (int i = 0, g = 0; i < len; i++)
		{
			int x = s[i] - g;
			if (i < b.len) x -= b.s[i];
			if (x >= 0) g = 0;
			else
			{
				g = 1;
				x += 10;
			}
			c.s[c.len++] = x;
		}
		c.clean();
		return c;
	}

	/// 
	bign operator * (const bign& b) const
	{
		bign c;
		c.len = len + b.len;
		for (int i = 0; i < len; i++)
			for (int j = 0; j < b.len; j++)
				c.s[i + j] += s[i] * b.s[j];
		for (int i = 0; i < c.len - 1; i++)
		{
			c.s[i + 1] += c.s[i] / 10;
			c.s[i] %= 10;
		}
		c.clean();
		return c;
	}

	/// 
	bign operator / (const bign &b) const
	{
		bign ret, cur = 0;
		ret.len = len;
		for (int i = len - 1; i >= 0; i--)
		{
			cur = cur * 10;
			cur.s[0] = s[i];
			while (cur >= b)
			{
				cur -= b;
				ret.s[i]++;
			}
		}
		ret.clean();
		return ret;
	}

	/// 、 
	bign operator % (const bign &b) const
	{
		bign c = *this / b;
		return *this - c * b;
	}

	bool operator < (const bign& b) const
	{
		if (len != b.len) return len < b.len;
		for (int i = len - 1; i >= 0; i--)
			if (s[i] != b.s[i]) return s[i] < b.s[i];
		return false;
	}

	bool operator > (const bign& b) const
	{
		return b < *this;
	}

	bool operator <= (const bign& b) const
	{
		return !(b < *this);
	}

	bool operator >= (const bign &b) const
	{
		return !(*this < b);
	}

	bool operator == (const bign& b) const
	{
		return !(b < *this) && !(*this < b);
	}

	bool operator != (const bign &a) const
	{
		return *this > a || *this < a;
	}

	bign operator += (const bign &a)
	{
		*this = *this + a;
		return *this;
	}

	bign operator -= (const bign &a)
	{
		*this = *this - a;
		return *this;
	}

	bign operator *= (const bign &a)
	{
		*this = *this * a;
		return *this;
	}

	bign operator /= (const bign &a)
	{
		*this = *this / a;
		return *this;
	}

	bign operator %= (const bign &a)
	{
		*this = *this % a;
		return *this;
	}
} f[10010], d;

void init()
{
	int count = 0, k = 1;
	f[0] = 0;
	d = 1;
	for (int i = 1; i <= 10000; ++i)
	{
		f[i] = f[i - 1] + d;
		++count;
		if (count == k)
		{
			count = 0; //   
			++k;
			d *= 2;
		}
	}
}

int main()
{
	init();
	int n;
	while (~scanf("%d", &n))
		puts(f[n].str());
	return 0;
}

Java:

/*1.479s*/

import java.util.*;
import java.io.*;
import java.math.*;

public class Main {
	static Scanner cin = new Scanner(new BufferedInputStream(System.in));

	public static void main(String[] args) {
		BigInteger[] f = new BigInteger[10010];
		int count = 0, k = 1;
		f[0] = BigInteger.ZERO;
		BigInteger d = BigInteger.ONE;
		for (int i = 1; i <= 10000; ++i) {
			f[i] = f[i - 1].add(d);
			++count;
			if (count == k) {
				count = 0; //   
				++k;
				d = d.multiply(BigInteger.valueOf(2));
			}
		}
		while (cin.hasNext())
			System.out.println(f[cin.nextInt()]);
	}
}