解題區/解題區 - UVa

UVa 12134 - Find the Format String

contents

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

Problem

給指定的輸入和輸出，找到一個正規表達的方式符合預期的 scanf(format, args);

Sample Input

1
2
3
4
5
6
7
8
9
5
"11" "11"
"243" "24"
"563" "56"
"784" "784"
"789" "78"
1
"A" "b" 
0

Sample Output

1
2
Case 1: [01245678]
Case 2: I_AM_UNDONE

Solution

其實這一題只是單純的切割字符串，但是要記住 scanf 的 format 是中 scanf("%[exp]", &str) 來說，exp 只填入塞選字符，不涵蓋其他的運算子，則會掃描到空白前且不存在 exp 中的字符為一個 token。 // 記住：直到第一個不符合條件的地方做切割。

接著要處理最小字典順序的問題，因此要對於非必要的塞選也要填入。

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
85
86
87
88
89
90
91
92
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <string.h>
#include <algorithm>
#include <queue>
#include <stack>
using namespace std;
int main() {
    int n, cases = 0;
    char in[128][128], out[128][128];
    while (scanf("%d", &n) == 1 && n) {
        for (int i = 0; i < n; i++)
            scanf("%s %s", in[i], out[i]);
        
        int ascii[128] = {};
        for (int i = '0'; i <= '9'; i++)
            ascii[i] = 1;
        for (int i = 'A'; i <= 'Z'; i++)
            ascii[i] = 1;
        for (int i = 'a'; i <= 'z'; i++)
            ascii[i] = 1;
        
        for (int i = 0; i < n; i++) {
            for (int j = 1; out[i][j]; j++) {
                if (in[i][j] != out[i][j]) {
                    ascii[in[i][j]] = 0;
                } else {
                    if (ascii[in[i][j]]) {
                        ascii[in[i][j]] |= 2;
                    }
                }
            }
        }
        
        char ret[128];
        int m = 0;
        for (int i = '0', j = '0' - 1; i < 128; i++) {
//            printf("%d %d\n", i, ascii[i]);
            if (ascii[i] == 3) {
                while (j < i) {
                    if (ascii[j] == 1)
                        ret[m++] = j;
                    j++;
                }
                ret[m++] = i;
            }
        }
        if (m == 0) {
            for (int i = '0'; i < 128; i++) {
                if (ascii[i] == 1) {
                    ret[m++] = i;
                    break;
                }
            }
        }
        ret[m] = '\0';
        char format[128];
        format[0] = '%', format[1] = '[';
        for (int i = 0; i < m; i++)
            format[i+2] = ret[i];
        format[m+2] = ']', format[m+3] = '\0';
        int ok = 1;
        if (m == 0)
            ok = 0;
        for (int i = 0; i < n && ok; i++) {
            char s[128] = {};
            in[i][strlen(in[i]) - 1] = '\0';
            sscanf(in[i]+1, format, s + 1);
            s[0] = '"';
            int len = (int)strlen(s);
            s[len] = '"', s[len+1] = '\0';
            ok &= !strcmp(s, out[i]);
        }
        printf("Case %d: %s\n", ++cases, ok ? format+1 : "I_AM_UNDONE");
    }
    return 0;
}
/*
 5
 "11" "11"
 "243" "24"
 "563" "56"
 "784" "784"
 "789" "78"
 1
 "A" "b" 
 0
 */