解題區/解題區 - 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;
}