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
*/