TopCoder

FHVirus
想像不出自己 AC 的題目是實作不出來的!

User's AC Ratio

83.6% (46/55)

Submission's AC Ratio

47.3% (156/330)

Tags

Description

琵歐伯,一個終年下雨不停的音樂之城。這個城市裡有全國最好的音樂學院,也聚集了許多想成為音樂家的人。

琵歐伯音樂學院最重要的大事就是每年一月的畢業演奏會,全校的畢業生都必須上台表演。畢業演奏會對琵歐伯音樂學院的學生來說是非常重要的一次演出,表現優異的話可能會被外面的知名樂團看上,順利踏入音樂界。

本故事的主角 A 就是琵歐伯音樂學院的學生(*A為什麼叫*A呢,聽說是因為他把 A 演算法用得出神入化,於是被同學們尊稱為 A* 之神。不知道為什麼有次倒過來變成 *A,之後大家就跟著這樣叫了),主修的樂器是「符德魯琴」。這種樂器和一般樂器最不同的地方是,符德魯琴需要注入魔力才能演奏,需要極高的天份,一般人是學不來的。符德魯琴並不適合單獨演奏,通常符德魯琴系的畢業生都會找聲樂系的學生合奏。為此,*A 要在這兩個月中找出最適合和他搭配的人,才能演奏出最完美的音樂。

其實 *A 並不是應屆畢業生,他是以非常優秀的成績申請跳級,所以比正常的畢業生還小了一歲。這樣的特殊身份對他好有壞,壞處是他跟大一屆的聲樂系學長姊不太熟,還沒有固定的搭擋。好處是全聲樂系的學生都知道 *A 的符德魯琴非常好聽,人又很正,不論男女都想跟他合作演出。

*A 利用他的優勢找了 $n$($n \leq 1000$)個學姊(*A 是個大色鬼只找學姊不找學長),分別問了她們有空一起練習合奏的時間。很巧的是每個人有空的時間都是一段連續的日期,其中第 i 個學姊有空的時間是從今天開始算 $R_i$ 天後到 $D_i$ 天後(包含頭尾這兩天)。合奏是為了計算兩個人之間的「適合度」,要計算和學姊 $i$ 的「適合度」至少要 $P_i$ 次的合奏才行。

*A 是個大忙人,除了要準備畢業演奏之外還有很多約會,所以每天最多只能和一個人合奏。他希望能夠在畢業演奏會之前多和幾個學姊試試看,想請你幫他完成這個程式,讓他找到最好的搭擋,要是之後順利成為知名的音樂家,*A 絕對不會忘記你的!

Input Format

輸入檔包含多組測試資料。每組測試資料的第一行是一個整數 $n$。接下來 $n$ 行每行有三個正整數,其中第i行依序是 $Ri, Di, Pi$ ($0 < Ri, Di, Pi \leq 10^ 7, Ri < Di$),且滿足($R_1 \leq R_2 \leq \dots \leq R_n, D_1 \leq D_2 \leq \dots \leq D_n$)。讀到 $n = 0$ 的時候代表檔案的結尾,不需要對於這個數字作任何輸出。

Output Format

對每組測試資料,輸出一個整數表示最多能算出幾個學姊的「適合度」。

Sample Input 1

3
1 4 3
2 6 4
5 6 2
0

Sample Output 1

2

Hints

Problem Source

原TIOJ1100 / NPSC2006決賽(prob C)

Subtasks

No. Testdata Range Score
1 0 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 2000 65536 262144 1