1050 - F.暗黑破壞神 - TIOJ

暗黑破壞神二(Diablo II)是一款有名的動作角色扮演遊戲。

... 這個遊戲的特色在於，每種職業都有他獨特的技能系統，當你等級越高，你可以練的技能就越多，就可以有更多 ... Togglenavigation Bulletin Problems Submissions Contests Discuss About Rank Signin Signup × Close NewProblems2020全國賽、2021全國模擬賽修復完成，2022TOI初選、2021全國賽上線囉！ 1050.F.暗黑破壞神 Submit Status Ranklist BacktoProblemsList TopCoder Caido $\text{W}ai\text{M}ai\sim$ User'sACRatio 100.0%(15/15) Submission'sACRatio 65.6%(21/32) Tags NPSC2003-NPSC-fin Description 　　暗黑破壞神二(DiabloII)是一款有名的動作角色扮演遊戲。

在遊戲你可以扮演法師、聖騎士等等不同的職業來殺怪、解謎。

這個遊戲的特色在於，每種職業都有他獨特的技能系統，當你等級越高，你可以練的技能就越多，就可以有更多的方法來解決怪物。

我們現在將暗黑破壞神裡的技能系統詳細說明： 　　‧要學習技能，你必須要有「技能點數」。

當你想練某個技能時，你可以在此技能放置一點或不只一點的技能點（當然，你放置的技能點越多，你的這招就會越厲害。

） 　　‧要如何得到「技能點數」呢？一個人物的等級從一開始的等級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級才可達到此地步。

　　你現在的任務就是要寫個程式，來解決這樣的問題：給你一個技能系統、欲練成的技能與點數，看看至少要到等級多少才能練成。

InputFormat 輸入檔包含了多筆的測試資料。

每一筆測試資料的內容如下： ‧第1行：一個正整數s，表示此技能系統中共有多少個技能。

(1<=s<=30) ‧第2~s+1行（接下來的s行）： 每一行都代表一個技能的敘述，含有技能名稱、技能等級、前置技能。

格式如下： 技能名稱技能等級前置技能個數前置技能1前置技能2...... 例如： meteor242fire_wallfire_ball 敘述著meteor(隕石)這個技能，是等級24的技能；它有兩個前置技能，一個是fire_wall(火牆)，另一個是fire_ball(火球)。

再舉一個例子： fire_mastery300 表示說fire_mastery(支配火燄)這個技能，是等級30的技能，而且此技能不需要前置技能。

你可以假設技能的名字裡不會有空白，且長度不會超過64個字元。

‧第s+2行：一個正整數n，表示想練成技能的個數。

(1<=n<=s) ‧第s+3~s+n+2行（接下來的n行）： 每一行包括了一個字串和一個正整數，代表著想練成的技能，以及要練到多少級。

格式如下： 欲練技能欲練點數 例如： fire_ball20 meteor20 fire_mastery20 warmth10 這四行就表示說，希望將fire_ball,meteor,fire_mastery這三個技能練到20點，而且將warmth這個技能練到10點。

　　以上的這s+n+2行就代表著一筆測試資料。

　　輸入檔以s=0作結束。

（你不用也不能處理這一筆不合法的測試資料） OutputFormat 　　對於每一筆測試資料，依序輸出(i)一個整數，代表「人物至少要到幾級才能練成測資要求的情況」；或是(ii)輸出字串IMPOSSIBLE，如果人物到了99級以後，還無法完全達到想要的情況。

　　請每行輸出恰一組測資的答案。

SampleInput copy 10 fire_bolt10 warmth10 inferno60 blaze121inferno fire_ball121fire_bolt fire_wall181blaze enchant182fire_ballwarmth meteor242fire_wallfire_ball fire_mastery300 hydra301enchant 4 fire_ball20 meteor20 fire_mastery20 warmth10 2 hide10 sneak61hide 1 sneak2 2 skeleton10 skeleton_mastery11skeleton 1 skeleton_mastery20 2 a10 b10 2 a50 b50 0 SampleOutput copy 75 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」。

ProblemSource 原TIOJ1050/NPSC2003決賽(probF) Subtasks No. TestdataRange Score 1 0 100 TestdataandLimits No. TimeLimit(ms) MemoryLimit(KiB) OutputLimit(KiB) Subtasks 0 1000 65536 262144 1 Submit Status Ranklist BacktoTop