回分類題庫
h110: C.蚯蚓的遺跡保衛戰2
關鍵字: NPSC 2012 高中組決賽

測資點 : 2 | Time Limit : 10000 ms | Memory Limit : 128000 KB
Accepted : 20 Times / 17 Users | Submit : 70 Times / 20 Users | Accepted rate : 85%
題目加入時間 : 2013-11-07 13:27

Content: 简体中文

有一款遊戲叫做遺跡保衛戰。最近出了第二集,轟動了蚯蚓界,而蚯蚓界霸者—老蚯,也不能跟不上流行。但不幸的是,雖然身為蚯蚓界的霸者,但仍是遊戲界的菜鳥。於是他要他的謀士,也就是你,幫他規劃一下玩遊戲的策略。

這遊戲始創於胖胖天界,後來傳到蚯蚓界的時候,規則有做了一些修改,畢竟這是蚯蚓的世界。首先遊戲主角每秒鐘會得到一塊錢,可以用來買裝備加強自身的能力。但是每件裝備都會有不同的價格和增益效果(例如提昇力量、加強攻擊力. . . ),為了方便起見,我們把增益效果都量化成一個整數,稱之為增益值。所以,第 i 件裝備的價格是 pi 以及增益值是 bi。 

有趣的是同類型的裝備們會融合,例如你買了兩雙鞋子,增益值分別是 b1, b2。他們會自己組合成一雙增益值為 b1+b2 的裝備。所以你不用考慮買太多裝備的問題,買就對了! 

話說回來,這遊戲有個限制,要求你必須先買下"老蚯的祝福",才可以開始購買其他裝備。而"老蚯的祝福"這件裝備,價值 1 塊錢且增益值為 1。

接下來,他想要盡快買齊他想要的 n 件裝備。然而,雖然有很多種方式都能在最短的時間買齊所有裝備,但有些成效很差。舉例來說有時候直接存錢買比較貴的裝備不一定比較好,因為這樣做的話,可能會導致遊戲前期沒辦法買太好的裝備,那麼前期的裝備太弱會玩得很辛苦。

於是老蚯希望你幫他挑選一個買裝備的策略,使得從遊戲一開始(時間 0)到買齊所有裝備這段時間的平均增益值最大。因為這樣的話,可以讓遊戲過程過的比較平滑,比較不會太崩潰。另外,我們定義,在某一秒鐘的增益值,為主角當前所有已買的裝備增益值總和。 

Input:

輸入檔的第一行有一個正整數 T (T<=10),表示接下來總共有幾筆測試資料。

每筆測試資料的第一行有一個整數 n (0<=n<=105),表示老蚯想買 n 件裝備。接下來會有 n 行,第 i 行有兩個整數 pi 和 bi (0<=pi, bi<=10000),分別表示第 i 件裝備的價格和增益值。注意這 n 件裝備不含"老蚯的祝福"。 

Output:

對於每一筆測試資料請輸出中間用一個空白隔開的兩個整數 p, q,分別為平均值的分子和分母。注意這個分數必須是最簡分數,也就是說 p, q 要互質,即 p 與 q 的最大公因數為 1。如果 p=0,請輸出 0 1。

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
2
3
1 10
5 5
10 1
3
1 1
5 5
10 10

Sample Output :

216 17
81 17

Hint :

範例說明: 

第一筆測試資料中,最佳策略中增益值的增長如下圖所示。

 

Author :

NPSC 2012 高中組決賽 (管理員:sagit)

  Solve it!   Status Forum