解題區/解題區 - UVa

UVa 10413 - Crazy Savages

contents

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

Problem

瘋狂的島嶼上有 n 個野蠻人、m 個山洞，山洞呈現環狀分佈。

每個野蠻人一開始各自在自己的洞窟 Ci，每隔一天就會移動到下 Pi 個山洞，在島上待 Li 天後就會死亡。

兩個野蠻人若剛好移動到相同洞窟，則會發生爭吵，請問至少要幾個洞窟，才能不發生爭吵。

Input

1
2
3
4
5
6
7
8
9
10
11
2
3
1 3 4
2 7 3
3 2 1
5
1 2 14
4 4 6
8 5 9
11 8 13
16 9 10

Output

1
2
6
33

Solution

窮舉洞窟數量 m，檢查是否存在爭吵。

檢查任兩個野蠻人 i, j 是否會在生存時間內相遇，假設會在第 k 天相遇，滿足公式

1
2
ci + k * pi = a * m  --- (1)
cj + k * pj = b * m  --- (2)

將公式整理後

1
2
3
(2)-(1) 	=> (ci - cj) + k * (pi - pj) = m * (a - b)
            => (a - b) * m + k * (pj - pi) = ci - cj
check k in [0, min(L[i], L[j])] has a

檢查 k 最小為多少，使得等式解存在。

套用擴充歐幾里德算法，得到 ax + by = gcd(x, y) 的第一組解 (a, b)，其 a, b 的參數式為

1
2
3
4
5
g = gcd(x, y)
a = a + lcm(x, y)/x * k
b = b + lcm(x, y)/y * k
=> a = a + y / g * k
=> b = b + x / g * k

最小化 a 參數，滿足 a >= 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
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
#include <stdio.h> 
#include <algorithm>
#include <math.h>
using namespace std;
const int MAXN = 32;
const int INF = 0x3f3f3f3f;
int C[MAXN], P[MAXN], L[MAXN];
// a x + by = g
void exgcd(int x, int y, int &g, int &a, int &b) {
    if (y == 0)
        g = x, a = 1, b = 0;
    else
        exgcd(y, x%y, g, b, a), b -= (x/y) * a;
}
int hasCollision(int m, int n) {
    // assume m caves arranged in a circle
    // ci + k * pi = a * m  --- (1)
    // cj + k * pj = b * m  --- (2)
    // (2)-(1) 	=> (ci - cj) + k * (pi - pj) = m * (a - b)
    //			=> (a - b) * m + k * (pj - pi) = ci - cj
    // check k in [0, min(L[i], L[j])] has a solution.
    for (int i = 0; i < n; i++) {
        for (int j = i+1; j < n; j++) {
            int x = P[j] - P[i], y = m, z = C[i] - C[j];
            int a, b, g;
            int limitR = min(L[i], L[j]), limitL = 0;
            exgcd(x, y, g, a, b);
        
            if (z%g)	continue;
            a = a * (z / g);
            // ax + by = z
            // a = a + lcm(x, y)/x * k, b = b + lcm(x, y)/y * k
            // a = a + y / g * k, b = b + x / g * k
            // minmum a, a >= 0
            if (g < 0)	g = -g;
            a = (a%(y/g) + y/g) % (y/g);
            if (a <= limitR)
                return true;
        }
    }
    return false;
}
int main() {
    int testcase, n;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        
        int m = 0;
        for (int i = 0; i < n; i++) {
            scanf("%d %d %d", &C[i], &P[i], &L[i]);
            m = max(m, C[i]);
        }
            
        int ret = -1;
        for (int i = m; i < 99999999; i++) {
            
            if (!hasCollision(i, n)) {
                ret = i;
                break;
            }
        }
        printf("%d\n", ret);
    }
    return 0;
}
/*
2
3
1 3 4
2 7 3
3 2 1
5
1 2 14
4 4 6
8 5 9
11 8 13
16 9 10
*/