做题网站推荐: OpenJudge VIJOS UOJ CF JOYOI CODEVS 洛谷 RQNOJ BZOJ POJ HDU 牛客网

本站题目推荐: 高精度 模拟 排序 递推 贪心 递归 搜索 动态规划 数学 图论 数据结构 实名认证 卡评测举报

输入输出 变量类型 顺序结构 选择结构 循环结构 一维数组 NOIP 资源下载


问题 2917. -- 「一本通 6.4 练习 1」荒岛野人

2917: 「一本通 6.4 练习 1」荒岛野人

时间限制: 1 Sec  内存限制: 512 MB
提交: 0  解决: 0
[上一题][提交][讨论版][状态][下一题]

题目描述

原题来自:NOI 2002

克里特岛以野人群居而著称。岛上有排列成环行的 MMM 个山洞。这些山洞顺时针编号为 1,2,⋯,M1,2,cdots ,M1,2,,M

岛上住着 NNN 个野人,一开始依次住在山洞 C1,C2,⋯,CNC_1,C_2,cdots ,C_NC1,C2,,CN 中,以后每年,第 iii 个野人会沿顺时针向前走 PiP_iPi 个洞住下来。每个野人 iii 有一个寿命值 LiL_iLi,即生存的年数。下面四幅图描述了一个有 666 个山洞,住有三个野人的岛上前四年的情况。三个野人初始的洞穴编号依次为 1,2,31,2,31,2,3;每年要走过的洞穴数依次为 3,7,23,7,23,7,2;寿命值依次为 4,3,14,3,14,3,1

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

输入

第一行为一个整数 NNN,即野人的数目;

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

输出

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

提示

样例输入

3
1 3 4
2 7 3
3 2 1

样例输出

6

样例说明

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

对于全部数据,1≤N≤15,1≤Ci,Pi≤100,0≤Li≤1061le Nle 15,1le C_i,P_ile 100,0le L_ile 10^61N15,1Ci,Pi100,0Li106

标签

[上一题][提交][讨论版][状态][下一题]