PKU 1426 Find The Multiple

• 動的計画法
• Subset Sum Problemという有名問題らしい
• 横方向に桁数、縦方向にNの余剰を配置する
• REで通らなかったため、テーブルを埋め込んだ

static const char* table[] = 
{"",
"1",
"10",
"111",
"100",
"10",
"1110",
"1001",
"1000",
"111111111",
"10",
"11",
"11100",
"1001",
"10010",
"1110",
"10000",
"11101",
"1111111110",
"11001",
"100",
"10101",
"110",
"110101",
"111000",
"100",
"10010",
"1101111111",
"100100",
"1101101",
"1110",
"111011",
"100000",
"111111",
"111010",
"10010",
"11111111100",
"111",
"110010",
"10101",
"1000",
"11111",
"101010",
"1101101",
"1100",
"1111111110",
"1101010",
"10011",
"1110000",
"1100001",
"100",
"100011",
"100100",
"100011",
"11111011110",
"110",
"1001000",
"11001",
"11011010",
"11011111",
"11100",
"100101",
"1110110",
"1111011111",
"1000000",
"10010",
"1111110",
"1101011",
"1110100",
"10000101",
"10010",
"10011",
"111111111000",
"10001",
"1110",
"11100",
"1100100",
"1001",
"101010",
"11101001",
"10000",
"1111111101",
"111110",
"101011",
"1010100",
"111010",
"11011010",
"11010111",
"11000",
"11010101",
"1111111110",
"1001",
"11010100",
"10000011",
"100110",
"110010",
"11100000",
"11100001",
"11000010",
"111111111111111111",
"100",
"101",
"1000110",
"11100001",
"1001000",
"101010",
"1000110",
"110100111",
"111111110100",
"1111111011",
"110",
"111",
"10010000",
"1011011",
"110010",
"1101010",
"110110100",
"10101111111",
"110111110",
"110001101",
"111000",
"11011",
"1001010",
"10001100111",
"11101100",
"1000",
"11110111110",
"11010011",
"10000000",
"100100001",
"10010",
"101001",
"11111100",
"11101111",
"11010110",
"11011111110",
"11101000",
"10001",
"100001010",
"110110101",
"100100",
"10011",
"100110",
"1001",
"1111111110000",
"11011010",
"100010",
"1100001",
"11100",
"110111",
"11100",
"1110001",
"11001000",
"11111011011",
"10010",
"1110110",
"1010100",
"10101101011",
"111010010",
"100011",
"100000",
"11101111",
"11111111010",
"1010111",
"1111100",
"1111110",
"1010110",
"11111011",
"10101000",
"10111101",
"111010",
"1111011111",
"110110100",
"1011001101",
"110101110",
"100100",
"110000",
"100101111",
"110101010",
"11010111",
"11111111100",
"1001111",
"10010",
"100101",
"110101000",
"1110",
"100000110",
"1001011",
"1001100",
"1111101100011",
"110010",
"11101111",
"111000000",
"11001",
"111000010",
"101010",
"110000100",
"1101000101",
"1111111111111111110",
"111000011",
"1000",};

int main() {
	for (int N; cin >> N && N; ) {
	//for (int N = 1; N <= 200; ++N) {
		cout << table[N] << endl;
		//if (N == 1) {
		//	cout << "1" << endl;
		//	continue;
		//}
		//static int dp[256][512];
		//memset(dp, 0, sizeof(dp));
		//dp[0][1] = -1;
		//for (int i = 0; i < 256; ++i) {
		//	for (int n = 0; n < N; ++n) {
		//		if (!dp[i][n]) {
		//			continue;
		//		}

		//		dp[i + 1][(n * 10) % N] = n;
		//		dp[i + 1][(n * 10 + 1) % N] = n;
		//	}
		//}

		//int start;
		//for (start = 0; start < 256; ++start) {
		//	if (dp[start][0]) {
		//		break;
		//	}
		//}

		//vector<int> answer;
		//int current = 0;
		//for (int i = start; i > 0; --i) {
		//	const int next = dp[i][current];
		//	if ((next * 10) % N == current) {
		//		answer.push_back(0);
		//	} else {
		//		answer.push_back(1);
		//	}
		//	current = next;
		//}
		//answer.push_back(1);
		//reverse(answer.begin(), answer.end());

		//cout << "\"";
		//for (vector<int>::iterator it = answer.begin(), itEnd = answer.end(); it != itEnd; ++it) {
		//	cout << *it;
		//}
		//cout << "\",";
		//cout << endl;
	}
}