bzoj1407 [Noi2002]Savage

Description

img

Input

第1行为一个整数N(1<=N<=15),即野人的数目。

第2行到第N+1每行为三个整数Ci, Pi, Li表示每个野人所住的初始洞穴编号,每年走过的洞穴数及寿命值。

(1<=Ci,Pi<=100, 0<=Li<=10^6 )

Output

仅包含一个数M,即最少可能的山洞数。输入数据保证有解,且M不大于10^6。

Sample Input

3
1 3 4
2 7 3
3 2 1

Sample Output

6
//该样例对应于题目描述中的例子。

HINT

Source

鸣谢刘汝佳先生授权使用

题解

枚举答案,然后$O(n^2)$判断是否符合条件。由题意可以得出方程$c_1+p_1*t-(c_2+p_2*t)=M*y$

其中$t$表示他们跳到同一格的时间,$y$为辅助元,我们可以整理得到$(p_1-p_2)*t-M*y=c_2-c1$

。注意$p_1=p_2$和$c_1=c_2$的特殊情况。如果有解则M不符合条件,有解情况为$c_2-c_1\equiv M\pmod{d} $且$x\leq\min(L_1,L_2)$。

要注意$M$要除以$D$,这样才能保证最小解。

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<bits/stdc++.h>
#define ps puts("")
#define fi first
#define nd second
#define mset(x) memset((x), 0, sizeof (x))
#define mk make_pair
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
ll read() {ll x = 0;char f = 1, ch = getchar();while(ch < '0' || ch > '9') {if(ch == '-')f = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * f;}
void write(ll x) {if(x < 0) x = -x, putchar('-');if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const int N = 20;
ll C[N], p[N], l[N];
ll exgcd(ll a, ll b, ll &x, ll &y){
if(b) {
ll d = exgcd(b, a % b, y, x);
y -= a / b * x;
return d;
} else {
x = 1;
y = 0;
return a;
}
}
int main() {
int n;
ll T = 0;
n = read();
for(int i = 1; i <= n; ++i)
C[i] = read(), p[i] = read(), l[i] = read(), T = max(T, C[i]);
for(; ; ++T) {
bool fg = 1;
for(int i= 1; i <= n && fg; ++i)
for(int j = i + 1; j <= n && fg; ++j) {
ll a = p[i] - p[j], b = -T, c = C[j] - C[i];
if(!c) {fg = 0;break;}
if(!a) continue;
a = -a;
b = -b;
c = -c;
ll xx, yy;
ll d = exgcd(a, b, xx, yy);
if(!(c % d)) {
ll M = T / d;
xx = c / d * xx % M;
xx = (xx + M) % M;
if(xx <= min(l[i], l[j])) {
fg = 0;
break;
}
}
}
if(fg) {
writeln(T);
break;
}
}
return 0;
}