P2421 [NOI2002]荒岛野人

    • 144通过
    • 398提交
  • 题目提供者 woshiren
  • 评测方式 云端评测
  • 标签 NOI系列 2002
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目背景

    原 A-B数对(增强版)参见P1102

    题目描述

    克里特岛以野人群居而著称。岛上有排列成环行的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不大于10^6。

    输入输出样例

    输入样例#1: 复制
    3
    1 3 4
    2 7 3
    3 2 1
    输出样例#1: 复制
    6

    说明

    对于50% 的数据:N 的范围是[1…1,000]。

    对于另外50% 的数据:N 的范围是[1…100,000]。

    对于100% 的数据:C 的范围是[1…1,000,000,000],N 个整数中每个数的范围是:[0…1,000,000,000]。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。