在 Department for Bills and Coins，現今貨幣制度以新的擴展形式被提出，目的是為了適應新的經濟體系。將來，一些被稱為 e-coin 的新貨幣會被製造出來，除了傳統的價值（conventional value）外，並且賦予一個 InfoTechnological 的價值。當然，這種改良的目標就是為了落實經濟上的正義，尤其是針對那些為數眾多的網際網路公司（dotcom company），事實上，這些公司擁有很少的錢但卻擁有很多 IT 技術在裡面。因此，所有舊樣式的貨幣在新的制度下將會保持原本傳統的價值和零 InfoTechnological 值。
為了成功在新的貨幣系統下做比較，因此引進一種叫做 e-modulus 的概念。他的計算方式是 SQRT(X*X+Y*Y)，其中 X 和 Y 分別是傳統價值和 InfoTechnological 值的總和，舉例來說，有 3 元的傳統價值和 4 元的 InfoTechnological 值的錢的 e-modulus 值將會是 5 元。請記得，你必須在算出 e-modulus 之前，先分別算出傳統價值和 InfoTechnological 值的總和。
為了簡化 e-currency 這種措施，你被分派去寫一支程式。給你一個必須達到的 e-modulus 值和一列不同種類的 e-coin，計算最少需要多少 e-coin 來達到相應的 e-modulus 值。在這裡，每種 e-coin 在湊出相應的 e-modulus 時，e-coin 的使用數量上沒有限制。
輸入
第一行有一個整數 n（$0<n{\leq}100$）代表問題的數量，接著有 n 個問題：
其中第一行有兩個整數 m（$0<m{\leq}40$）、S（$0<S{\leq}300$），其中 m 是問題中 e-coin 的種類數，而 S 代表需要達到的 e-modulus 值。
接著 m 行中，每一行由一對非負整數所組成，用以描述 e-coin 的價值。
第一個整數代表傳統價值，而第二個整數代表 InfoTechnological 值。
當多於一個數字在同一行時，它們將會被空白隔開。在每個問題之間會有空白行。
輸出
輸出有 n 行，每行有一個整數代表可以達到 e-modulus 需要的貨幣數量；或是如果 S 沒辦法達到，則輸出「not possible」。
範例輸入
3
2 5
0 2
2 0
3 20
0 2
2 0
2 1
3 5
3 0
0 4
5 5
範例輸出
not possible
10
2
(Joint Effort Contest, Problem Source: Swedish National Programming Contest, arranged by department of Computer Science at Lund Institute of Technology.)
沒有留言:
張貼留言