解題區►解題區 - UVa

UVa 12486 - Space Elevator

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

將所有數字中出現 4 或者是 13 為子字串排除，將剩餘數字排序後，根據輸入輸出 i-th 的結果為何。(傳統避諱的樓層命名方式)

Sample Input

1
2
3
4
5
1
4
11
12
440

Sample Output

1
2
3
4
5
1
5
12
15
666

Solution

  • dp[i][0] 表示長度為 i 的情況下，不以 3 開頭的所有符合數字
  • dp[i][1] 表示長度為 i 的情況下，以 3 開頭的所有符合數字

接著，企圖添加 digit 在長度為 i-1 的數字前面，只要不添加 1 湊出 13 即可。直接禁用 4 就沒有什麼問題。

而隨後要輸出 i-th 的時候，用扣的方式依序得到 lower_bound。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <stdio.h>
#include <algorithm>
using namespace std;
int main() {
	unsigned long long n;
	unsigned long long dp[30][2] = {};
	unsigned long long sum[30] = {};
	dp[0][0] = 1; // [1-9^3], dp[i][1] - [3(0-9)*]
	for(int i = 1; i < 30; i++) {
		for(int j = 0; j < 2; j++) {
			dp[i][0] = 8 * dp[i-1][0] + 7 * dp[i-1][1];
			dp[i][1] = dp[i-1][0] + dp[i-1][1];
		}
	}
	for(int i = 1; i < 30; i++)
		sum[i] = sum[i-1] + (dp[i-1][0] + dp[i-1][1])* 7 + dp[i][1] - dp[i-1][1];
	while(scanf("%llu", &n) == 1) {
		int len = 0;
		for(len = 1; sum[len] <= n; len++);
		int prev = 0;
		n -= sum[len-1];
		for(int i = len; i >= 1; i--) {
			int last = -1;
			for(int j = (i == len); j <= 9; j++) {
				if(j == 4 || (prev == 1 && j == 3))	continue;
				if(j == 1) { // [1] - [0-9^3]
					if(n > dp[i-1][0]) {
						n -= dp[i-1][0], last = j;
//						printf("%llu test\n", dp[i-1][0]);
					} else {
						break;
					}
				} else {
					if(n > dp[i-1][0] + dp[i-1][1]) {
						n -= dp[i-1][0] + dp[i-1][1], last = j;
//						printf("%llu test\n", dp[i-1][0] + dp[i-1][1]);
					} else
						break;
				}
			}
			last++;
			if(last == 4)	last++;
			if(i == len && last == 0)	last = 1;
			if(prev == 1 && last == 3)	last = 5;
			printf("%d", last), prev = last;
		}
		puts("");
	}
	return 0;
}