#P1407. [Noi2002]Savage

    ID: 419 传统题 1000ms 512MiB 尝试: 3118 已通过: 984 难度: 5 上传者: 标签>CF1800普及+/提高-暴力枚举线性同余方程扩展欧几里得算法鸣谢刘汝佳先生授权使用

[Noi2002]Savage

题目描述

岛上有 m 个洞穴,顺时针编号为 1∼m。岛上有 nn(1≤n≤151≤n≤15)个野人分别住在 c1,c2,…,cn(1≤ci≤100)c_1,c_2,…,c_n (1≤c_i≤100) 中。以后每年,第 i 个野人会沿顺时针向前走 pi(1≤pi≤100)p_i (1≤p_i≤100) 个洞住下来,其中第 i 个野人可以生存 lil_i 年。没有 22 个野人能在有生之年生存在同一个洞穴中,求洞穴个数 mm(m≤106m≤10^6)的最小值。

输入格式

第1行为一个整数 N(1<=N<=15),即野人的数目。 第2行到第 N+1 每行为三个整数 Ci,Pi,Li 表示每个野人所住的初始洞穴编号,每年走过的洞穴数及寿命值。 (1<=Ci,Pi<=100,0<=Li<=10^6)。

输出格式

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

3
1     3      4
2     7      3
3     2      1
6
//该样例对应于题目描述中的例子。

提示

没有写明提示。

题目来源

鸣谢刘汝佳先生授权使用。