1050 . F.暗黑破壞神
TopCoder
Tags
Description
暗黑破壞神二（Diablo II）是一款有名的動作角色扮演遊戲。在遊戲你可以扮演法師、聖騎士等等不同的職業來殺怪、解謎。這個遊戲的特色在於，每種職業都有他獨特的技能系統，當你等級越高，你可以練的技能就越多，就可以有更多的方法來解決怪物。我們現在將暗黑破壞神裡的技能系統詳細說明：
- 要學習技能，你必須要有「技能點數」。當你想練某個技能時，你可以在此技能放置一點或不只一點的技能點（當然，你放置的技能點越多，你的這招就會越厲害。）
- 要如何得到「技能點數」呢？一個人物的等級從一開始的等級 $1$ ，最高可以升到等級 $99$ 。當人物每升一級，你就可以獲得技能點數一點。此時你可以選擇馬上將此點數用掉，或是儲存起來，以後任何時候仍然可以使用。
- 由於一開始，人物等級 $1$ 時是沒有技能點數的，所以如果在升級的過程中，你把點數全部儲存起來不練技能的話，最高到 $99$ 級你會有 $98$ 點的技能點可用。
- 某些技能，必須要習得其它技能（點數不限，最少一點）才可以練。例如要練「隕石」，就必須要先會「火球」和「火牆」這兩個技能（也就是在這兩個技能各放上至少一點），所以我們稱「火球」和「火牆」為「隕石」的「前置技能」。可以參考上頁圖１，像「支配火燄」就沒有前置技能，而「火球」有一個前置技能「火彈」。
- 你可以假設在這個技能系統中，不會發生「學技能甲要先會技能乙、但學技能乙要先會技能甲」這種互依的情況。
- 某些技能，必須要等到人物達到某個等級後才可以練：我們稱之為「等級 $X$ 的技能」。要特別注意的是，對於一個等級 $X$ 的技能，要練一點時人物必須有 $X$ 級；練兩點必須要 $X+1$ 級……必須要 $X+Y-1$ 級才能練 $Y$ 點。例如對於等級 $24$ 的技能「隕石」，當人物等級 $34$ 時，最多只能練到 $11$ 點。
- 如果技能甲是技能乙的前置技能，而且技能甲是「等級 $X$ 的技能」、技能乙是「等級Y的技能」，那麼 $X$ 不會比 $Y$ 大。
- 儲存下來的技能點數，只要符合前面所述的限制，在任何等級時，可以一次將任意多的點數放在任何可升級的技能上。
現在問題來了。小瑋新接觸這個遊戲，他聽別人說，法師只要練了 $20$ 點火球、 $20$ 點隕石、 $20$ 點支配火燄、 $10$ 點暖氣，就天下無敵了。所以他想要看看他的法師最快要到等級多少的時候才能達到這種地步。
如果小瑋的法師想要變天下無敵，他至少要付出如圖二所標的，共 $74$ 點技能點。所以在考慮了前置技能和技能等級的限制後，我們發現小瑋至少要到 $75$ 級才可達到此地步。
你現在的任務就是要寫個程式，來解決這樣的問題：給你一個技能系統、欲練成的技能與點數，看看至少要到等級多少才能練成。
Input Format
輸入檔包含了多筆的測試資料。每一筆測試資料的內容如下：
- 第 $1$ 行：一個正整數 $s$ ，表示此技能系統中共有多少個技能。$(1 \le s \le 30)$
- 第 $2 \sim s+1$ 行（接下來的 $s$ 行）：每一行都代表一個技能的敘述，含有技能名稱、技能等級、前置技能。格式如下：
技能名稱 技能等級 前置技能個數 前置技能1 前置技能2 ......
例如：
meteor 24 2 fire_wall fire_ball
敘述著 meteor （隕石）這個技能，是等級 $24$ 的技能；它有兩個前置技能，一個是 fire_wall （火牆），另一個是 fire_ball （火球）。
再舉一個例子：
fire_mastery 30 0
表示說 fire_mastery （支配火燄）這個技能，是等級 $30$ 的技能，而且此技能不需要前置技能。
你可以假設技能的名字裡不會有空白，且長度不會超 $64$ 個字元。
- 第 $s+2$ 行：一個正整數 $n$ ，表示想練成技能的個數。$(1 \le n \le s)$
- 第 $s+3 \sim s+n+2$ 行（接下來的 $n$ 行）：每一行包括了一個字串和一個正整數，代表著想練成的技能，以及要練到多少級。格式如下：
欲練技能 欲練點數
例如：
fire_ball 20
meteor 20
fire_mastery 20
warmth 10
這四行就表示說，希望將 fire_ball, meteor, fire_mastery 這三個技能練到 $20$ 點，而且將 warmth 這個技能練到 $10$ 點。
以上的這 $s+n+2$ 行就代表著一筆測試資料。
輸入檔以 $s=0$ 作結束。（你不用也不能處理這一筆不合法的測試資料）
Output Format
對於每一筆測試資料，依序輸出 (i) 一個整數，代表「人物至少要到幾級才能練成測資要求的情況」；或是 (ii) 輸出字串 IMPOSSIBLE，如果人物到了 $99$ 級以後，還無法完全達到想要的情況。
請每行輸出恰一組測資的答案。
Sample Input 1
fire_bolt 1 0
warmth 1 0
inferno 6 0
blaze 12 1 inferno
fire_ball 12 1 fire_bolt
fire_wall 18 1 blaze
enchant 18 2 fire_ball warmth
meteor 24 2 fire_wall fire_ball
fire_mastery 30 0
hydra 30 1 enchant
4
fire_ball 20
meteor 20
fire_mastery 20
warmth 10
2
hide 1 0
sneak 6 1 hide
1
sneak 2
2
skeleton 1 0
skeleton_mastery 1 1 skeleton
1
skeleton_mastery 20
2
a 1 0
b 1 0
2
a 50
b 50
0
Sample Output 1
7
22
IMPOSSIBLE
Hints
在範例輸入裡共有四筆測資。第一筆測資跟最前面題目所舉例的情況是一模一樣的，可以對照圖一作參考。
第二筆測資，雖然在等級 $6$ 的時候就可以練一點 sneak ，而練完一點還會剩下三點未使用（等級 $2$ 放一點在 hide ，升等級 $3,4,5$ 時都沒用到，升等級 $6$ 時共有四點可以使用，放一點在 sneak 還剩三點），但是根據前面「等級 $6$ 技能」的定義：要放第二點在 sneak 上，必須要到等級 $7$ 才可以；所以即使在等級 $6$ 的時有三點可用的技能點，這時卻不能放第二點在 sneak 上。
第三筆測資，在升等級 $2$ 的時候放一點在 skeleton 上；升等級 $3$ 的時候放一點在 skeleton_mastery 上，以後每升一級還是照樣把新得到的技能點放在 skeleton_mastery 。所以升到等級 $22$ 時， skeleton_mastery 就可以點到二十點。（而且此時不會有多餘的技能點可用）
第四筆測資，因為人物到了 $99$ 級最多只有 $98$ 點技能點可以用，但是要達到測資要的情況，必須要有 $100$ 點技能點，所以顯然此人物到了 $99$ 級時還是無法達到要求，故輸出IMPOSSIBLE。
2022/06/02 Update by FHVirus: 你可以假設輸入中，對於每一個技能，其前置技能都會較早被輸入。
Problem Source
原TIOJ1050 / NPSC2003決賽(prob F)
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 100 |