解題區/解題區 - UVa

UVa 12368 - Candles

contents

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

Problem

現在只有 0 - 9 共計 10 根蠟燭，有 N 個人過生日，每個人的生日年紀不大於 100。

最多用 10 根蠟燭，來表示每一個人的生日。每個人的生日可以用兩個整數加總，或者單純用一個整數表示。

Sample Input

1
2
3
2 10 11
1 30
0

Output for Sample Input

1
2
Case 1: 654
Case 2: 30

Solution

預建表，找到所有數字 [1, 100] 能用哪幾種蠟燭建出來。

測資很緊，不建表會一直 TLE。

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <stdio.h> 
#include <algorithm>
#include <iostream>
#include <map>
using namespace std;
int able[128][1024];
void build() {
    int d1, d2, d3, d4;
    for(int i = 1; i <= 100; i++) {
        if(i < 100) {
            if(i < 10) {
                d1 = i;
                able[i][1<<d1] = 1;
            } else {
                d1 = i%10, d2 = i/10;
                if(d1 != d2)
                    able[i][(1<<d1)|(1<<d2)] = 1;
            }
        }
        for(int j = 1; j < i; j++) {
            int a = j, b = i - j, mask = 0;
            if(a < 10) {
                mask |= 1<<a;
            } else {
                d1 = a%10, d2 = a/10;
                if(d1 == d2)
                    continue;
                mask |= (1<<d1)|(1<<d2);
            }
            if(b < 10) {
                if(mask&(1<<b))
                    continue;
                mask |= 1<<b;
            } else {
                d1 = b%10, d2 = b/10;
                if(d1 == d2)
                    continue;
                if(mask&((1<<d1)|(1<<d2)))
                    continue;
                mask |= (1<<d1)|(1<<d2);
            }
            able[i][mask] = 1;
        }
    }
    for(int i = 0; i < 128; i++) {
        for(int j = 0; j < 1024; j++) {
            for(int k = j; k; k = k&(k-1))
                able[i][j] |= able[i][j&(k-1)];
        }
    }
}
int main() {
    build();
//	freopen("in.txt", "r+t", stdin);
//	freopen("out.txt", "w+t", stdout);
    int n, A[10], cases = 0;
    while(scanf("%d", &n) == 1 && n) {
        map<int, int> R;
        for(int i = 0; i < n; i++)
            scanf("%d", &A[i]);
        
        int ret = (1<<10)-1;
        for(int i = 0; i < (1<<10); i++) {
            if(__builtin_popcount(i) >= __builtin_popcount(ret))
                continue;
            int f = 1;
            for(int j = 0; j < n && f; j++)
                f &= able[A[j]][i];
            if(f) {
                ret = i;		
            }
        }							
        printf("Case %d: ", ++cases);
        for(int i = 9; i >= 0; i--) {
            if((ret>>i)&1)
                printf("%d", i);
        }
        puts("");
    }
    return 0;
}