TopCoder

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

100.0% (6/6)

Description

  楓之谷是一個線上的平面捲動遊戲,整個遊戲的地圖分割成許多場景,在每一個場景之中,遊戲角色可以移動,跳躍,爬樓梯和繩子等等。而在場景之間,有傳送點連接,有單向的傳送點 (只能從一邊到另一邊,不能倒著回來),也有雙向的傳送點,而另外也有一些傳送點是在場景的內部的。

  說實在話,這是一個相當空虛的遊戲,這個遊戲是沒有止境的,遊戲的主軸就是讓玩家不斷地打怪物,賺寶物和經驗值,然後升級,升級了以後可以有更強的攻擊力和防禦力,就可以打更強的怪物,賺更難得的寶物和更多的經驗值...。單調無聊而重覆的動作,適合讓作學生的在考前念書念不下去時拿來發洩。

  遊戲中有個玩家叫作 CindyWangXD,我不知道她為什麼要用這個名字,或許她欣賞王心凌吧,只是王心凌的英文名字好像也不是這樣寫的。這個玩家是個弓箭手,所以在她的道具的「消耗欄」裡面,除了放了有各式補血、補氣的藥水以外,還放了大量的弓箭、弩箭。消耗欄的格子數是有限的,而每一格最多只能放100瓶水或是1000支箭,而且不同的東西還不能放在同一格,對於愛冒險、喜歡打高級怪物的CindyWangXD來說,因為每打一支都要花至少三十支箭以上,若不是帶著將近一萬支箭在身上,她總是放不下心。

  根據遊戲的設計,每一回把箭射出去,或是把一瓶水喝掉的時候,當該種箭 (或是水) 放置在不只一格的位置時,那程式會自動從最前面那一格開始消耗。所以過了一些時候,就有可能會有兩格都是三四百支箭,總共在道具的「消耗欄」佔用兩格,卻不會自動地放在同一格裡面。因此每過一段時候,她就要手動地把這些格子整理整理,盡量空出格子,好繼續攜帶更多的箭或是藥水。理想的整理結果是:放藥水的格子每一格都放100瓶,最後如果有不足100的部分全都集中在同一格;同理,放箭的格子每一格都放1000支,最後如果有不足1000的也全都集中在同一格。雖然現在她道具的消耗欄看起來很亂,但你可以假設每一種物品在道具的消耗欄中所佔據的格數,都不會超過十格以上。

  由於CindyWangXD都是用筆記型電腦玩遊戲,觸控板不是很好用,甚至她用的那一台還有一點故障,難以精準控制滑鼠的位置,所以整理格子的動作變得很辛苦,她希望能夠事先計畫好要怎麼搬動格子裡的東西,使得她搬動的次數盡可能地少。

  補充說明搬動道具消耗欄中物品的方法。搬動的過程都是用滑鼠操作的,點擊一個有放東西的格子,就可以把那一格的東西拿起來,然後再點擊另一格,就會把東西放下去。點選的這兩格不可以有不同的物品。而如果放下去以後總數超過一格放置數量的上限 (藥水100或箭1000),那麼就只會把該格數量補到上限,剩下的會留在原來拿起來的那一格。這樣地「拿起來→放下去」的過程算是搬動一次。

  請你試著寫一個程式,給定一個未整理過的道具消耗欄,有效率地計算出至少需要多少次的搬動,以將道具依照上述的規定整理。

Input Format

  輸入的第一行將有一個整數,表示有幾組測試資料,然後依序就是這幾組測試資料。每一組測試資料的第一行也是一個整數 N (0 ≤ N ≤ 40),表示這組測試資料裡原本的消耗欄裡有幾格物品,爾後的N行就是這些格子的資料,每一行會有兩項,第一項是物品的名稱,第二項是該項物品的數量。

  補充物品的名稱如下。
   水類:RedWater、OrangeWater、BlueWater、WhiteWater。
   箭類:Arrow、Bolt、BrozenArrow、BrozenBolt、IronArrow、IronBolt。

Output Format

  對於每一組測試資料,請輸出一個數字於一行中,表示整理該道具消耗欄所需最少的搬動次數。

Sample Input

2
5
Arrow 3
Arrow 10
Arrow 100
Arrow 6
Arrow 25
8
WhiteWater 20
BlueWater 70
BlueWater 40
Arrow 980
BlueWater 30
Arrow 1000
Arrow 30
BlueWater 60

Sample Output

4
3

Hints

範例1是把所有的都放到同一格;
範例2是下列3個:
把 BlueWater 30放到BlueWater 70
把BlueWater 60放到BlueWater 40
把Arrow 30放到Arrow 980 (還會剩10在原來放Arrow 30的格子裡)
也有其他種搬法,只要搬的次數一樣少,都可以。

Problem Source

原TIOJ1075 / NPSC2005決賽(prob D)

Subtasks

For Testdata: 0 ~ 0, Score: 100
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 30000 65536 65536