TopCoder

腦子裝咖哩
想像不出自己 AC 的題目是實作不出來的!雖然想像得出來也不一定可以就是了

User's AC Ratio

92.9% (104/112)

Submission's AC Ratio

39.2% (240/612)

Tags

Description

傳說中,魔法部是個處理世界上各種魔法事件的神秘部門,他們的職責就是要保護魔法世界的隱密性,不要讓魔法干擾麻瓜們(魔法世界對不懂魔法的凡人的稱呼)的生活。身為剛上任的魔法部長,你最近真是忙得焦頭爛額,因為「那個人」回來了(指的是黑魔王佛地魔,因為這個名字實在是太邪惡了,因此大家都以「那個人」來稱呼他)!由於復活之後的「那個人」開始帶領食死人們在世界上到處作亂,讓你大傷腦筋。還好,你最近得到了一個魔法寶物──「預言之石」,它可以在當天凌晨零時的時候預言出今天一天之內發生的魔法事件,於是你就可以即時安排正氣師去阻止食死人的行動。

由於「那個人」不斷的在麻瓜世界裡作亂,因此正氣師得跑到麻瓜世界理去處理,所以就不能騎著掃把到處飛了(要不然被麻瓜們看到就糟糕了)。因此,他們只好學著使用麻瓜世界的行動方式──開車。還好麻瓜世界的馬路是由一條條南北向的大道和東西向的街組成,就像棋盤一樣,因此每個路口都可以用兩個數字 $(x, y)$ 表示,例如 $(5, 3)$ 就代表第 $5$ 大道第 $3$ 街口。雖然不能騎掃把,正氣師還是可以用一點小小的魔法讓路上通行無阻,因此只要用一分鐘的時間就可以從一個路口到下一個路口,例如從 $(5, 3)$ 開車到 $(5, 4)$ 只要一分鐘就好了;而若是從 $(5, 3)$ 開車到 $(7, 5)$,則需要 $(7-5) + (5-3) = 4$ 分鐘。

每當一個魔法事件發生時,都得要有一位正氣師即時趕到才能處理(當然正氣師也可以提早到達發生地點,不過得等到事件發生才能處理)。如果這個正氣師是直接從正氣師局動身的話,就可以用「現影術」瞬間移動到魔法事件發生的地點。而當正氣師處理完一件事的時候,如果趕得及,還可以再趕去處理另一個魔法事件,這時就只能開車了(當然,他們隨時都有辦法弄來一部車)。但是最近的事情實在是太多了,讓正氣師局的人員都接應不暇,因此你得作最好的指派,使得可以出最少的人力去處理完所有的魔法事件。

Input Format

輸入資料的第一行有一個數字 $n$,表示你現在要處理 $n$ 天的資料。每天的資料有許多行,第一行有個數字 $m$($1 ≤ m ≤ 1000$),表示當天預言之石預告了 $m$ 個魔法事件的發生。接下來有 $m$ 行,每行有三個數字 $t\ x\ y$,表示在當天時間 $t$($0 ≤ t < 1440$)的時候在第 $x$ 大道第 $y$ 街口($0 ≤ x, y ≤ 1000$)會有魔法事件發生。你可以假設任兩個魔法事件不可能在同時同地發生。

Output Format

輸出資料應該有 $n$ 行,每行對應到輸入資料的每一天。每行有一個數字,表示當天最少要派出多少正氣師,才能處理完所有事件。

Sample Input 1

2
3
1 5 3
2 5 4
3 6 6
5
10 6 8
20 2 14
30 7 19
40 8 10
50 0 12

Sample Output 1

2
1

Hints

Problem Source

原 TIOJ1069 / NPSC2005 初賽 (prob E)

Subtasks

No. Testdata Range Score
1 0 100

Testdata and Limits

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