解題區/解題區 - UVa

UVa 10694 - Combinatorial Summation

Problem

對於組合公式，輸出其結果。

Sample Input

1
2
3
2
3
4

Sample Output

1
2
7
14

Solution

暴力法將前幾項找出來，發現其相鄰兩項之差恰好有規律。

1
2
0 1 3 7 14 26 46 79 133 
  0 2 4 7 12 20 33 54

其規律是前兩項總和再加一。

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
import java.util.Scanner;
import java.math.BigInteger;
public class Main {
    public static void main(String[] args) {
        BigInteger[] f1 = new BigInteger[1024];
        BigInteger[] f2 = new BigInteger[1024];
        f1[1] = BigInteger.valueOf(2);
        f1[2] = BigInteger.valueOf(4);
        f2[0] = BigInteger.valueOf(0);
        f2[1] = BigInteger.valueOf(1);
        for (int i = 3; i < f1.length; i++)
            f1[i] = f1[i - 2].add(f1[i - 1]).add(BigInteger.ONE);
        for (int i = 2; i < f2.length; i++)
            f2[i] = f2[i - 1].add(f1[i - 1]);
        Scanner cin = new Scanner(System.in);
        int testcase = cin.nextInt();
        while (testcase-- != 0) {
            int n = cin.nextInt();
            if (n < 0)
                n = 0;
            System.out.println(f2[n]);
        }
    }
}
/*
 * 0 1 3 7 14 26 46 79 133 
 	 0 2 4 7 12 20 33 54
 */
Read More +
解題區/解題區 - UVa

UVa 1635 - Irrelevant Elements

Problem

題目給定一種亂數產生方式，一開始先給定 n 個數字序列 ai (1 <= i <= n)，之後相鄰兩兩相加得到 n - 1 個數字的序列，最後這一個數字 mod m = ? 來決定最後要輸出的亂數。

請問最後產生出來的數字 無關序列的第幾項。

Sample Input

1
3 2

Sample Output

1
2
1
2

Solution

其實可以見到的，第 i 個數字會在最後使用 C(n-1, i) 次，無關的意思，也就是說恰好 C(n-1, i) == 0 mod m，不管 ai 為何皆不影響最後產生出來的數字。

為了加速運算，我們必須先質因數分解 m 的結果。

對於 C(a, b) = a! / (b!(b-a)!) 是否整除 m，查閱 m 的所有質因數 p 的個數是否符合需求。

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
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <string.h>
#include <assert.h>
using namespace std;
#define maxL (50000>>5)+1
#define GET(x) (mark[(x)>>5]>>((x)&31)&1)
#define SET(x) (mark[(x)>>5] |= 1<<((x)&31))
int mark[maxL];
int P[5500], Pt = 0;
void sieve() {
    register int i, j, k, l;
    SET(1);
    int n = 50000;
    for(i = 2; i <= n; i++) {
        if(!GET(i)) {
            for(j = i + i; j <= n; j += i)
                SET(j);
            P[Pt++] = i;
        }
    }
}
int isPrime(int n) {
    for(int i = 0; i < Pt && P[i] * P[i] <= n; i++) {
        if(n%P[i] == 0) {
            return 0;
        }
    }
    return 1;
}
vector< pair<int, int> > factor(int n) {
    vector< pair<int, int> > R;
    
    for(int i = 0, j; i < Pt && P[i] * P[i] <= n; i++) {
        if(n%P[i] == 0) {
            for(j = 0; n%P[i] == 0; n /= P[i], j++);
            R.push_back(make_pair(P[i], j));
        }
    }
    if(n != 1)	R.push_back(make_pair(n, 1));
    return R;
}
int g(int n, int p) {
    int ret = 0;
    long long pp = p;
    while (n >= pp) {
        ret += n / pp;
        pp *= p;
    }
    return ret;
}
int main() {
    sieve();
    int n, m;
    while (scanf("%d %d", &n, &m) == 2) {
        vector< pair<int, int> > f = factor(m);
        vector<int> solution;
        n--;
        for (int i = 0; i <= n; i++) {
            int ok = 1;
            for (int j = 0; j < f.size() && ok; j++) {
                int p = f[j].first;
                int cnt = g(n, p) - g(i, p) - g(n - i, p); // C(n, i) has p^cnt.
                if (cnt < f[j].second) {
                    ok = 0;
                }
            }
            if (ok) {
                solution.push_back(i + 1);
            }
        }
        printf("%d\n", (int)solution.size());
        for (int i = 0; i < solution.size(); i++) {
            printf("%d%s", solution[i], i == solution.size() - 1 ? "" : " ");
        }
        puts("");
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 1594 - Ducci Sequence

Problem

將序列根據步驟轉換，是否會產生迴圈或者是回歸到 0。

Sample Input

1
2
3
4
5
6
7
8
9
4 
4 
8 11 2 7 
5 
4 2 0 2 0 
7 
0 0 0 0 0 0 0 
6 
1 2 3 1 2 3

Sample Output

1
2
3
4
ZERO 
LOOP 
ZERO 
LOOP

Solution

用 hash (RS hashing) 來壓縮一下儲存的方式，碰撞的機率應該是挺低的。

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
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <vector>
#include <assert.h>
#include <map>
#include <algorithm>
using namespace std;
int nextSeq(int A[], int n) {
    int B[32];
    A[n] = A[0];
    for (int i = 0; i < n; i++)
        B[i] = abs(A[i] - A[i+1]);
    for (int i = 0; i < n; i++)
        A[i] = B[i];
    return 1;
}
int main() {
    int testcase, n, A[32];
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        for (int i = 0; i < n; i++)
            scanf("%d", &A[i]);
        
        map<int, int> R;
        do {
            int ok = 1, hash = 0;
            int a = 63689, b = 378551;
            for (int i = 0; i < n; i++) {
                hash = hash * a + A[i], a = a * b;
                ok &= A[i] == 0;
            }
            if (ok) {
                puts("ZERO");
                break;
            }
            int &f = R[hash];
            if (f) {
                puts("LOOP");
                break;
            }
            f = 1;
        } while (nextSeq(A, n));
    }
    return 0;
}
/*
 4
 4
 8 11 2 7
 5
 4 2 0 2 0
 7
 0 0 0 0 0 0 0
 6
 1 2 3 1 2 3
 */
Read More +
解題區/解題區 - UVa

UVa 1590 - IP Networks

Problem

找在同一個區域的 IP 中的 IP 遮罩。

Sample Input

1
2
3
4
3 
194.85.160.177 
194.85.160.183 
194.85.160.178

Sample Output

1
2
194.85.160.176 
255.255.255.248

Solution

也就是說我們必須找到其最長共同前綴，知道共同前綴的長度直接輸出 1111111…111000。

用 trie 對於這一道題目，只會用到 0/1 兩種字符，也可以直接暴力掃描，用 trie 沒有甚麼特別快的好處。

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
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
using namespace std;
struct Trie {
    int n, label, dist;
    int link[2];
} Node[1048576];
int TrieSize;
int insertTrie(const char* str) {
    static int i, idx;
    for(i = idx = 0; str[i]; i++) {
        if(Node[idx].link[str[i]-'0'] == 0) {
            TrieSize++;
            memset(&Node[TrieSize], 0, sizeof(Node[0]));
            Node[TrieSize].label = TrieSize;
            Node[TrieSize].dist = i + 1;
            Node[idx].link[str[i]-'0'] = TrieSize;
        }
        idx = Node[idx].link[str[i]-'0'];
    }
    Node[idx].n ++;
    return Node[idx].label;
}
void binaryIP(const int ip[], char buf[]) {
    int idx = 0;
    for (int i = 0; i < 4; i++) {
        for (int j = 8 - 1; j >= 0; j--) {
            buf[idx++] = '0' + ((ip[i]>>j)&1);
        }
    }
    buf[idx] = '\0';
}
void getAllLCP(char buf[]) {
    int idx = 0, bidx = 0;
    do {
        int branch = 0, next = 0, c = 0;
        for (int i = 0; i < 2; i++) {
            if (Node[idx].link[i]) {
                branch++, next = Node[idx].link[i], c = i;
            }
        }
        if (branch != 1)
            break;
        buf[bidx++] = c + '0', idx = next;
    } while (true);
    buf[bidx] = '\0';
}
int main() {
    int n, ip[4];
    char bip[128];
    while (scanf("%d", &n) == 1) {
        TrieSize = 0;
        memset(&Node[0], 0, sizeof(Node[0]));
        for (int i = 0; i < n; i++) {
            scanf("%d.%d.%d.%d", &ip[0], &ip[1], &ip[2], &ip[3]);
            binaryIP(ip, bip);
            insertTrie(bip);
        }
        getAllLCP(bip);
        int m = (int)strlen(bip);
        for (int i = 0; i < 4; i++) {
            int bb = 0;
            for (int j = 8 - 1; j >= 0; j--) {
                if (i * 8 + 7 - j < m) {
                    if (bip[i * 8 + 7 - j] == '1') {
                        bb |= 1<<j;
                    }
                }
            }
            printf("%d%c", bb, i == 3 ? '\n' : '.');
        }
        for (int i = 0; i < 4; i++) {
            int bb = 0;
            for (int j = 8 - 1; j >= 0; j--) {
                if (i * 8 + 7 - j < m) {
                    bb |= 1<<j;
                }
            }
            printf("%d%c", bb, i == 3 ? '\n' : '.');
        }
    }
    return 0;
}
/*
 3
 194.85.160.177
 194.85.160.183
 194.85.160.178
*/
Read More +
解題區/解題區 - UVa

UVa 816 - Abbott's Revenge

Problem

給每一個路口的可行進方向，請問從起點到終點的最短路徑為何。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
SAMPLE
3 1 N 3 3
1 1 WL NR *
1 2 WLF NR ER *
1 3 NL ER *
2 1 SL WR NF *
2 2 SL WF ELF *
2 3 SFR EL *
0
NOSOLUTION
3 1 N 3 2
1 1 WL NR *
1 2 NL ER *
2 1 SL WR NFR *
2 2 SR EL *
0
END

Sample Output

1
2
3
4
5
SAMPLE
  (3,1) (2,1) (1,1) (1,2) (2,2) (2,3) (1,3) (1,2) (1,1) (2,1)
  (2,2) (1,2) (1,3) (2,3) (3,3)
NOSOLUTION
  No Solution Possible

Solution

忘記有可能起點和終點一樣，所以刷了不少 WA。

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
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <string.h>
using namespace std;
int g[32][32][4];
char dirName[1024] = "NESW";
const int dx[] = {-1, 0, 1, 0}; // N, E, S, W
const int dy[] = {0, 1, 0, -1};
void bfs(int sx, int sy, int sdir, int ex, int ey) {
    int visited[32][32][4] = {};
    int fdir[] = {-1, 1, 0}, tx, ty;
    queue<int> X, Y, D;
    pair<int, pair<int, int> > from[32][32][4];
    int ox = sx, oy = sy;
    sx += dx[sdir], sy += dy[sdir];
    X.push(sx), Y.push(sy), D.push(sdir);
    visited[sx][sy][sdir] = 1;
    from[sx][sy][sdir] = make_pair(-1, make_pair(-1, -1));
    while (!X.empty()) {
        sx = X.front(), X.pop();
        sy = Y.front(), Y.pop();
        sdir = D.front(), D.pop();
        if (sx == ex && sy == ey) {
            int tx, ty, dir;
            stack< pair<int, int> > stk;
            tx = sx, ty = sy, dir = sdir;
            while (tx >= 0) {
                stk.push(make_pair(tx, ty));
                int ttx = from[tx][ty][dir].second.first;
                int tty = from[tx][ty][dir].second.second;
                int tdd = from[tx][ty][dir].first;
                tx = ttx, ty = tty, dir = tdd;
            }
            stk.push(make_pair(ox, oy));
            int output = 0;
            while (!stk.empty()) {
                if (output%10 == 0) {
                    printf("\n ");
                }
                pair<int, int> pt = stk.top();
                stk.pop();
                printf(" (%d,%d)", pt.first, pt.second);
                output++;
            }
            puts("");
            return ;
        }
        for (int i = 0; i < 3; i++) {
            if (g[sx][sy][sdir]&(1<<i)) {
                int dir = (sdir + fdir[i] + 4)%4;
                tx = sx + dx[dir], ty = sy + dy[dir];
                if (visited[tx][ty][dir] == 0) {
                    visited[tx][ty][dir] = 1;
                    X.push(tx), Y.push(ty), D.push(dir);
                    from[tx][ty][dir] = make_pair(sdir, make_pair(sx, sy));
                }
            }
        }
    }
    printf("\n  No Solution Possible\n");
}
int main() {
    char testcase[1024], sdir[1024];
    int x, y, sx, sy, ex, ey;
    while (gets(testcase) && strcmp("END", testcase)) {
        memset(g, 0, sizeof(g));
        scanf("%d %d %s %d %d", &sx, &sy, sdir, &ex, &ey);
        while (scanf("%d", &x) == 1 && x) {
            scanf("%d", &y);
            char token[10];
            while (scanf("%s", token) == 1 && token[0] != '*') {
                int dir = find(dirName, dirName+4, token[0]) - dirName;
                int follow = 0;
                for (int i = 1; token[i]; i++) {
                    switch (token[i]) {
                        case 'L': follow |= 1; break;
                        case 'R': follow |= 2; break;
                        case 'F': follow |= 4; break;
                    }
                }
                g[x][y][dir] = follow;
            }
        }
        int dir = find(dirName, dirName+4, sdir[0]) - dirName;
        printf("%s", testcase);
        bfs(sx, sy, dir, ex, ey);
        while (getchar() != '\n');
    }
    return 0;
}
/*
SAMPLE
3 1 N 3 3
1 1 WL NR *
1 2 WLF NR ER *
1 3 NL ER *
2 1 SL WR NF *
2 2 SL WF ELF *
2 3 SFR EL *
0
NOSOLUTION
3 1 N 3 2
1 1 WL NR *
1 2 NL ER *
2 1 SL WR NFR *
2 2 SR EL *
0
END
 
 
 SAMPLE
 3 1 N 3 3
 1 1 WL NR *
 1 2 WLF NR ER *
 1 3 NL ER *
 2 1 SL WR NF *
 2 2 SL WF ELF *
 2 3 SFR EL *
 0
 NOSOLUTION
 3 1 N 3 2
 1 1 WL NR *
 1 2 NL ER *
 2 1 SL WR NFR *
 2 2 SR EL *
 0
 MyMaze 1
 3 1 N 1 1
 0
 MyMaze 2
 3 1 N 3 1
 0
 MyMaze 3
 3 1 N 2 1
 0
 MyMaze 4
 2 2 W 3 2
 1 1 NR *
 1 2 ER *
 2 1 WR *
 2 2 SF *
 0
 MyMaze 5
 2 2 N 2 3
 1 1 WL *
 1 2 NL *
 2 1 SF *
 2 2 NR *
 3 1 SL *
 3 2 EL *
 0
 Circle
 2 1 N 2 1
 1 1 NR *
 1 2 ER *
 2 2 SF *
 3 1 WR *
 3 2 SR *
 0
 Robert Abbott's Atlanta Maze
 4 2 N 4 3
 1 1 NR WL *
 1 2 NLR WF EFR *
 1 3 EFR WFR NL *
 1 4 ER NL *
 2 1 SFL WL NFR *
 2 2 EL SFLR WFRL NFL *
 2 3 EFLR SF NF WFRL *
 2 4 SR ELR NF *
 3 1 WR SL *
 3 2 EFL SLR WR NF *
 3 3 EFL SLR WL *
 3 4 EL SR *
 0
 END
 */
Read More +
解題區/解題區 - UVa

UVa 721 - Invitation Cards

Problem

ACM 參賽選手要到比賽會場，公車都是單向運行，求選手們來回的最少花費。

給一個有向圖，求從編號 1 到所有點的最短路徑總和，以及所有點到編號 1 的最短路徑總和。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
2
2 2
1 2 13
2 1 33
4 6
1 2 10
2 1 60
1 3 20
3 4 10
2 4 5
4 1 50

Sample Output

1
2
46
210

Solution

對一開始給定的圖，從編號 1 做一次 SSSP (單源最短路徑)，隨後再對題目給的反向圖做一次 SSSP 即可以得到所有點到編號 1 的最短路徑。

這一題很類似於 zerojudge 的地道問題。

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
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
#define MAXN 1048576
vector< pair<int, long long> > g[MAXN], invg[MAXN];
long long dist[MAXN];
int inq[MAXN];
long long spfa(int source, int n, vector< pair<int, long long> > g[]) {
    for (int i = 0; i < n; i++) {
        dist[i] = 1LL<<60, inq[i] = 0;
    }
    queue<int> Q;
    int u, v;
    long long w;
    Q.push(source), dist[source] = 0;
    while (!Q.empty()) {
        u = Q.front(), Q.pop();
        inq[u] = 0;
        for (int i = 0; i < g[u].size(); i++) {
            v = g[u][i].first, w = g[u][i].second;
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                if (!inq[v]) {
                    Q.push(v), inq[v] = 1;
                }
            }
        }
    }
    long long ret = 0;
    for (int i = 0; i < n; i++) {
        ret += dist[i];
    }
    return ret;
}
int main() {
    int testcase, N, M;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &N, &M);
        for (int i = 0; i < N; i++) {
            g[i].clear(), invg[i].clear();
        }
        for (int i = 0; i < M; i++) {
            int x, y, c;
            scanf("%d %d %d", &x, &y, &c);
            x--, y--;
            g[x].push_back(make_pair(y, c));
            invg[y].push_back(make_pair(x, c));
        }
        long long ret = 0;
        ret += spfa(0, N, g);
        ret += spfa(0, N, invg);
        printf("%lld\n", ret);
    }
    return 0;
}
/*
 2
 2 2
 1 2 13
 2 1 33
 4 6
 1 2 10
 2 1 60
 1 3 20
 3 4 10
 2 4 5
 4 1 50
*/
Read More +
解題區/解題區 - UVa

UVa 561 - Jackpot

Problem

拉霸遊戲，給你每一個輪子上的情況，而你可以可以看到每個輪子的連續三個可視範圍。

可視範圍構成的 3 x 3 區塊，

  • 如果上面一排都是相同元素，則獎金累加 5 元
  • 如果下面一排都是相同元素，則獎金累加 5 元
  • 如果中間一排都是相同元素，則獎金累加 10 元
  • 如果左上到右下的對角線上都是相同元素，則獎金累加 7 元
  • 如果右上到左下的對角線上都是相同元素，則獎金累加 7 元

求轉動一次的期望獎金為何

Sample Input

1
2
3
4
5
6
7
8
9
2
3 4 6
AAB
BABA
BBAAAB
12 15 18
CCCCCCCCCCCC
CCCCCCCCCCCCCCC
CCCCCCCCCCCCCCCCCC

Sample Output

1
2
8.5000
34.0000

Problem

直接窮舉每一種字符的機率於每一個位置即可。

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
#include <stdio.h>
#include <math.h>
#include <iostream>
using namespace std;
int main() {
    int testcase;
    int A, B, C;
    char sa[1024], sb[1024], sc[1024];
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d %d", &A, &B, &C);
        scanf("%s %s %s", sa, sb, sc);
        int cntA[26] = {}, cntB[26] = {}, cntC[26] = {};
        for (int i = 0; sa[i]; i++) {
            cntA[sa[i] - 'A']++;
        }
        for (int i = 0; sb[i]; i++) {
            cntB[sb[i] - 'A']++;
        }
        for (int i = 0; sc[i]; i++) {
            cntC[sc[i] - 'A']++;
        }
        double ret = 0;
        for (int i = 0; i < 26; i++) {
            ret += cntA[i] * cntB[i] * cntC[i] * 7.0 / A/ B/ C * 2;
            ret += cntA[i] * cntB[i] * cntC[i] * 10.0 / A/ B/ C;
            ret += cntA[i] * cntB[i] * cntC[i] * 5.0 / A/ B/ C * 2;
        }
        printf("%.4lf\n", ret);
    }
    return 0;
}
/*
 2
 3 4 6
 AAB
 BABA
 BBAAAB
 12 15 18
 CCCCCCCCCCCC
 CCCCCCCCCCCCCCC
 CCCCCCCCCCCCCCCCCC
*/
Read More +
解題區/解題區 - UVa

UVa 560 - Magic

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
*/
Read More +
解題區/解題區 - UVa

UVa 358 - Don't Have A Cow

Problem

有一個半徑為 R 的圓草地，接著將一頭牛綁在圓周上 (定點)，請問繩長多少的時候，恰好能夠將圓佔有 P% 的面積。

Sample input

1
2
1
100 0.33

Sample output

1
R = 100, P = 0.33, Rope = 13.24

Solution

將圓放在坐標軸上，假設綁定的位置於 (R, 0)，而接著二分另外一點 (於圓上) 可以拉到綁定的位置。

計算繩長和面積即可。

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
#include <stdio.h>
#include <math.h>
#include <iostream>
using namespace std;
#define eps 1e-8
int main() {
    int testcase;
    double R, P;
    const double pi = acos(-1);
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%lf %lf", &R, &P);
        double l = 0, r = pi, mid, ret = 0;
        double A = R * R * pi;
        while (fabs(l - r) > eps) {
            mid = (l + r)/2;
            ret = hypot(R * cos(mid) - R, R * sin(mid));
            double theta = (pi - mid)/2;
            double area = (ret * ret * theta/2 + (R * R * mid/2 - R * R * sin(mid)/2))*2;
            if (area < A * P)
                l = mid;
            else
                r = mid;
        }
        printf("R = %.0lf, P = %.2lf, Rope = %.2lf\n", R, P, ret);
        if(testcase)
            puts("");
    }
    return 0;
}
/*
*/
Read More +
解題區/解題區 - UVa

UVa 12654 - Patches

Problem

輪胎上有數個洞需要補丁，只有兩種補丁，每個補丁長度不同，求用總長度最少的補丁覆蓋所有的洞。

Sample Input

1
2
3
4
5
6
7
8
9
10
5 20 2 3
2 5 8 11 15
4 20 12 9
1 2 3 13
2 10 3 2
0 9
2 10 3 2
0 2
2 10 3 2
0 3

Sample Output

1
2
3
4
5
8
12
2
2
3

Solution

這一題最麻煩就是處理環的部分，事實上我們可以窮舉補丁的起始位置，然後針對這一個位置進行 O(n) 計算 DP 最小值。

因此最後能在 O(n^2) 完成，為了簡化計算，直接對陣列的 rotate shift left 操作。

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
#include <stdio.h>
#include <algorithm>
using namespace std;
int F[1024];
int main() {
    int N, C, T[2];
    while(scanf("%d %d %d %d", &N, &C, &T[0], &T[1]) == 4) {
        for(int i = 0; i < N; i++)
            scanf("%d", &F[i]);
        sort(F, F+N);
        int ret = 0x3f3f3f3f;
        for(int i = 0; i < N; i++) {
            int dp[1024] = {};
            for(int j = 0; j <= N; j++)
                dp[j] = 0x3f3f3f3f;
            dp[0] = 0;
            int cover1 = 0, cover2 = 0;
            for(int j = 0; j < N; j++) {
                while(cover1 + 1 < N && F[cover1 + 1] - F[j] <= T[0])
                    cover1++;
                while(cover2 + 1 < N && F[cover2 + 1] - F[j] <= T[1])
                    cover2++;
                dp[cover1+1] = min(dp[cover1+1], dp[j] + T[0]);
                dp[cover2+1] = min(dp[cover2+1], dp[j] + T[1]);
            }
            ret = min(ret, dp[N]);
            swap(F[0], F[N]);
            F[N] += C;
            for(int j = 0; j < N; j++)
                F[j] = F[j+1];
        }
        printf("%d\n", ret);
    }
    return 0;
}
/*
5 20 2 3
2 5 8 11 15
4 20 12 9
1 2 3 13
2 10 3 2
0 9
2 10 3 2
0 2
2 10 3 2
0 3
*/
Read More +