《P2421 [NOI2002] 荒岛野人》

题目描述

克里特岛以野人群居而著称。岛上有排列成环形的 m 个山洞。这些山洞顺时针编号为 1,2,…,m。岛上住着 n 个野人，一开始依次住在山洞 C1​,C2​,…,Cn​ 中，以后每年，第 i 个野人会沿顺时针向前走 Pi​ 个洞住下来。

每个野人 i 有一个寿命值 Li​，即生存的年数。

下面四幅图描述了一个有 6 个山洞，住有三个野人的岛上前四年的情况。三个野人初始的洞穴编号依次为 1,2,3；每年要走过的洞穴数依次为 3,7,2；寿命值依次为 4,3,1。

奇怪的是，虽然野人有很多，但没有任何两个野人在有生之年处在同一个山洞中，使得小岛一直保持和平与宁静，这让科学家们很是惊奇。他们想知道，至少有多少个山洞，才能维持岛上的和平呢？

输入格式

第 1 行为一个整数 n(1≤n≤15)，即野人的数目。

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

输出格式

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

输入输出样例

输入 #1复制

3 1 3 4 2 7 3 3 2 1

输出 #1复制

6

说明/提示

1≤N≤15，1≤Ci​,Pi​≤100，0≤Li​≤106

保证 M≤106

代码实现：

#include <cstdio> #include <iostream> using namespace std; const int maxn = 20, maxm = 1e6; int len[maxn], pos[maxn], val[maxn]; int n, m; int exgcd(int a, int b, int &x, int &y) { if (!b) { x = 1; y = 0; return a; } int res = exgcd(b, a % b, x, y), t = x; x = y; y = t - a / b * y; return res; } bool check(int i, int j, int b) { int a = pos[j] - pos[i], d = val[i] - val[j], x, y; if (a < 0) a = -a, d = -d; int g = exgcd(a, b, x, y); if (d % g) return 1; return ((x * (d / g) % (b / g) + (b / g)) % (b / g)) > min(len[i], len[j]); } int main() { scanf("%d", &n); for (int i = 1; i <= n; ++i) { scanf("%d%d%d", val + i, pos + i, len + i); m = max(m, val[i]); } for (int i = m; i <= maxm; ++i) { bool ok = 1; for (int j = 1; j <= n && ok; ++j) for (int k = 1; k <= n && ok; ++k) if (k != j && !check(j, k, i)) ok = 0; if (ok) { printf("%d\n", i); break; } } return 0; }