National Olympiad in Informatics, China, 2002
Day 2, Problem 1 - Island of Cavemen
The Crete islands are famously home to a society of savage cavemen. On the islands, there are M caves arranged in a loop shape. These caves are labeled 1, 2, …, M in clockwise order. There are N cavemen living on the island, initially located in caves C1, C2, …, CN. Each year afterwards, the i-th caveman will move clockwise by Pi caves. Each caveman has a lifespan of Li, the number of years they survive. The four figures below illustrate the scenario of an island with six caves and three cavemen, in the span of four years. The three cavemen initially live in the caves numbered 1, 2, and 3. Each year they move by 3, 7, and 2 caves, respectively. Their lifespans are 4, 3, and 1, respectively.
What's interesting is that although there are many cavemen, no two cavemen will ever share the same cave in any year of their lifetimes. This ensures that the little island will always maintain its peace and quiet, which is very puzzling for scientists. They would like to know, what is the minimum number of caves needed for the island to maintain its peace?
The first line of input contains a single integer N (1 ≤ N ≤ 15), the number of cavemen. Lines 2 to N+1 each contain three integers Ci, Pi, and Li. (1 ≤ Ci, Pi ≤ 100; 0 ≤ Li ≤ 106), representing the initial cave numbers of caveman i, the number of caves it moves by per year, and its lifespan.
Output a single integer M, the minimum number of caves required to maintain peace. There is guaranteed to be a solution, and M will not exceed 106.
3 1 3 4 2 7 3 3 2 1
Point Value: 20 (partial)
Time Limit: 2.00s
Memory Limit: 16M
Added: May 11, 2014
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3