題目 2533:
信息學(xué)奧賽一本通T1637-荒島野人
時(shí)間限制: 2s
內(nèi)存限制: 192MB 提交: 6 解決: 4
題目描述
原題來自：NOI 2002
克里特島以野人群居而著稱。島上有排列成環(huán)行的 M 個(gè)山洞。這些山洞順時(shí)針編號(hào)為 1,2,?,M。
克里特島以野人群居而著稱。島上有排列成環(huán)行的 M 個(gè)山洞。這些山洞順時(shí)針編號(hào)為 1,2,?,M。
島上住著 N 個(gè)野人，一開始依次住在山洞 C1,C2,?,CN 中，以后每年，第 i 個(gè)野人會(huì)沿順時(shí)針向前走 Pi個(gè)洞住下來。每個(gè)野人 i 有一個(gè)壽命值 Li ，即生存的年數(shù)。下面四幅圖描述了一個(gè)有 6 個(gè)山洞，住有三個(gè)野人的島上前四年的情況。三個(gè)野人初始的洞穴編號(hào)依次為 1,2,3；每年要走過的洞穴數(shù)依次為 3,7,2；壽命值依次為 4,3,1。
奇怪的是，雖然野人有很多，但沒有任何兩個(gè)野人在有生之年處在同一個(gè)山洞中，使得小島一直保持和平與寧?kù)o，這讓科學(xué)家們很是驚奇。他們想知道，至少有多少個(gè)山洞，才能維持島上的和平呢？
輸入格式
第一行為一個(gè)整數(shù) N，即野人的數(shù)目；
第二行到第 N+1 每行為三個(gè)整數(shù) Ci,Pi,Li ，表示每個(gè)野人所住的初始洞穴編號(hào)，每年走過的洞穴數(shù)及壽命值。
第二行到第 N+1 每行為三個(gè)整數(shù) Ci,Pi,Li ，表示每個(gè)野人所住的初始洞穴編號(hào)，每年走過的洞穴數(shù)及壽命值。
輸出格式
僅包含一個(gè)數(shù) M，即最少可能的山洞數(shù)。輸入數(shù)據(jù)保證有解，且 M 不大于 106。
樣例輸入
3 1 3 4 2 7 3 3 2 1
樣例輸出
6
提示
樣例說明
該樣例對(duì)應(yīng)于題目描述中的例子。
數(shù)據(jù)范圍與提示：
對(duì)于全部數(shù)據(jù)，1≤N≤15,1≤Ci,Pi≤100,0≤Li≤106。
該樣例對(duì)應(yīng)于題目描述中的例子。
數(shù)據(jù)范圍與提示：
對(duì)于全部數(shù)據(jù)，1≤N≤15,1≤Ci,Pi≤100,0≤Li≤106。