解題區/解題區 - UVa

UVa 560 - Magic

contents

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

Problem

根據下列幾個條件，要把一個數字移除掉這些性質。

  • if a number is divisible by 3: divide it by 3
  • if a number is divisible by 7: divide it by 7
  • if a 3 occurs in the decimal representation: remove this 3 (remove if possible leading zeros)
  • if a 7 occurs in the decimal representation: remove this 7 (remove if possible leading zeros)
  • if a substring of 3 times the same digit occurs in the decimal representation: remove * it (remove if possible leading zeros)
  • if a substring of 7 times the same digit occurs in the decimal representation: remove it (remove if possible leading zeros)
  • if eventually no digit is left, consider this as the number 0.

移除的位置和順序可以任意替換，請問最後最大的數字為何？

Sample Input

1
2
3
4
3
999
273
2331

Sample Output

1
2
3
11
2
11

Solution

模擬這些移除的操作，使用 bfs 搜索，由於數字會越來越小，因此小於當前答案的部分可以忽略搜索，否則將很容易得到 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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <string.h>
using namespace std;
string divideString(string u, int div) {
    char s[1024] = {};
    int num = 0;
    for (int i = 0; i < u.length(); i++) {
        num = num * 10 + u[i] - '0';
        s[i] = num/div + '0', num %= div;
    }
    int idx = s[0] == '0' ? 1 : 0;
    string v = s + idx;
    return v;
}
string removePos(string u, int pos, int items = 1) {
    string v = u.substr(0, pos) + u.substr(pos + items);
//    cout << u << ", " << pos <<" = " << v<< endl;
    if (v.length() == 0)
        return "0";
    return v;
}
int numicStringCompare(string u, string v) {
    if (u.length() != v.length())
        return u.length() < v.length();
    for (int i = 0; i < u.length(); i++) {
        if (u[i] != v[i])
            return u[i] < v[i];
    }
    return 0;
}
int main() {
    int testcase;
    scanf("%d", &testcase);
    while (testcase--) {
        char s[1024];
        scanf("%s", s);
        set<string> diff;
        queue<string> Q;
        string ret = "";
        diff.insert(s), Q.push(s);
        while (!Q.empty()) {
            string u = Q.front();
            Q.pop();
//            cout << u << endl;
            if (numicStringCompare(u, ret))
                continue;
            int r3 = 0, r7 = 0;
            int cond = 0;
            for (int i = 0; i < u.length(); i++) {
                r3 = (r3 * 10 + u[i] - '0')%3;
                r7 = (r7 * 10 + u[i] - '0')%7;
            }
            if(r3 == 0) {
                string v = divideString(u, 3);
                if (diff.find(v) == diff.end())
                    diff.insert(v), Q.push(v);
                cond = 1;
            }
            if (r7 == 0) {
                string v = divideString(u, 7);
                if (diff.find(v) == diff.end())
                    diff.insert(v), Q.push(v);
                cond = 1;
            }
            for (int i = 0; i < u.length(); i++) {
                if (u[i] == '3' || u[i] == '7') {
                    string v = removePos(u, i);
                    if (diff.find(v) == diff.end())
                        diff.insert(v), Q.push(v);
                    cond = 1;
                }
            }
            for (int i = 0; i < u.length(); i++) {
                int con3 = 0, con7 = 0;
                for (int j = i, k = 0; k < 3 && j < u.length(); j++, k++) {
                    if (u[j] == u[i])
                        con3++;
                    else    break;
                }
                for (int j = i, k = 0; k < 7 && j < u.length(); j++, k++) {
                    if (u[j] == u[i])
                        con7++;
                    else    break;
                }
                if (con3 == 3) {
                    string v = removePos(u, i, 3);
                    if (diff.find(v) == diff.end())
                        diff.insert(v), Q.push(v);
                    cond = 1;
                }
                if (con7 == 7) {
                    string v = removePos(u, i, 7);
                    if (diff.find(v) == diff.end())
                        diff.insert(v), Q.push(v);
                    cond = 1;
                }
            }
            if (cond == 0) {
                if (numicStringCompare(ret, u)) {
                    ret = u;
                }
            }
        }
        cout << ret << endl;
    }
    return 0;
}
/*
 3
 999
 273
 2331
 
 6
 4900006514979587103
 9305660497031957126752544737246
 13708976269278645181999140607
 1427490008594779
 107351103235212538538682
 65244379091939972650698
*/