Description

古典數學家很常以信件來討論各自的猜想，以下是尤拉(Euler)寄給哥德巴契(Goldbach)的一封信

“That every number which is resolvable into two prime numbers can be resolved into as many prime numbers as you like, can be illustrated and confirmed by an observation which you have formerly communicated to me, namely that every even number is a sum of two primes, and since (n-2) is also a sum of two prime numbers, n must be a sum of three, and also four prime numbers, and so on. If, however, n is an odd number, then it is certainly a sum of three prime numbers, since (n-1) is a sum of two prime numbers, and can therefore be resolved into as many prime numbers as you like. However, that every number is a sum of two primes, I consider a theorem which is quite true, although I cannot demonstrate it.”

-- Euler to Goldbach, 1742

Euler認為所有偶數的數字都可以拆成兩個質數相加，但畢竟沒有經過證明，
而且有些奇數也有可能是兩個質數相加，請你設計一個程式，
判斷某個數字n是不是可以寫N = p1+p2，(p1, p2為相異兩質數)

Input

每一行代表一個測試資料，最多有10,000行
每行都有一個正整數 (0 < n <= 100,000,000)

Output

對於每一個測試資料，有以下兩種輸出情形：
n is not the sum of two primes!
n is the sum of p1 and p2.
如果一個存在多組n = p1 + p2，則輸出p1 < p2且p2-p1的值要最小的答案

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

給你一些點的座標，把這些點用墨水畫直線連起來，使得所有的點最後都連在一起。你的任務是寫一個程式找出墨水畫出的長度最小是多少？

Input

輸入的第一列有一個整數，代表以下有幾組測試資料。

每組測試資料的第1列有一個整數n（0< n <= 100），代表點的個數。接下來有n列代表這n個點的座標，每列有2個實數

輸入的第一列與第一組測試資料間空一列，各測試資料間亦空一列。請參考Sample Input

Output

對每一組測試資料輸出墨水畫出的長度最小是多少(四捨五入到小數點後第二位)。測試資料間亦請空一列。

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

經過在百貨公司的一場血拼之後，小梅發現她身上的零錢共有17分（cent，美金貨幣單位，其他貨幣及面值請參考下方紅字部分），分別是1個dime，1個nickel，以及2個penny。隔天，小梅去便利商店買完東西後發現她身上的零錢恰好又是17分，這次是2個nickel及7個penny。小梅就在想，有幾種硬幣的組合可能湊成17分呢？經過仔細算算之後，發現共有6種。

你的問題就是：給一個金額，請你回答共有多少種硬幣組合的方式。

p.s 美國的零錢共有以下幾種硬幣以及其面值：

• penny, 1 cent
• nickel, 5 cents
• dime, 10 cents
• quarter, 25 cents
• half-dollar, 50 cents

Input

每組測試資料1列，有1個整數n（0 <= n <=30000），代表零錢的總金額。

Output

對每組測試資料請輸出共有多少種硬幣組合方式。輸出格式為以下2種其中之一。

• There are m ways to produce n cents change.
• There is only 1 way to produce n cents change.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

長短腳叔叔在爬樓的時候為了避免跌倒，他的左腳只爬奇數個階梯(1, 3, 5, ...)，右腳只爬偶數個階梯(2, 4, 6, ...)，最多可以一次爬2K個階梯

當然身為一個正常的大叔，走路不會故意連續走兩個左腳或連續走兩個右腳，一定是一左一右交替著走，

在一個不知名的山上寺廟前有N階樓梯，請問他有幾種走法可以爬到山上？

舉例來說，假如N=5, K = 2

長短腳叔叔可以{左腳1階, 右腳4階}, {左腳3階, 右腳2階}, {右腳2階, 左腳3階}, {右腳2階, 左腳1階, 右腳2階}, {右腳4階, 左腳1階}

一共有5種走法

Input

輸入第一行包含一個整數T (T < 100) 表示接下來有幾筆測資。

接下來的每組測資都有兩個數字：

N (1 <= N <= 1000)表示有幾階樓梯, 

K (1 <= K <= 50)表示他左腳可以走{1, 3, 5, ..., 2K-1}階樓梯，右腳可以走{2, 4, 6, ... 2K}階樓梯

Output

每組輸出一行輸出有幾種走法可以爬到山上，因為走法可能太多，

假設一共有X種走法，請輸出X%12345678來表示所有走法

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

阿星是神偷專業協會 (Thief Professional Committee) 的會員之一，這個協會每年都會舉辦一次偷盜大賽，比賽的規則如果

1. 每位參賽者會發配一個有限空間的黑色布袋，假設該布袋容量為R，一旦裝太多東西，很有可能會被警察抓到，所以身為一個專業的小偷是不會讓自己超載。
2. 每個人都可以從任務欄上選一張收藏品清單，清單裡面有每個博物館收藏品的大小以及該物品的價值
3. 比賽限時一個晚上，統計出每位參賽者總共偷了價值多少的收藏品
4. 而偷到收藏品價值總和最多的會員，就是該年度的MVP

阿星很想要得到這個稱號來證明自己高超的偷術，但是他不知道要怎麼樣才能在不超載（收藏品總大小不超過R）的情況下，哪一張清單才能偷到總價值最多的收藏品，他希望你能告訴他每一張清單在總大小R以內最多可以的收藏品總價值。

Input

第一行表示公佈欄上有T (T <= 100)張清單，以及布袋容量R (R <= 100)

接下來每一張清單的第一行有一個數字N (N <= 100)表示清單上有N個收藏品，之後的N行中，每行都有兩個數字W_i (1 <= W_i <= 100), V_i  (1 <= V_i <= 1,000,000)表示該收藏品的大小以及價值。

Output

每一行都要輸出“List i: value”的形式，其中i表示第i張清單，value表示這張清單中可以偷取最多總價值多少的收藏品，詳情請看Sample Output

Sample Input  Download

Sample Output  Download

Tags

Discuss