中午十二點是個既令人期待又怕受傷害的時候……。
工作告一段落後該是起來走走、吃個飯、聊個天甚至睡個午覺的時候了。誰不希望吃到一頓可口又滿足的中餐和小睡片刻呢?可是似乎不是每個人都這麼想的……。每天中午十二點整阿正一定準時抬起頭,說聲:「走!吃飯吧!」然後聽到稀稀落落的「好」、「嗯」、「等一下」或者是「再一分鐘」。有時大家已經準備要起身了,只見有個人還緊盯著銀幕口中喃喃道:「馬上好,馬上好,再一下就好了。」這時總有幾個已經走到門邊的人想趁機多打幾行字、多算些資料或者記下「不可錯過的絕妙點子」。因此要等到全部人都放下手邊的事總是要花上不少時間。
這天同樣的事情又發生了,小正決定用科學方法估計要等多久才能等到大家都起身離開。於是他在紙上寫下周圍朋友的名字,然後依照平時的印象把每個人站起來又坐回去的模式列出來。接著在每個時間點,如果紙上的兩個人都是站起來的就用一條線連起來。這麼一來就得到了一張會隨時間變動的圖,在這張圖上如果出現了完全子圖就表示這群人同時放下了手邊的工作,站了起來。
小正發現光靠這張變動圖,恐怕要等到大家都吃完回來了才算得出多久才能出去吃飯。因此他需要一支程式幫忙。為簡單起見,假設每個人站起來的時候只要有人還在做事就會坐回去,同時每次坐回去的時間會一樣久,因此可能固定每五分鐘站起來一次。另外一個決定這張圖的因素是在十二點整時,小正邀大家出去吃飯後每個人會在多久後站起來,幸好這每個人還蠻固定的,會拖的就是會拖,乾脆的就是乾脆。
請您幫幫小正,從這張圖的描述,算算要到幾點幾分才會出現包含全部人的完全子圖?
因為小正對自己的估計不是十分有把握,因此輸入檔中會有多筆資料,每一筆是一種估計,佔一行。每行開頭有一個數字 n 代表圖上有多少人,n = 0 表示結束,不需處理這筆資料。接下來會有 2n 個整數,以一個空白隔開。第 2i - 1 和 2i 個數,fi 和 wi,分別表示第 i 個人在聽到小正的話後多久會站起來以及每次坐回去後多久會再站起來,單位都是分鐘。1 ≦ n ≦ 40;之後的 2n 個數中,對所有的 1 ≦ i ≦ n,0 ≦ fi < wi ≦ 20。
對每筆輸入請輸出一行,包含一個 12 小時制的「時:分」時間(「時」介於 1到 12 之間,分只有一位數時要補零),表示多久後才能吃到中餐。如果無論怎麼等都等不到的話,小正大概要餓肚子了,請輸出「Starvation」。
其中第二筆資料表示要到下午一點十八分才能吃到中餐。
原TIOJ1459 / NPSC2007初賽(prob B)
No. | Testdata Range | Score |
---|---|---|
1 | 0 | 100 |