著名的費馬大定理是指:當 $n>2$ 時,$x^n+y^n=z^n$ 無整數解,這邊我們要處理的問題跟費馬大定理有點關係。

給你一個正整數 N,你的任務是算出兩個與方程式 $x^2+y^2=z^2$ 的解相關的數字。($0 < x < y < z \leq{N}$)

第一個數字是互質的數對 (triples) $(x,y,z)$ 數目。互質是指 x、y、z 沒有大於 1 的公因數。第二個數字p是在 小於等於 N 的數字內不屬於任何數對 $(x,y,z)$ 的正整數總數,這邊 x、y、z 不需要互質。

例如,$N=10$,可找到一組互質數對 $(3,4,5)$ 及 一組不互質的數對 $(6,8,10)$, 1、2、7、9 共 4 個數字沒用到。所以 $N=10$ 要輸出 1 與 4。

閱讀全文 »

紐西蘭的貨幣包含了 \$100, \$50, \$20, \$10, \$5 的紙鈔和 \$2, \$1, 50c, 20c, 10c, 5c 的硬幣。給你某金額的數字,請你寫一個程式回答:使用這些面額的紙鈔或硬幣,有多少種不同的方法可以組合成這個金額。例如:20c 可以有 4 個方法可以得到:(改變金額的順序不會增加方法數,例如 $2\times{5c}+1\times{10c}$ 和下面第 3 種方法視為同一種)

  • $1\times{20c}$
  • $2\times{10c}$
  • $1\times{10c}+2\times{5c}$
  • $4\times{5c}$
閱讀全文 »

西元67年,在羅馬和猶太人的衝突中,史學家 Josephus 和其他40個人被關在一個洞穴中。羅馬人知道 Josephus 的下落後希望他能投效羅馬帝國。但是他的同伴們卻不允許他投降。所以Josephus 建議他們彼此殺害,一個接一個,被殺的順序就由命運決定。傳統上他們決定命運的方式為:大家圍成一個圓圈,從某個人開始算起,每算到 3 個人那個人就被殺掉,如此不斷下去,直到只剩一個人。後來 Josephus 成為唯一的存活者並投降羅馬。我們有興趣的是:Josephus 如何剛好是那個存活者?真的是運氣好,還是他事先在暗地裡用 41 顆石頭練習過,或者他有一個數學的方法可以知道要站在哪一個位置才能成為最後的存活者?

聽過這個故事後,你相當的憂心要是將來某一天你也面臨同樣的情況要怎麼辦。所以你決定用你的手上型電腦寫一個程式算出應該從那個人開始算起,你才可以成為那個最後唯一存活的人。

在這個問題中,你的程式必須能解決 Josephus 描述的另一種變形。有 n 個人排成一個圓圈,面向內,依順時鐘方向編號從 1 到 n。你的位置在 1 。殺人程序由編號 i 的人開始算起(順時鐘方向),直到算到第 k 個人,那個人立刻被殺掉。然後從這個被殺的人左邊的那個人再順時鐘方向算 k 個人,那個人必須負責埋葬剛才被殺的那個人,然後回去站在剛才被殺的那個人的位置。接下來從這個人的左邊那個人算起,第 k 個人又被殺掉,如此一直下去直到只剩下一個人為止。

例如:當 n=5, k=2, i=1, 那麼被殺的順序為 2, 5, 3, 1,存活者為4。

閱讀全文 »

在這個問題中,根據所給的振幅 (Amplitude) 及頻率 (Frequency),你的程式要產生這樣的波。

Input

輸入的第一列有一個整數 n,代表有幾組測試資料。接下來每組測試資料有 2 列,各有 1 個正整數 (A、F),A 代表振幅 (A <= 9),F 代表頻率。

第一列以及各組測試資料間皆有一空白行。請參考 Sample input。

Output

每組測試資料請輸出 F 個波,每個波振幅的水平高度為 A。波本身是以其 “高度” 的內容所組成。每個波之間以一空白行分隔開來。

測試資料間也以一空白行分開。

請參考 sample output。

Sample Input

2

3
2

5
3

Sample Output

1
22
333
22
1

1
22
333
22
1

1
22
333
4444
55555
4444
333
22
1

1
22
333
4444
55555
4444
333
22
1

1
22
333
4444
55555
4444
333
22
1

超級盃又來了,為了打發中場休息時間,大家就來下注最後的結果會如何。大家下注的目標為兩隊最後的分數和,或者兩隊最後分數差的絕對值。

給你這 2 個值,你能推出這 2 隊最後的得分是多少嗎?

Input

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

每組測試資料一列,有 2 個大於等於 0 的整數 s、d,s 代表比賽結束時 2 隊分數的總和, d 代表比賽結束時 2 隊分數差的絕對值。

Output

對每組測試資料輸出一列,包含 2 個整數代表比賽結束時這 2 隊的分數,分數大的在前。如果沒有這樣的分數,請輸出「impossible」。

請記得:美式足球的分數一定是大於等於 0 的整數。

Sample Input

4
40 20
20 40
5 1
100 1

Sample Output

30 10
impossible
3 2
impossible

所謂的「三角套匯 (arbitrage)」就是在幾種外幣中做金錢的交易,期待從匯差中獲取少許的利潤。例如:1 元美金可以買 0.7 英鎊,1 元英鎊可以買 9.5 法朗,1 元法朗可以買 0.16 美金。所以如果我們把 1 元美金換成英鎊,再把英鎊換成法朗,最後再把法朗換回美金,那麼最後得到的美金將是:1*0.7*9.5*0.16=1.064 美元。也就是說我們可以從中獲取匯差 0.064 美元,相當於賺了 6.4% 。

請你寫一個程式找出是否有這樣套匯的情況,可以獲取如上所述的利益。

要產生一個成功的套匯,在換外幣的過程中,開始的幣種一定得等於最後的幣種。但是從哪一種開始都可以。

閱讀全文 »

寫一個程式從一連串的整數序列中選出最長的嚴格遞增子序列 (strictly increasing subsequence)。例如:在 1, 3, 2, 2, 4, 0 中最長的嚴格遞增子序列為 1,3, 4 或者 1, 2, 4。

Input

只有一組測試資料。

輸入包含一連串的整數,每個整數一列。請參考 Sample Input。

Output

首先輸出一列最長的嚴格遞增子序列的長度是多少。然後一列僅含有一個減號 (dash character,-)。然後接下來為這個最長的嚴格遞增子序列的內容,每個整數一列。

如果有不止一個最長的嚴格遞增子序列,請輸出在輸入中最後出現的。例如在 1, 3, 2, 2, 4, 0 中,應該輸出 1, 2, 4 而不是 1, 3, 4。

請參考 Sample Output。

Sample Input

-7
10
9
2
3
8
8
1

Sample Output

4
-
-7
2
3
8

Peter 和他的朋友打算開車去度假。他們共有 7 個人,打算開 2 部車。

出發的時刻到了,他們正準備把行李裝上車。由於他們希望 2 部車上行李的重量一樣,他們要求你寫一個程式來判斷是否可能達成這個目標。請注意,每件行李是不可以打開的。

Input

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

每組測試資料一列。含有 $n$ 個正整數 ($1\leq{n}\leq{20}$),分別代表這 $n$ 個行李的重量。所有行李重量的總和不會超過 $200$

請參考 Sample Input。

Output

對每組測試資料輸出一列,如果這 n 個行李可以分成總重量相同的 2 堆以放在 2 部車上,請輸出 YES,否則輸出 NO

Sample Input

4
1 2 1 2 1
2 3 4 1 2 5 10 50 3 50
3 5 2 7 1 7 5 2 8 9 1 25 15 8 3 1 38 45 8 1
1 2 3 4 5 6 7 8 9 10 11 12 13 93

Sample Output

NO
YES
YES
NO

McCarthy 是一個有名的資訊專家。他定義了一個遞迴的函數叫做 f91 。它輸入一個正整數 N 並且依據以下的規則傳回一個正整數:

  • 如果 $N\leq{100}$,那麼 f91(N) = f91( f91( N+11) )
  • 如果 $N\geq{101}$,那麼 f91(N) = N-10

請你寫一個程式來計算 f91。

Input

每組測試資料一列。含有 1 個正整數 N ($N\leq{1000000}$)。輸入最多有 250000 組測試資料。

$N=0$ 代表輸入結束。

Output

對每組測試資料輸出一列 f91(N)。輸出格式請參考 Sample Output。

Sample Input

500
91
0

Sample Output

f91(500) = 490
f91(91) = 91

你的任務是模擬一種叫「Accordian」的紙牌遊戲,他的遊戲規則如下:

一副撲克牌有52張牌,首先把紙牌一張一張由左到右排好(不能有重疊,所以共有52堆牌,每堆一張),當某一張牌與他左邊那張牌或者左邊的第三張牌有「Match」的時候,就把這張牌移到那張牌上面去。在這裡兩張牌「Match」指的是這兩張牌的花色(suit)或者點數(rank)一樣。當你做了一個移動之後,要察看是否還可以做其他的移動。在任何時間,只有最上面那張牌可以被移動。如果因為移動一張牌使得產生一個空格(也就是被移動的那堆牌只有一張牌),你必須把右邊所有的牌堆往左移一格。如此不斷的尋找可移動的牌,直到沒有一張牌可以移動遊戲就結束了。

在選擇可以移動的牌的時候可能有些狀況會發生。如果有兩張牌都可以移動,你應該要移動最左邊的那張牌。當一張牌可以被移動到左邊一格,或左邊三格的時候,你必須移動到左邊三格。

閱讀全文 »