解題區/解題區 - UVa

UVa 11828 - Palindrome Again

Problem

You are given a string S of length N. Can you find a string P which satisfies the following conditions?

  1. Length of P will be N

  2. Distance between S and P will be less than or equal to K

  3. P will be a palindrome.

  4. P can contain only characters ‘a’, ‘b’, …, ‘z’

You have to calculate, in how many ways you can choose P. This number can be very large, so print the answer modulo 1000000000 (109).

Notes:

  • A string is a sequence of characters. For this problem consider that all strings can contain only ‘a’, ‘b’, …, ‘z’, i.e. 26 available characters.

  • The length of the string is defined by the number of characters in the string. For example, length of “abcba” is 5.

  • A string is called palindrome when it is the same string when written from forwards or backwards. For example – “abcba”, “abba”, “a” are palindrome but “abc” is not a palindrome.

  • Distance between two string of same length is the number of mismatches of corresponding characters. For example, distance between “abcb” and “bcba” is 4 because no character of first string matches to the character of the corresponding index of second string, but distance between “abc” and “cba” is 2.

    Input

Input starts with an integer T (T is around 5000), the number of test cases.

Each test case consists of two lines. First line contains two integers N(1≤N≤1000) and K (0≤K≤1000). Second line contains a string S of length N. S contains only characters from ‘a’, ‘b’, …, ‘z’.

Output

For each test case output the number of test cases followed by the number of ways the string can be chosen modulo 1000000000 (109). See sample output for exact format.

Sample Input

1
2
3
4
5
6
7
3
3 2
kxk
4 1
addc
4 3
addc

Output for Sample Input

1
2
3
Case 1: 51
Case 2: 2
Case 3: 76

Solution

題目描述：

對一個 S 字串，修改最多 K 個字符的情況下，求最多有多少不同的字符串是迴文

題目解法：

最樸素的算法，對於每個字串 S，使用 O(NK) 的算法，利用 dp[N][K] 表示對於前綴長為 N，已經修改了 K 個字符的總數為何。

先來看最樸素的寫法，一定會拿 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
// TLE
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <ctype.h>
using namespace std;
int main() {
    int testcase, cases = 0, N, K;
    char s[1024];
    long long dp[2][1024];
    long long mod = 1000000000LL;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d %d %s", &N, &K, s);
        memset(dp, 0, sizeof(dp));
        dp[0][0] = 1;
        int froll = 0, L = N/2 + N%2;
        for(int i = 0; i < N; i++)
            s[i] = tolower(s[i]);
        for(int i = 0; i < L; i++) {
            memset(dp[!froll], 0, sizeof(dp[!froll]));
            int diff, cos;
            diff = s[i] == s[N - i - 1] ? 0 : 1;
            cos = i == N - i - 1 ? 1 : 2;
            for(int j = 0; j <= K; j++) {
                if(diff) {
                    dp[!froll][j + 2] += dp[froll][j] * 24;
                    dp[!froll][j + 1] += dp[froll][j] * 2;
                } else {
                    dp[!froll][j + cos] += dp[froll][j] * 25; // using diff
                    dp[!froll][j] += dp[froll][j];
                }
                dp[!froll][j] %= mod;
            }
            froll = !froll;
        }
        long long ret = 0;
        for(int i = 0; i <= K; i++)
            ret = (ret + dp[froll][i])%mod;
        printf("Case %d: %lld\n", ++cases, ret);
    }
    return 0;
}

之後，仔細拆解之後，發現由於只會考慮字串的一半，並且條件分為兩種，原本就已經匹配還是沒有匹配，而事實上我們可以分成 P, Q 兩種形式。

  • P = number of characters where a[i] = a[n-i-1];
  • Q = number of characters where a[i] != a[n-i-1];

所以考慮預先建表，將這兩個事件獨立分開計算，最後乘積起來就可以了。

對於 P, Q 的情況，分別建立 dp(i, j) 為目前 i 個字符，恰好修改 j 次的迴文字串數量。但是題目要求為 最多修改 K 次，因此對 P, Q 其中一種進行調整為 dp(i, j) 為目前 i 個字符，修改最多 j 次的回文字串數量。

因此對於每次詢問，可以在 O(N) 時間內完成。

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 <string.h>
#include <algorithm>
#include <ctype.h>
using namespace std;
long long dp1[1024][1024], dp2[1024][1024];
long long mod = 1000000000LL;
/*
P= number of characters where a[i] = a[n-i-1];
Q= number of characters where a[i] != a[n-i-1];
*/
long long solve(int P, int Q, int K) {
    long long ret = 0;
    for(int i = 0; i <= K; i++)
        ret = (ret + dp1[P][i] * dp2[Q][K - i])%mod;
    return ret;
}
int main() {
    dp1[0][0] = dp2[0][0] = 1;
    // dp1(P, K), dp2(Q, K)
    for(int i = 1; i < 1024; i++) {
        for(int j = 0; j < 1024; j++) {
            if(j >= 2)
                dp1[i][j] += dp1[i - 1][j - 2] * 25;
            dp1[i][j] += dp1[i - 1][j];
            if(j >= 1)
                dp2[i][j] += dp2[i - 1][j - 1] * 2;
            if(j >= 2)
                dp2[i][j] += dp2[i - 1][j - 2] * 24;
            dp1[i][j] %= mod, dp2[i][j] %= mod;
        }
    }
    // 
    for(int i = 0; i < 1024; i++) {
        for(int j = 1; j < 1024; j++)
            dp2[i][j] = (dp2[i][j] + dp2[i][j-1])%mod;
    }
    
    int testcase, cases = 0, N, K;
    char s[1024];
    
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d %d %s", &N, &K, s);
        int P = 0, Q = 0;
        for(int i = 0; i < N/2; i++) {
            P += s[i] == s[N - i - 1];
            Q += s[i] != s[N - i - 1];
        }
        long long ret = 0;
        if(N&1)
            ret = (solve(P, Q, K) + solve(P, Q, K - 1) * 25) %mod;
        else
            ret = solve(P, Q, K);
        printf("Case %d: %lld\n", ++cases, ret);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 11802 - All Your Bases Belong to Us

It is very easy to find number of trailing zero in n! for a particular base b. In this problem you have to do the reverse. You have to find for how many bases b, n! has k trailing zeros in base b.

Input

Input starts with a positive number T≤10000, denoting the number of test cases to follow.

Each test case contains two non-negative integers, n≤1015 and 1≤k≤1015 in a line. You may assume and n/k<500.
Output

For each input output one line containing the number of different bases. Print the solution modulo 1000000007

Sample Input

1
2
3
4
5
6
5
10 2
10 3
10 4
10 5
10 8

Sample Output

1
2
3
4
5
Case 1: 24
Case 2: 0
Case 3: 4
Case 4: 0
Case 5: 1

Solution

題目描述：

對於 n! 的 b 進制數中，尾數恰好為 k 個 0 情況為何？

題目解法：

質因數分解，找到每一個質數的次方數，根據數學組合和排容原理得到，大於等於 k 個 0 的基底情況個數為何，因此

對於 2^n1 * 3^n2 * 5^n3 * 7^n4 ... = n!，

base = pi^mi * ...，保證 (pi^mi)^k => mi * k <= ni。計算 mi (0, 1, …, ni/k)的可能情況總數乘積即可。

最後用排容原理吧！

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
 
#include <stdio.h>
#include <stdlib.h>
#define LL long long
#define maxL (10000>>5)+1
#define GET(x) (mark[x>>5]>>(x&31)&1)
#define SET(x) (mark[x>>5] |= 1<<(x&31))
using namespace std;
int mark[maxL];
int P[5050], Pt = 0;
void sieve() {
    register int i, j, k;
    SET(1);
    int n = 10000;
    for(i = 2; i < n; i++) {
        if(!GET(i)) {
            for(k = n/i, j = i*k; k >= i; k--, j -= i)
                SET(j);
            P[Pt++] = i;
        }
    }
}
int main() {
    sieve();
    const long long mod = 1000000007LL;
    int testcase, cases = 0;
    long long N, K;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%lld %lld", &N, &K);
        long long ret1 = 1, ret2 = 1;
        for(int i = 0; i < Pt; i++) {
            long long p = P[i], cnt = 0;
            while(p <= N)
                cnt += N / p, p *= P[i];
            if(cnt < K)
                break;
            ret1 *= cnt/K + 1;
            ret2 *= cnt/(K+1) + 1;
            ret1 %= mod;
            ret2 %= mod;
        }
        printf("Case %d: %lld\n", ++cases, ((ret1 - ret2)%mod + mod)%mod);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 11785 - Hypercube

Problem

In geometry, a hypercube is an n-dimensional analogue of a square (n = 2) and a cube (n = 3). It consists in groups of opposite parallel line segments aligned in each of the space’s dimensions, at right angles to each other and of the same length. An n-dimensional hypercube is also called an n-cube.

\epsfbox{p11785.eps}

In parallel computing, the vertexes are processors, and the line segments (edges) represent connections. The n-cube architecture has the following properties:

  • Each node has n connections with different processors.
  • Each processor has a unique identifier, between 0 and 2n - 1.
  • Two processors are directly connected if and only if their identifiers differ in just one bit. For instance, in a 3-cube, processors 3 (011 in binary) and 7 (111 in binary) are directly connected.
  • The number of processors is 2n

The new company WEFAIL is designing hypercubes, but they are always contracting new people, whose do not know all the hypercube properties, and sometimes they fail; thus these properties are not satisfied in all cases. Given an arbitrary graph, your task is to write a program that determines whether the graph is a hypercube or not.

Input

The input consists in several problem instances. Each instance contains one graph, which starts with a line with two positive integers: K and M, representing the number of vertexes ( 0 < K$\le$1024) and the number of edges respectively. It follows ( 0$\le$M$\le$5130) lines, representing the edges. Each edge is given by two 32 bits integers, representing the processors connected by the edge.

The end of input is indicated by a test case with K = 0.

Output

For each problem instance, the output is a single line, with the word YES if the corresponding graph is a hypercube, and NO otherwise (quotes for clarity). The output must be written to standard output.

Sample Input

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

Sample Output

1
2
3
YES
NO
NO

Solution

題目描述：

判斷是否與超立方體同構

題目解法：

原本使用貪心的映射方式，然後進行超立方體的判斷，但是這樣的條件不好撰寫，其中肯定有 BUG。

最後使用全局最短路總和會相同的方式，還真是各種邪惡的題目。然而題目假使會有超出節點的編號，直接忽略報錯即可。

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
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
#include <string.h>
using namespace std;
vector<int> g[1024];
int bfs(int n) {
    int visited[1024] = {};
    int u, v, ret = 0;
    queue<int> Q;
    Q.push(0), visited[0] = 1;
    while(!Q.empty()) {
        u = Q.front(), Q.pop();
        for(int i = 0; i < g[u].size(); i++) {
            v = g[u][i];
            if(visited[v] == 0) {
                visited[v] = visited[u] + 1;
                ret += visited[u];
                Q.push(v);
            }
        }
    }
    return ret;
}
int main() {
    int n, m, x, y;
    while(scanf("%d %d", &n, &m) == 2 && n+m) {
        for(int i = 0; i < n; i++)
            g[i].clear();
        int size = 0, eflag = 0;
        for(int i = 0; i < m; i++) {
            scanf("%d %d", &x, &y);
            if(x >= 0 && x < n && y >= 0 && y < n) {
                g[x].push_back(y);
                g[y].push_back(x);
            } else {
                eflag = 1;
            }
        }
        for(m = 0; (1<<m) < n; m++);
        for(int i = 0; i < n; i++)
            if(g[i].size()%m)
                eflag = 1;
        if((n&(-n)) != n || eflag) {
            puts("NO");
            continue;
        }
        int ret = 0, ac = 0;
        for(int i = 0; i < n; i++)
            ret += bfs(i);
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                int t = i^j;
                ac += __builtin_popcount(t);
            }
        }
        puts(ret == ac ? "YES" : "NO");
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 11766 - Racing Car Computer

Problem

The racing cars of today are equipped with so many sophisticated equipment. Introduction of a new visual transducer which is interfaced with the on-board computer can tell you on the fly how many cars are ahead of you while how many are trailing. There are N cars on a racing track. Each has an on-board computer with the new feature. During the race, every single car’s computer keeps displaying two integers, a (The number of cars in front of him) & b (The number of cars behind him) for a particular moment. It is possible that at some time, some of the cars are racing side by side i.e. they are exactly at the same location. A car will not consider any other car at the same location to be a leading or trailing car.

Now, it is suspected that some of the new transducers are not working properly inside such high speed vehicles. The report with all computers’ data generated at a particular timestamp is reported to you. You are to determine the minimum number of cars that have faulty data.

Input

Each test case begins with an integer N (1<=N<=1000), the number of cars on a track . The next N lines each has two integers - a & b (0<=a,b<=1500) for a particular car.

The last test case is followed by a line with a single 0 indicating the end of input.

Output

For each test case, print a line in the format, “Case X: Y”, where X is the case number & Y is the minimum number of cars that must have faulty data according to the report.

Sample Input

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

Output for Sample Input

1
2
Case 1: 3
Case 2: 1

Solution

題目描述：

有n个人进行比赛，给出每个人的状况，a表示这个人前面有a个人，b表示说这个人后面有b个人。问说最少有多少个人的状态是不成立的。

題目解法：

將問題轉換成區間，來表示這個人可能所在的區間，假使前面有 a 個人，後面有 b 個人，則這個人可能所在為 [a+1, n-b]，我們允許區間內最高容量為 n - b - a (當作權重) 個人，求不相交區間的最大權重。

最後 n 扣除這個最大權重就是答案。

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
#include <stdio.h>
#include <map>
#include <algorithm>
using namespace std;
int main() {
    int n, cases = 0;
    int a, b;
    while(scanf("%d", &n) == 1 && n) {
        map<int, int> R[1024];
        for(int i = 0; i < n; i++) {
            scanf("%d %d", &a, &b);
            if(a + b >= n)
                continue;
            int &ww = R[a+1][n-b];
            ww = min(ww + 1, n - a - b);
        }
        int ret = 0, dp[1024] = {};
        for(int i = 0; i <= n; i++) {
            if(i)
                dp[i] = max(dp[i], dp[i-1]);
            for(map<int, int>::iterator it = R[i+1].begin();
                it != R[i+1].end(); it++)
                dp[it->first] = max(dp[it->first], dp[i] + it->second);
            ret = max(ret, dp[i]);
        }
        printf("Case %d: %d\n", ++cases, n - ret);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 11765 - Component Placement

Problem

In circuit design, component placement is an important step in the design automation. Inferior placements may affect the performance and manufacturing cost.

You are given a PCB (Printed Circuit Board). It’s a large green board. You can place components on either side of the PCB. However, cost of placing a component on both sides are not the same. You are given N components. For each component ci, cost of placing it on the top layer is Xi and on the bottom layer is Yi.

These components may interact with each other. If both the components are on the same side of the PCB, the interconnection cost is negligible. But, if they are on different sides, their interconnection is costly. For each such interconnection j, the cost will be Zj.

Finally, some design issues restricts some components to be on the top side or bottom side. Now, find the minimum cost to place the components.

Input

First line contains a positive integer T (T<= 50) that denotes the number of test cases.

Each test case starts with 2 integers N (1 <= N <= 200) and M (0 <= M <= 100000, M <= N * (N-1) / 2), the number of components and number of interconnections. This will be followed by N integers in a line, each between 1 and 10000000 (inclusive), where i-th of it describes the cost of placing the component on the top layer. The next line contains N more integers, each between 1 and 10000000 (inclusive), where i-th of it denotes the cost of placing it on the bottom layer. The next line contains N more integers, each will be either 0, -1 or +1, where

  • -1 means i-th component can only be placed on the bottom
  • +1 means i-th component can only be placed on the top
  • 0 means the component can be placed on either side

Then there will be M lines, each containing three integers, p, q, and r (1 <= p, q <= N, 1 <= r <= 10000000), denoting that, p and q-th component has to be interconnected and if they are on different layers, the cost of interconnection will be r. There will be at most one interconnection between any pair or components.

Output

For each test case, output the minimum cost to place the components.

Sample Input

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
5
4 0
5 6 7 8
8 7 6 5
0 0 0 0
4 2
5 6 7 8
8 7 6 5
0 0 0 0
1 3 10
2 4 10
4 3
5 6 7 8
8 7 6 5
0 0 0 0
1 3 10
2 4 10
2 3 1
4 3
5 6 7 8
30 31 32 33
0 0 0 0
1 3 10
2 4 10
2 3 1
4 3
5 6 7 8
8 7 6 5
-1 0 0 1
1 2 10
3 4 10
2 3 1

Output for Sample Input

1
2
3
4
5
22
24
25
26
31

Solution

題目描述：

有一些元件，設置在電路板上面時，要不放上面或者是放下面，放置的成本各有不同，假如兩個元件之間必須相連，則當他們放置在不同側的時候，會有額外的花費，如果放在同側則無需考慮。

求放置的最小成本。

題目解法：

利用最大流 = 最小割的方式，將不同側的成本反應在最小割上面。

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
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
using namespace std;
struct Node {
    int x, y, v;// x->y, v
    int next;
} edge[100005];
int e, head[505], prev[505], record[505];
int level[505], visited[505];
void addEdge(int x, int y, int v) {
    edge[e].x = x, edge[e].y = y, edge[e].v = v;
    edge[e].next = head[x], head[x] = e++;
    edge[e].x = y, edge[e].y = x, edge[e].v = 0;
    edge[e].next = head[y], head[y] = e++;
}
bool buildLevelGraph(int s, int t) {
    memset(level, 0, sizeof(level));
    queue<int> Q;
    Q.push(s), level[s] = 1;
    while(!Q.empty()) {
        int tn = Q.front();
        Q.pop();
        for(int i = head[tn]; i != -1; i = edge[i].next) {
            int y = edge[i].y;
            if(edge[i].v > 0 && level[y] == 0) {
                level[y] = level[tn] + 1;
                Q.push(y);
            }
        }
    }
    return level[t] > 0;
}
int constructBlockingFlow(int s, int t) {
    int ret = 0;
    stack<int> stk;
    memset(visited, 0, sizeof(visited));
    stk.push(s);
    while(!stk.empty()) {
        int now = stk.top();
        if(now != t) {
            for(int i = head[now]; i != -1; i = edge[i].next) {
                int y = edge[i].y;
                if(visited[y] || level[y] != level[now] + 1)
                    continue;
                if(edge[i].v > 0) {
                    stk.push(y), prev[y] = now, record[y] = i;
                    break;
                }
            }
            if(stk.top() == now)
                stk.pop(), visited[now] = 1;
        } else {
            int flow = 1e+9, bottleneck;
            for(int i = t; i != s; i = prev[i]) {
                int ri = record[i];
                flow = min(flow, edge[ri].v);
            }
            for(int i = t; i != s; i = prev[i]) {
                int ri = record[i];
                edge[ri].v -= flow;
                edge[ri^1].v += flow;
                if(edge[ri].v == 0)
                    bottleneck = prev[i];
            }
            while(!stk.empty() && stk.top() != bottleneck)
                stk.pop();
            ret += flow;
        }
    }
    return ret;
}
int maxflowDinic(int s, int t) {
    int flow = 0;
    while(buildLevelGraph(s, t))
        flow += constructBlockingFlow(s, t);
    return flow;
}
int main() {
    int n, m, testcase;
    int U[1024], D[1024], kind, x, y, v;
    scanf("%d", &testcase);
    while(testcase--) {
        e = 0;
        memset(head, -1, sizeof(head));
        
        scanf("%d %d", &n, &m);
        for(int i = 0; i < n; i++)
        	scanf("%d", &U[i]);
        for(int i = 0; i < n; i++)
        	scanf("%d", &D[i]);
    	
    	int source = n + 1, sink = source + 1;
    	const int INF = 0x3f3f3f3f;
        for(int i = 0; i < n; i++) {
        	scanf("%d", &kind);
        	if(kind == 0) {
        		addEdge(source, i, U[i]);
        		addEdge(i, sink, D[i]);
        	} else if(kind == 1) {
        		addEdge(source, i, U[i]);
        		addEdge(i, sink, INF);
        	} else {
        		addEdge(source, i, INF);
        		addEdge(i, sink, D[i]);
        	}
        }
        for(int i = 0; i < m; i++) {
        	scanf("%d %d %d", &x, &y, &v);
        	x--, y--;
        	addEdge(x, y, v);
        	addEdge(y, x, v);
        }
        printf("%d\n", maxflowDinic(source, sink));
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 11754 - Code Feat

題目描述：

找前 S 小的 M 符合取模結果存在於給定的集合。

題目解法：

對於取模結果窮舉，可以在 O(n)時間內利用中國餘式定理得到其最小解，但是如果窮舉情況太多，倒不如直接窮舉數字。

特別小心，M > 0 的條件，為了除去這個 bug，花了不少時間。

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
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <iostream>
#include <string.h>
#include <set>
#include <queue>
#include <algorithm>
using namespace std;
// #define DEBUG
long long inv(long long n, long long m) { // get n*? = 1 (mod m)
    long long la = 1, lb = 0, ra = 0, rb = 1;
    long long i = 0, t, mod = m;
    while(n%m) {
        if(!i) {
            la -= n/m*ra;
            lb -= n/m*rb;
        } else {
            ra -= n/m*la;
            rb -= n/m*lb;
        }
        i = !i;
        t = n, n = m, m = t%m;
    }
    return i ? (la%mod+mod)%mod : (ra%mod+mod)%mod;
}
int X[1024], Xn[1024], C, S, a[1024];
long long Y[1024][128];
vector<long long> solution;
long long chinese_remainder(int n, int m[], int a[]) {
    long long M = 1, ret = 0;
    for(int i = 0; i < n; i++)
        M *= m[i];
    for(int i = 0; i < n; i++) {
        ret += a[i] * inv(M/m[i], m[i]) %M * M/m[i];
        ret %= M;
    }
    return (ret%M + M)%M;
}
void dfs(int idx) {
    if(idx == C) {
        long long smallest = chinese_remainder(C, X, a);
        solution.push_back(smallest);
        return ;
    }
    for(int i = 0; i < Xn[idx]; i++) {
        a[idx] = Y[idx][i];
        dfs(idx+1);
    }
}
void test(int C, int res) {
    printf("[%d] ", res);
    for(int i = 0; i < C; i++) {
        printf("%d: %d, ", X[i], res%X[i]);
    }
    puts("");
}
int main() {
    while(scanf("%d %d", &C, &S) == 2 && C + S) {
        set<long long> remainder[1024];
        for(int i = 0; i < C; i++) {
            scanf("%d %d", &X[i], &Xn[i]);
            for(int j = 0; j < Xn[i]; j++)
                scanf("%lld", &Y[i][j]), remainder[i].insert(Y[i][j]);
            sort(Y[i], Y[i] + Xn[i]);
        }
        solution.clear();
        long long o = 1, M = 1;
        for(int i = 0; i < C; i++) {
            o *= Xn[i], M *= X[i];
        }
        if(o < 10000) {
            dfs(0);
            sort(solution.begin(), solution.end());
            for(int i = 0, ratio = 0; i < S; ratio++) {
                for(int j = 0; j < solution.size() && i < S; j++) {
                    long long mn = solution[j] + ratio * M;
                    if(mn == 0)
                        continue;
                    printf("%lld\n", mn);
                    i++;
                }
            }
        } else {
            int base = 0;
            for(int i = 0; i < C; i++)
                if(X[base] * Xn[i] < X[i] * Xn[base])
                    base = i;
            for(int i = 0, ratio = 0; i < S; ratio++) {
                for(int j = 0; j < Xn[base] && i < S; j++) {
                    long long mn = (long long) ratio * X[base] + Y[base][j];
                    if(mn == 0) continue;
                    int f = 1;
                    for(int k = 0; k < C; k++)
                        f &= remainder[k].find(mn%X[k]) != remainder[k].end();
                    if(f) {
                        printf("%lld\n", mn);
                        i++;
                    }
                }
            }
        }
        puts("");
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 11751 - Installing Diagnostic Software

You have recently been appointed as the administrator for a wired network of devices. Unfortunately, your predecessor used very poor quality lines to connect the devices. The board of executives is currently deciding if they want to fund an upgrade to a wireless network, or simply replace the existing wires with ones of better quality. As expected, this decision is being weighed down with bureaucratic nonsense; it looks like it will take some time before anything is approved.

Meanwhile, you still have to deal with the problem at hand. You have access to an antiquated version of Newton Network Monitor which is a software package that, once installed on a machine, will monitor all lines connected to that machine and immediately alert the user when a line has failed. This should help reduce your response time to any failures.

Your task is to install the software on some machines so each line is being monitored by at least one of its endpoint devices. For various technical reasons, the time it takes to install the software varies from device to device so you want to minimize the total amount of time spent installing the software. You cannot install on more than one machine at a time (since you only have one copy of the software) meaning the total time spent installing the software is exactly the sum of the installation times on each machine.

Input Format

Each input case begins with two numbers n,m with 1 ≤ n ≤ 1,000 and 0 ≤ m ≤ 25,000. Following this are m pairs of distinct integers between 0 and n-1 which describe a wire connecting the two devices. The time spent installing the software on machine numbered i is 2i. The input is terminated with n = m = 0; this should not be processed.
Output Format

For each input case, there is to be one line of output containing a sequence of n bits with no spaces. The i’th bit is 1 if the software is installed on machine i, and 0 if not.

Sample Input

1
2
3
4
5
6
3 2
0 2
1 2
3 1
1 2
0 0

Sample Output

1
2
110
010

Solution

題目描述：

給定一個 N 個點的城市和邊，每一條邊上至少有一個點安裝服務，而在編號 i 的地方設置服務器成本為 $2^{i}$，求最少花費。

題目解法：

明顯地，會發現對於編號最大的節點來說，周遭的點數全設置也不會比該點設置來得高，那還不如將周圍都設置服務。藉此，從編號大的開始檢查，如果還沒有設置服務，將其鄰居全都設置服務！

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
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <queue>
#include <string.h>
using namespace std;
vector<int> g[1024];
int main() {
    int n, m, x, y;
    while(scanf("%d %d", &n, &m) == 2 && n + m) {
        for(int i = 0; i < n; i++)
            g[i].clear();
        for(int i = 0; i < m; i++) {
            scanf("%d %d", &x, &y);
            g[x].push_back(y);
            g[y].push_back(x);
        }
        int used[1024] = {};
        for(int i = n - 1; i >= 0; i--) {
            if(used[i])	continue;
            for(int j = 0; j < g[i].size(); j++)
                used[g[i][j]] = 1;
        }
        for(int i = 0; i < n; i++)
            printf("%d", used[i]);
        puts("");
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 11705 - Grasshopper

We are at a funfair, where an array of trampolines, named ‘’The Grasshopper Labyrinth’’, catches our attention. As the figure below shows, all of them are labelled with non-negative integers:

\epsfbox{p11705a.eps}

People are inside, jumping from one trampoline to another, trying to reach the trampoline in the northwest corner, where the exit to the attraction is located. If you reach the exit fast enough, you may win a prize. However, in order to be eligible for the prize, you must abide by the following rule: after leaping from a trampoline labelled with z, you need to get to another one z trampolines away, in the same row or column.

Therefore, your problem is to find the shortest path from any trampoline to the way out, measured by the number of leaps needed. Since the length of the jump from any trampoline is given, it is sufficient to label each trampoline with the direction of the best jump from it.

\epsfbox{p11705b.eps}

For a given starting position, a path is considered shorter than another if it requires a smaller number of jumps; in case of a tie, the path whose first step gets you northmost in the array is to be preferred; and in case of a tie, the one getting you westmost.

Instead of these symbols, we are using the plain text ones: the appropriate cardinal point (‘N’, ‘S’, ‘E’ or ‘W’) for the arrows, ‘X’ for the trampolines without possible escape, and the asterisk ‘*’ for the special trampoline at the upper left position, which represents the exit.

Input

Several cases are given in a single test file. The first line in each test case contains a pair of integers between 1 and 50, separated by a single space; the first is the number of rows and the second the number of columns in the matrix. Then, the entries in the matrix follow, line by line, each element being a non-negative integer, again separated by single whitespace characters. A 0 x 0 matrix will denote the end of the test cases, and hence should not be analyzed.

Output

The expected output of each data case is a character matrix. Each element is one of the allowed charset, N'',S’’, E'',W’’, X'' or*’’, as described above. The output for each case is followed by a blank line.

Sample Input

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

Sample Output

1
2
3
4
5
6
7
8
9
10
11
*SWX
EENW
NENW
*EEWWWXWWWWWWWWWXWWW
*XWSWX
ESSWSW
NWXWWX
EEEWNW
XXNNNX

Solution

題目描述：

每一個位置的彈簧上會標記一個數字 w，表示可以跳躍至上下左右其中一個方向的 w 距離所在。
求每一個位置下一步的方向，來獲得最短路徑 (跳躍次數) 到最左上角。

題目解法：

題目忘了講到字典順序，如果有相同的情況，則選擇跳躍越左上角越好。

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
#include <stdio.h> 
#include <queue>
#include <algorithm>
using namespace std;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};
const char ds[] = {'S', 'E', 'N', 'W'};
int main() {
//	freopen("in.txt", "r+t", stdin);
//	freopen("out.txt", "w+t", stdout); 
    int n, m, g[64][64];
    while(scanf("%d %d", &n, &m) == 2 && n+m) {
        for(int i = 0; i < n; i++)
            for(int j = 0; j < m; j++)
                scanf("%d", &g[i][j]);
                
        char ret[64][64] = {};
        int visited[64][64] = {}, x, y, tx, ty, d;
        int vx[64][64], vy[64][64];
        queue<int> X, Y;
        X.push(0), Y.push(0);
        while(!X.empty()) {
            x = X.front(), X.pop();
            y = Y.front(), Y.pop();
            for(int i = 0; i < 4; i++) {
                tx = x + dx[i], ty = y + dy[i], d = 1;
                while(tx < n && ty < m && tx >= 0 && ty >= 0) {
                    if(g[tx][ty] == d) {
                        if(visited[tx][ty] == 0) {
                            visited[tx][ty] = visited[x][y] + 1;
                            ret[tx][ty] = ds[i];
                            vx[tx][ty] = x, vy[tx][ty] = y;
                            X.push(tx), Y.push(ty);
                        } else if(visited[tx][ty] == visited[x][y] + 1 
                        && make_pair(x, y) < make_pair(vx[tx][ty], vy[tx][ty])) {
                            ret[tx][ty] = ds[i];
                            vx[tx][ty] = x, vy[tx][ty] = y;
                        }
                    }
                    tx += dx[i], ty += dy[i], d++;
                }
            }
        }
        for(int i = 0; i < n; i++, puts("")) {
            for(int j = 0; j < m; j++) {
                if(i == 0 && j == 0)
                    putchar('*');
                else if(visited[i][j] == 0)
                    putchar('X');
                else
                    putchar(ret[i][j]);
            }
        }
        puts("");
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 11700 - Pipes

After writing a solver for the “moveable maze” game last week, you have grown tired of it. After all, you already know the optimal solution. To entertain yourself, you find another puzzle game called “Pipes”, and play that for a while. On one puzzle, you have not been able to find a solution by hand, and you think that there is no solution. You decide to write a program to tell you whether this is the case.

The game is played on a grid with R rows and C columns. Each square of the grid contains a black dot in the centre and black lines in the direction of some, none, or all of its north, east, south, and west neighbouring squares, with the following restriction: if two opposite directions both have lines, then at least one of the other two directions has a line as well. In other words, it is forbidden for a square to consist of a straight line.

The objective of the game is to rotate each square, as many times as you like, such that for each square, if it has a line going in a compass direction (that is, north, east, south, or west), then it has a neighbour in that compass direction and that neighbour has a line going in the opposite compass direction. In other words, each edge in the grid should either have a line on both sides or neither side.

Your task is to determine whether a given grid has a solution.

Input Specification

The input consists of several test cases.

The first line of each test case contains the two integers R and C, separated by spaces, with 1 <= R,C <= 12.

The following R lines of input each contain one row of the grid, from north to south. Each of these lines contains exactly C strings of letters, separated by spaces, that correspond to squares of the grid, from west to east. Their format is as follows:

  • If the string is the single character x, then the square does not contain a line to any of its neighbours.
  • Otherwise, the string contains some of the characters N, E, S, W, which indicate that a black line extends from this square’s centre in the direction of its north, east, south, or west neighbour, respectively. No character will appear in the string more than once.

Input is terminated by a line containing 0 0. These zeros are not a test case and should not be processed.

Sample Input

1
2
3
4
5
6
7
8
3 3
NW NW x
NES NESW W
E W x
2 2
ES x
x N
0 0

Output Specification

For each test case, output SOLVABLE if there is a solution to the puzzle, and UNSOLVABLE otherwise.
Output for Sample Input

1
2
SOLVABLE
UNSOLVABLE

Solution

題目描述：

一個類似水管通路的遊戲，每一格都會有四個方向的缺口，請將每一個缺口與相鄰的格子缺口對齊。

題目解法：

當初以為是要從某一個邊流向到另一個邊，但是題目並沒有說明這些，其實就假想每一個格子都會有四個方向的標記，翻轉每一個格子，標記和標記之間要對到。(有標記的邊一定要與另一個有標記的邊相鄰)

因此，類似於關燈遊戲的窮舉方式，從左上依序窮舉到右下，同時檢查上一列的條件是否符合。

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
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
using namespace std;
int g[16][16][4], n, m;
int kind[16][16], solvable;
static const int dx[] = {-1, 0, 1, 0}; // N, E, S, W
static const int dy[] = {0, 1, 0, -1};
void rotate(int r, int c) {
    int t = g[r][c][0];
    for(int i = 1; i < 4; i++)
        g[r][c][i-1] = g[r][c][i];
    g[r][c][3] = t;
}
int check(int r, int c, int ign) {
    for(int i = 0; i < 4; i++) {
        if(i == ign)	continue;
        if(g[r][c][i]) {
            int tx = r + dx[i], ty = c + dy[i];
            if(tx < 0 || ty < 0 || tx >= n || ty >= m)
                return 0;
            if(!g[tx][ty][(i+2)%4])
                return 0;
        }
    }
    return 1;
}
void dfs(int r, int c) {
    if(solvable)
        return;
    if(c == m) {
        if(check(r, c-1, 2))
            dfs(r + 1, 0);
        return ;
    }
    if(r == n) {
        int f = 1;
        for(int i = 0; i < m; i++)
            f &= check(r-1, i, -1);
//		if(f)
//		for(int i = 0; i < n; i++) {
//			for(int j = 0; j < m; j++) {
//				printf("[%d, %d] ", i, j);
//				for(int k = 0; k < 4; k++)
//					printf(" %d", g[i][j][k]);
//				puts("");
//			}
//		}
        solvable |= f;
        return;
    }
    
    if(kind[r][c] == 0) {
        if(check(r-1, c, -1)) {
            if(c && !check(r, c-1, 2))
                return;
            dfs(r, c+1);
        }
    } else {
        for(int i = 0; i < kind[r][c]; i++, rotate(r, c)) {
            if(check(r-1, c, -1)) {
                if(c && !check(r, c-1, 2))
                    continue;
                dfs(r, c+1);
            }
        }
    }
}
int main() {
    char s[128], mapped[128] = {};
    mapped['N'] = 0;
    mapped['E'] = 1;
    mapped['S'] = 2;
    mapped['W'] = 3;
    while(scanf("%d %d", &n, &m) == 2 && n + m) {
        memset(g, 0, sizeof(g));
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                scanf("%s", s);
                if(s[0] != 'x') {
                    for(int k = 0; s[k]; k++)
                        g[i][j][mapped[s[k]]] = 1;
                }
                if(s[0] == 'x')
                    kind[i][j] = 0;
                else {
                    int len = strlen(s);
                    if(len == 4)
                        kind[i][j] = 0;
                    else if(len == 1 || len == 3)
                        kind[i][j] = 4;
                    else {
                        if(g[i][j][0] == g[i][j][2])
                            kind[i][j] = 2;
                        else
                            kind[i][j] = 4;
                    }
                }
            }
        }
        solvable = 0;
        dfs(0, 0);
        puts(solvable ? "SOLVABLE" : "UNSOLVABLE");
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 11696 - Beacons

Problem

In ancient times, communication was not as swift as it is today. When a kingdom was at war, it could take months to muster all the armed forces. But by using fire-lit beacons at strategic locations, it was still possible to quickly send emergency signals.

When the first beacon is lit, all other beacons within sight from it are also lit. All beacons within sight of these are then lit, and so on until all beacons are lit - assuming of course that all beacons are within sight of each other, directly or indirectly. If they are not, the dire news must be carried by riders between some beacons.

Given the location of all beacons in the kingdom as well as the location and size of all mountain peaks, write a program that determines how many messages must be sent by riders in order for all beacons to be lit when an enemy threatens the country.

For simplicity, we model the country in the following way: a beacon is represented as a point in the xy-plane and a mountain peak is represented as a circle. Two beacons are considered to be within sight of each other if no mountain peak blocks the straight line between the two beacons.

The input will be constructed so that the straight line between any pair of beacons will not touch the circumference of a mountain peak, unless it passes through the interior of another mountain peak. Mountain peaks will not overlap or touch, nor will any beacon be on a mountain peak or on its circumference.

Input

The first line of the input file contains an integer N (N<25) which denotes the total number of test cases. The description of each test case is given below:

The first line of input for each test case contains two integers n (1 ≤ n ≤ 1000) and m (0 ≤ m ≤ 1000) the number of beacons and the number of mountain peaks, respectively. Then follow n lines specifying the locations of the beacons. The location of each beacon is given as a pair of integers x and y (0 ≤ x, y ≤ 10000). Then follow m lines describing the mountain peaks. Each mountain peak is given as a pair of integers x and y x(0 ≤ x, y ≤ 10000) specifying the location of the peak and a radius r (1 ≤ r ≤ 5000).

Output

For each test case the output should be a line containing a single integer: the number of messages that must be carried by riders for all beacons to be lit.

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
2
6 3
1 8
5 4
7 7
9 2
16 6
17 10
4 7 2
6 3 1
12 6 3
4 4
0 4
8 4
4 0
4 8
2 2 1
6 2 1
2 6 1
6 6 1

Sample Output

1
2
2
1

Solution

題目描述：

每個山峰將會由一個點為圓心和半徑構成，而從編號 1 將會發送狼煙，這個狼煙要傳遞到每一個其他點，但有可能會被山峰擋住 (當作圓柱也行)，因此必須採用人工的方式將訊息傳遞到另一個點進行施放，當每一個點獲得訊息後，也會點燃狼煙傳給其他點。

求最少的人工傳遞次數。

題目解法：

找到這題的 graph，接著找有多少個 component 即可，但是對於建造 graph 的成本上，不能使用 O(n n m) 任抓兩個點並且檢查是否有圓柱遮蔽。

窮舉對於每一個點，將其當作圓心，得到其他點的極角排序，接著對於每一個圓柱找到遮蔽的極角區間，二分搜索區間後，直接針對該區間的點進行圓柱遮蔽判斷。如此一來建圖的效率就能快很多。

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
#include <stdio.h>
#include <math.h>
#include <vector>
#include <string.h>
#include <algorithm>
using namespace std;
#define eps 1e-8
struct Pt {
    double x, y;
    Pt(double a = 0, double b = 0):
    	x(a), y(b) {}
    bool operator<(const Pt &a) const {
        if(fabs(x-a.x) > eps)	return x < a.x;
        return y < a.y;
    }
    bool operator==(const Pt &a) const {
        return fabs(x-a.x) < eps && fabs(y-a.y) < eps;
    }
    Pt operator+(const Pt &a) const {
        return Pt(x + a.x, y + a.y);
    }
    Pt operator-(const Pt &a) const {
        return Pt(x - a.x, y - a.y);
    }
    Pt operator/(const double val) const {
        return Pt(x / val, y / val);
    }
    Pt operator*(const double val) const {
        return Pt(x * val, y * val);
    }
};
double dist(Pt a, Pt b) {
    return hypot(a.x - b.x, a.y - b.y);
}
double dot(Pt a, Pt b) {
    return a.x * b.x + a.y * b.y;
}
double cross2(Pt a, Pt b) {
    return a.x * b.y - a.y * b.x;
}
Pt D[1024], E[1024];
double Er[1024];
#define maxL (1048576>>5)+1
#define GET(x) (g[(x)>>5]>>((x)&31)&1)
#define SET(x) (g[(x)>>5] |= 1<<((x)&31))
int g[maxL];
void buildGraph(int n, int m) {
    memset(g, 0, sizeof(g));// all link
    sort(D, D+n); // let (i, j) i < j for polar angle in [-pi/2, pi/2]
    for(int i = 0; i < n; i++) {
        vector< pair<double, int> > A;
        for(int j = i+1; j < n; j++)
            A.push_back(make_pair(atan2(D[j].y - D[i].y, D[j].x - D[i].x), j));
        sort(A.begin(), A.end());
        for(int j = 0; j < m; j++) { // test obstacle
            double mm = atan2(E[j].y - D[i].y, E[j].x - D[i].x);
            double theta = asin(Er[j] / dist(E[j], D[i])), L = mm - theta, R = mm + theta;
            int st = lower_bound(A.begin(), A.end(), make_pair(L, -1)) - A.begin();
            for(int k = st; k < A.size() && A[k].first <= R; k++) {
                if(dot(D[i] - D[A[k].second], E[j] - D[A[k].second]) > 0)
                    SET(i * n + A[k].second), SET(A[k].second * n + i);
            }
        }
    }
}
int visited[1024];
void dfs(int u, int n) {
    visited[u] = 1;
    for(int i = 0; i < n; i++) {
        if(!GET(u * n + i) && !visited[i]) {
            dfs(i, n);
        }
    }
}
int main() {
    int testcase, n, m;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d %d", &n, &m);
        for(int i = 0; i < n; i++) 
            scanf("%lf %lf", &D[i].x, &D[i].y);
        for(int i = 0; i < m; i++)
            scanf("%lf %lf %lf", &E[i].x, &E[i].y, &Er[i]);
        buildGraph(n, m);
        int ret = 0;
        memset(visited, 0, sizeof(visited));
        for(int i = 0; i < n; i++) // compute how many component
            if(visited[i] == 0)
                dfs(i, n), ret++;
        printf("%d\n", ret - 1);
    }
    return 0;
}
/*
2
6 3
1 8
5 4
7 7
9 2
16 6
17 10
4 7 2
6 3 1
12 6 3
4 4
0 4
8 4
4 0
4 8
2 2 1
6 2 1
2 6 1
6 6 1
*/
Read More +