UVa 12400 - 3, 2, 1, 0 (數學想法題&高精度 or 打表)

思路：

按照這個思路，其實這個序列是唯一的，如下：（1000位數，打表代碼見文章最後）

3233232323222233222323222322322222332322232332333223232332222233232232233232223322232222233322223233323332333332323332333233333332233233222232223222222322322333322322222332323222322333232222222232223322332333223232233232222222323333323323232232333322333332223223322232323333232333332323233333323322223332223322222222232223332332332333233333233232333333233322223322222333333223232223232232223323232323333222323333332222333332222323323332323233332233323233233232332232223323223323222222323322333333323232322232222333233332232232233233332232223322233233232222222323333322322222222322323322333233333222323222222223222223233333223323232333223233222333232233333222233333322332322233332222333222323232223223233323223232332222332323232233333223333232232323322222233222333332223222233322323233233233232332323332222222332323322232332233323222222322333223322323322332232332222333222233333323332322232232232222233232332323332232222233323332233323223222232232232232332222333332332333333332223233333323323232223232

所以O(1)復雜度的代碼如下：

/*0.015s*/

#include
#include
const int mx = 1000;
const char s[mx + 1] = 233232323222233222323222322322222332322232332333223232332222233232232233232223322232222233322223233323332333332323332333233333332233233222232223222222322322333322322222332323222322333232222222232223322332333223232233232222222323333323323232232333322333332223223322232323333232333332323233333323322223332223322222222232223332332332333233333233232333333233322223322222333333223232223232232223323232323333222323333332222333332222323323332323233332233323233233232332232223323223323222222323322333333323232322232222333233332232232233233332232223322233233232222222323333322322222222322323322333233333222323222222223222223233333223323232333223233222333232233333222233333322332322233332222333222323232223223233323223232332222332323232233333223333232232323322222233222333332223222233322323233233233232332323332222222332323322232332233323222222322333223322323322332232332222333222233333323332322232232232222233232332323332232222233323332233323223222232232232232332222333332332333333332223233333323323232223232;

int cnt[2][mx];

int main()
{
	for (int i = 1; i < mx; ++i)
	{
		++cnt[s[mx - i - 1] - '2'][i];
		cnt[0][i] += cnt[0][i - 1];
		cnt[1][i] += cnt[1][i - 1];
	}
	int n, m, k;
	while (~scanf(%d%d%d, &n, &m, &k))
	{
		if (k && n >= cnt[1][k] && m >= cnt[0][k]) puts(s + mx - 1 - k);
		else puts(Impossible.);
	}
	return 0;
}

/*1.802s*/

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

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

	public static void main(String[] args) {
		int N, M, K, kk, i;
		BigInteger MASK, ten, cur;
		char ans[];
		while (cin.hasNextInt()) {
			N = cin.nextInt();
			M = cin.nextInt();
			K = cin.nextInt();
			if (K == 0) {
				System.out.println(Impossible.);
				continue;
			}
			if (K > M + N) {
				System.out.println(Impossible.);
				continue;
			}
			MASK = BigInteger.valueOf(2).pow(K).subtract(BigInteger.ONE); // MASK=2^k-1	
			ans = new char[K];
			kk = K;
			ten = BigInteger.ONE;
			cur = BigInteger.ZERO;
			for (i = 0; i < K; ++i) {
				if (cur.and(BigInteger.ONE.shiftLeft(i)).equals(BigInteger.ZERO)) { // cur二進制的第i位為0
					ans[--kk] = '2';
					if (--M < 0) {
						System.out.println(Impossible.);
						break;
					}
					cur = cur.add(ten.multiply(BigInteger.valueOf(2)));
					if (cur.compareTo(MASK) > 0) {
						cur = cur.and(MASK); // 取模,以防止cur過大減慢運算速度
					}
				}
				else {// cur二進制的第i位為1
					ans[--kk] = '3';
					if (--N < 0) {
						System.out.println(Impossible.);
						break;
					}
					cur = cur.add(ten.multiply(BigInteger.valueOf(3)));
					if (cur.compareTo(MASK) > 0) {
						cur = cur.and(MASK); // 取模,以防止cur過大減慢運算速度
					}
				}
				ten = ten.multiply(BigInteger.valueOf(10));
			}
			if (i == K)
				System.out.println(ans);
		}
	}
}