TopCoder

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

User's AC Ratio

66.7% (4/6)

Submission's AC Ratio

64.7% (11/17)

Tags

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 1

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 1

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)
2024/02/14 Update: 題敘修正(紅字)by FHVirus

Subtasks

No. Testdata Range Score
1 0 100

Testdata and Limits

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