个人网站建设教程荆门网站建设服务

个人网站建设教程,荆门网站建设服务,c 做网站起什么作用,在线设计闪字图片题目描述克里特岛以野人群居而著称。岛上有排列成环形的 m 个山洞。这些山洞顺时针编号为 1,2,…,m。岛上住着 n 个野人#xff0c;一开始依次住在山洞 C1​,C2​,…,Cn​ 中#xff0c;以后每年#xff0c;第 i 个野人会沿顺时针向前走 Pi​ 个洞住下来。每个野人 i 有一个…题目描述克里特岛以野人群居而著称。岛上有排列成环形的 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 行到第 N1 每行为三个整数 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≤151≤Ci​,Pi​≤1000≤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; }