11296 - Counting Solutions to an Integral Equation

Problem

給定 n 之值，請你計算等式：x + 2y + 2z = n 共有幾組解，其中x, y, z, n為非負整數。

The Input

最多有1500組測試資料，每組資料一列有一個整數 n (n < 1000001)。

The Output

請輸出每組測試資料的解。

Sample Input

2
3

Sample Output

3
3

---

原文出處

11287 - Pseudoprime Numbers

費馬定理表示對於所有的質數 p 及任何大於1的整數 a，存在 a^p == a(mod p)的關係，也就是說，將 a 的 p 次方除以 p 所得到的餘數為 a。對於某些非質數的 p 而言，存在一些滿足此關係式的 a 值，此非質數的 p 稱為"base-a pseudoprime"。

給定 2 < p <= 1,000,000,000且1 < a < p，請判斷 p 是否為"base-a pseudoprime"，是請輸出"yes"，否則請輸 出"no"。

每組測試資料給定兩個整數分別表示 p 與 a ，當 p = a = 0 表示測試資料結束。

Sample Input

3 2
10 3
341 2
341 3
1105 2
1105 3
0 0

Output for Sample Input

no
no
yes
no
yes
yes

---

原文出處

11286 - Conformity

Waterloo大學的新鮮人對於課程的選擇不盡相同，而校方希望他們所選的課程盡量一致，所以設立了一個獎項，頒發給選擇的「課程組合」為「最受歡迎的課程組合」的學生。

輸入有多組測試資料，每組資料的開頭有一個整數 n 表示新生的人數(1 <= n <= 10000)，接下來有 n 列分別為這些新生所選擇的課程代號，每列有五個表示課程代號的整數，其值介於100~499。當 n = 0 表示測試資料結束。

一組課程的受歡迎程度視所有剛好選擇該組課程的學生人數而定，如果沒有其他「課程組合」的人數比此「課程組合」的人數高，則該課程為最受歡迎的「課程組合」，請對每組測試資料輸出最受歡迎的「課程組合」的人數。

Sample Input

3
100 101 102 103 488
100 200 300 101 102
103 102 101 488 100
3
200 202 204 206 208
123 234 345 456 321
100 200 300 400 444
0

Output for Sample Input

2
3

---

原文出處

11264 - Coin Collector

Sultan到某個國家旅行，該國流通的硬幣共有 n 種，他想要儘可能的收集最多種不同的硬幣。假設他想從該國銀行提領X元，而銀行會以下列演算法兌換硬幣給他：

withdraw(x) {
    if(X == 0) return;
    令Y為其值不超過X且面額最大的硬幣。
    給客戶一個Y元的硬幣。
    withdraw(X-Y);
}


Sultan可以從銀行提領任意數量的金錢，他想要在一次的提領之中領取最多種不同的硬幣。

Input:

輸入資料的第一列有一個整數T表示測試資料的組數，每組測試資料以一個整數 n (1 <= n <= 1000)表示不同面額的硬幣數，下一列有 n 個整數C1, C2, ..., Cn分別表示硬幣的面額，且C1 < C2 < C3 < ... < Cn < 1000000000。C1必為1。

Output:

請對每組測試資料輸出Sultan一次最多可以從銀行拿到幾種不同的硬幣。

Sample Input	Sample Output
2 6 1 2 4 8 16 32 6 1 3 6 8 15 20	6 4

---

原文出處

11258 - String Partition

John是一位ACM程式題目的出題者，他這次想出一題超簡單的題目，給定一列非負整數，請將所有數值相加。

但是他在產生輸入資料時犯了一個錯誤，就是忘了在一列整數之間輸出用來分隔的空白字元，這導致所有數值都連在一起變成一列字串。

最後他將問題改成：請將該字串分割成數個以非零開頭的32位元有號整數(但可包含0)，請找出使所有數字的總和最大的分割方式，並輸出其總和。

Input
輸入資料的第一列有一個整數N(<= 500)表示測試資料的組數，每組資料一列包含最多200個位數的數字。

Output
請依題意輸出最大的數字總和。

Sample input

6
1234554321
5432112345
000
121212121212
2147483648
11111111111111111111111111111111111111111111111111111

Sample output

1234554321
543211239
0
2121212124
214748372
5555555666

---

原文出處

11247 - Income Tax

應稅總額為一個不小於 m 值的金額，必須對此應稅總額付出 x %的稅率，簡單地以此方式計算稅額會產生一些問題。例如當 m = 150000, 且稅率為 10%時，A, B兩人的應稅總額分別為145000 與 155000，所以A不需要繳稅，而B需要繳15000*0.1 = 15500的稅，其稅後收入為155000-15500=139500，雖然B比A賺更多的錢，但是其稅後收入反而變少了。

給定 m 與 x，請你找出最大的稅前收入 v，使得 v 的稅後收入小於賺的比 v 還少時的情況。你可以假設稅前收入為正整數，但稅後收入為實數。

Input

輸入資料最多有20000列，每列一組有兩個整數 m (0 < m <= 1000000000), x (0 <= x <= 100)。當 m = x = 0 表示測試資料結束。

Output

請對每組測試資料輸出最大的 v 之值，若找不到其值請輸出"Not found"。

Sample Input                            Output for Sample Input

20 10 2300 4 0 0

21 2394

---

原文出處

11246 - K-Multiple Free set

我們定義一個「不存在相對k倍的整數集合」(k-multiple free set)為一整數集合中任兩個整數中的一個不會是另一個的k倍，例如當k=2，{1, 3, 4}是合法的，但{2, 4, 5}並不是，因為4為2的2倍。

給定 n 與 k 之值，請你從1~n的整數集合中，找出最大的"k-multiple free set"共有幾個整數。

Input

輸入資料的第一列有一個整數T(1 <= T <= 1000)表示測試資料的組數，接下來有T組測試資料，每組一列有兩個整數 n (1 <= n <= 1000000000)，k (2 <= k <= 100)。

Output

請每組測試資料輸出一個整數，表示在1 ~ n之中屬於k-multiple free set的子集最多共有幾個整數。

Sample Input                            Output for Sample Input

3 10 2 100 2 1000 2

6 67 666

---

原文出處

11240 - Antimonotonicity

給定一個稱為Fred的數列，共有 n 項，且每一項的數值分別介於 1~n 之間，任一對相鄰的項其值必不相同，本題要求從Fred數列中找出稱為Mary的最長子序列滿足下列性質：

Mary[0] > Mary[1] < Mary[2] > Mary[3] < ...

Input

輸入資料的第一列有一個整數T表示測試資料的組數，T最大為50，接著有T組測試資料。每組測試資料一列，該列的第一個整數 n 表示Fred數列的項數，接下來有 n 個整數依序為數列的每一項，n 最大為30000，項與項之間以一個空白字元隔開，且每組資料的前後不會有多餘的空白字元。

Output

請對每組測試資料輸出最長子序列Mary共有幾項。

Sample Input

4
5 1 2 3 4 5
5 5 4 3 2 1
5 5 1 4 2 3
5 2 4 1 3 5

Sample Output

1
2
5
3

---

原文出處

11239 - Open Source

在學校的公佈欄上，每個開源專案名稱會以全大寫字母表示，每個欲參加專案的學生在專案名稱後寫上自已小寫的姓名(或帳號)，表示自已欲參加那個專案，請你對這些資料作整理，輸出每個專案總共參與的人數。

有時候同一個學生會在同一個專案上重複寫上自已的名字，這並不是什麼問題，只要不要重複計算人頭就好。但由於一個學生最多只能參加一個專案，所以如果發現同一個學生參加不同的專案，則該學生並不計入任何專案裡面。

最多有10,000個學生、100個專案。

Input Specification:
輸入有多組測試資料，每組資料的最後以一列以'1'開頭的字串作為結束，最後一組測試資料之後以一列以'0'開頭的字串作為所有測試資料的結束。

每組測試資料會有一到多組專案的資料表，每組資料的專案名稱以大寫表示，接下來為所有參與該專案的學生姓名，每個姓名一列。

Output Specification:
請參考範列資料，輸出所有專案名稱及其參與的學生總數，其輸出順序以參與學生的總數由大到小排列，對於相同人數的專案以專案名稱的字典順序排列。

Sample input

UBQTS TXT
tthumb
LIVESPACE BLOGJAM
philton
aeinstein
YOUBOOK
j97lee
sswxyzy
j97lee
aeinstein
SKINUX
1
0

Output for Sample Input

YOUBOOK 2
LIVESPACE BLOGJAM 1
UBQTS TXT 1
SKINUX 0

---

原文出處

11236 - Grocery store

有四個物品，請找出「其價格(幣值單位最小為1分錢，即0.01元)之總和等於四個數的乘積」之所有可能組合，例如(0.50, 1.00, 2.50, 16.00)即為其中一種可能的組合，因為0.50+1.00+2.50+16.00 = 0.50*1.00*2.50*16.00 = 20.00

Input Specification

本題無輸入資料

Output Specification

本題限定四個物品價格之總和不超過20.00元，請輸出所有可能的組合，每一個組合有四個數值，請以非遞減的方式依序輸出四個數值。你可以以任意順序輸出每一組，但請確定每一輸出組合是唯一的。

Sample Output

0.50 1.00 2.50 16.00
1.25 1.60 1.75 1.84
1.25 1.40 1.86 2.00
...

原文出處

11235 - Frequent values

給定一個有 n 個整數的數列 a1, a2, ... an，且數列以非遞減的次序排列，並給定多組整數對 i, j (1 <= i <= j <= n)，請你從 ai, ..., aj 中找出出現次數最多的數值共出現幾次。

Input Specification

輸入有多組測試資料，每組資料的第一列有兩個整數 n, q (1 <= n, q <= 100000)。下一列有 n 個以空白字元隔開的整數 a1, a2, ... an (-100000 <= ai <= 100000，其中 i 為1~n)，接下來有 q 列每列表示一組 i, j。
最後一組測試資料以一列一個0表示測試資料結束。

Output Specification

請對每次查詢的數對中找出其範圍內同一數值出現最多次的次數。

Sample Input

10 3
-1 -1 1 1 1 1 3 10 10 10
2 3
1 10
5 10
0

Sample Output

1
4
3

---

原文出處

11227 - The silver bullet.

給定一群牛羚的位置，請你找出位在同一直線上的牛羚最多有幾隻。

Input

輸入資料的第一列有一整數T(1 <= T <= 10)表示測試資料的組數，每組資料的第一列有一整數N(1 <= N <= 100)表示牛羚的數量，接下來有N列，每列有兩個實數(X, Y)表示每隻牛羚的位置(X, Y的值最多精確到小數點後兩位)，且100.00 >= X, Y >= -100.00。位置重複的牛羚只能計算一次。

Output

請參考範列資料的格式輸出資料編號、牛羚的總數、最多能連成一線的牛羚總數。

Sample input

3
5
0.00 0.00
0.00 0.00
1.00 1.00
1.00 0.00
0.00 1.00
2
0.00 0.00
0.00 0.00
6
0.00 2.00
0.00 0.00
1.00 1.00
1.00 0.00
0.00 1.00
0.00 -2.00

Sample output

Data set #1 contains 4 gnus, out of which a maximum of 2 are aligned.
Data set #2 contains a single gnu.
Data set #3 contains 6 gnus, out of which a maximum of 4 are aligned.

---

原文出處

11226 - Reaching the fix-point.

對於所有的整數 n (n > 1)，皆有唯一的一組質因數分解，例如4=2x2, 5=5, 6=2x3。

令sopf(n)表示 n 的所有質因數的總和，例如sopf(4) = 2 + 2 = 4, sopf(5) = 5, sopf(6) = 2 + 3 = 5。

由一個整數 n 開始，我們藉由sopf(n)找到下一個整數，再透過sopf(sopf(n))找到下下一個整數，以此類推，直到找到一數 f 使得 f = sopf(f)。例如由8開始，sopf(8) = 2 + 2 + 2 = 6，sopf(6) = 2 + 3 = 5，sopf(5) = 5，得到數列：8, 6, 5, 5, 5, ...。此數列共有3個不同的數值。

另外再定義 lsopf(n) 表示由 n 開始找出下一個sopf()直到重複為止，共有幾個數值，例如 lsopf(8) = 3, lsopf(4) = 1。

本題給定兩個自然數 n, m (1 < n, m)，請你找出介於 n 與 m 之間最大的 lsopf 之值。

Input

輸入資料的第一列有一個整數T(1 <= T <= 150)表示測試資料的組數，每組資料一列有兩個整數分別表示 n 與 m (1 <= n, m <= 500000)。

Output

請參考範列資料輸出格式，輸出其資料編號與介於 n, m 之間最大的 lsopf 之值。

Sample input

2
2 10
11 20

Sample output

Case #1:
3
Case #2:
4

---

原文出處

11218 - KTV

最近有一首三人合唱的歌很流行，你與朋友共九個人一同到KTV歡唱，你們決定一人只能唱一次，也就是將九個人分成三組，一組三人，每人剛好都被分派到一個組別。

但是有些人並不喜歡與另一些人搭檔，而有些組合的效果並不好聽，所以我們對所有可能的三人組合打分數，請找出9人最高的分組分數總和。

Input

輸入最多有1000組測試資料，每組資料的第一列有一個整數 n (0 < n < 81)表示所有可能的組合總數，接下來有 n 列，每列有四個整數表示一種組合，四個整數分別為a, b, c, s (1 <= a < b < c <= 9, 0 < s < 10000)，表示(a, b, c)這三人的組合其分數為 s。當 n = 0 表示測試結束。

Output

請對每組測試資料輸出其資料編號及最高的分數，若不存在任一組可能的組合則輸出-1。

Sample Input

3
1 2 3 1
4 5 6 2
7 8 9 3
4
1 2 3 1
1 4 5 2
1 6 7 3
1 8 9 4
0

Output for the Sample Input

Case 1: 6
Case 2: -1

---

原文出處

11204 - Musical instruments

The Problem

中學音樂老師Julio要將N件樂器分配給M位學生，N >= M。為了得到最適當的分配，Julio要求每位學生列出心中理想樂器排名的清單，Julio希望有最多學生能分配到心中理想樂器第一名的樂器，這可能會有很多種可能的分配方式，Julio想知道共有幾種可能的分配方式。

The Input

輸入資料的第一列有一個整數表示測試資料的組數，每組測試資料的第一列有兩個整數N, M，N表示樂器總數，M表示學生總數，且32 >= N >= M。接下來有M列，每列有N個以空白字元隔開的整數，表示每一位學生對這N個樂器的排名，第一個整數表示對第一項樂器的排名，第二個整數表示對第二項樂器 的排名，以此類推。

The Output

請對每組測試資料輸出共有幾種可能的分配方式。

Sample Input

4
10 6
1 2 3 4 5 6 7 8 9 10
4 5 6 7 8 9 10 1 2 3
6 7 8 9 10 1 2 3 4 5
7 8 9 10 1 2 3 4 5 6
9 10 1 2 3 4 5 6 7 8
9 10 3 4 5 6 7 8 1 2
12 4
3 4 5 6 7 8 9 10 1 2 11 12
7 8 9 10 1 2 6 11 12 3 4 5
4 5 6 7 8 9 10 12 1 2 3 11
12 5 6 7 8 9 10 1 2 3 4 11
6 4
2 3 1 4 5 6
2 3 1 4 5 6
6 1 2 3 4 5
5 1 2 3 4 6
2 1
1 2

Sample Output

1
2
4
1

---

原文出處

11202 - The least possible effort

Background

下圖為在一個8x8的棋盤上將西洋棋的「騎士」由1, 2, 3, ... 64的順序依序移動棋子，並使每一格剛好只經過一次的其中一種可能的移動方式。

在不同起點下，會有相同的移步方式，基於對稱性，上圖中的1, 26, 54, 7就會有相同的移步方式，只要找到其中一組解就可以輕易地找出另外三組解。

本題探討當棋盤非必然為正方形的情況。

The Problem

給定一個 n x m 的棋盤(6 <= n, m <= 10000)，請找出最少需要對幾個不同的起點做搜尋，以找出所有可能的騎士移步方式。下圖顯示基於對稱性，同一顏色的位置只需要搜尋一次，我們並不需要對每個不同的起點逐一尋找。

The Input

輸入資料的第一列有一整數 t 表示測試資料的組數，接下來每組資料一列共有兩個以空白字元隔開的整數 6 <= n, m <= 10000，分別表示棋盤為 n 列 m 行。

The Output

請對每組測試資料，輸出所有騎士的移步方式最少需要對幾個起點作搜尋。

Sample Input

3
6 9
15 10
7 13

Sample Output

15
40
28

原文出處

11231 - Black and white painting

你在逛美術館的時候發現有一幅畫僅由黑白相間的格子所構成，就好像是西洋棋盤一樣，相鄰的格子顏色皆不相同。
你很無聊地想知道，在這幅畫裡面有幾個不同位置可以嵌入一個西洋棋盤。注意，西洋棋盤的右下角一定是白色。

Input Specification

輸入有多筆測試資料，每筆資料有三個整數 n, m, c(8 <= n, m <= 40,000)，n 表示畫作方格的列數，m表示方格的行數，c恆為0或1，為0表示畫作的最右下角的方格為黑色，為1則為白色。最後一列有三個零表示測試資料結束。

Output Specification

請依題意輸出答案。

Sample Input

8 8 0
8 8 1
9 9 1
40000 39999 0
0 0 0

Sample Output

0
1
2
799700028

---

原文出處

11221 - Magic square palindromes.

魔術迴文方陣(magic square palindrome)是將一個字串以列順序的方式填入一個KxK的方陣中，且用下列四種方式讀取每個字母皆會得到與原字串相同的字串：

• 從(1, 1)開始由左至右讀取，直到該列結束後再換下一列的開頭，以此類推。
• 從(1, 1)開始由上到下讀取，直到該行結束後再換下一行的開頭，以此類推。
• 從(K, K)開始由右至左讀取，直到該列開頭再換上一列的結尾，以此類推。
• 從(K, K)開始由下到上讀取，直到該行開頭再換上一行的結尾，以此類推。
  

"Sator arepo tenet opera rotas"是較廣為人知的魔術迴文方陣字串，其中K=5 (5x5)，方陣顯示如下：

s	a	t	o	r
a	r	e	p	o
t	e	n	e	t
o	p	e	r	a
r	o	t	a	s

可發現利用上述四種方式讀取表格中的字母，所得到的字串皆相同。

Input

輸入的第一列為整數T(1 <= T <= 60)表示測試資料的組數，接下來有T列字串分別表示每組測試資料，每列字串長度皆大於零小於10,000，且包含小寫字母(a-z)、空白字元、逗號、句號、問號、驚嘆號、括號等字元，請注意，魔術迴文方陣字串僅包含26個小寫英文字母。

Output

每組測試資料輸出兩列，第一列以"Case #C:"的格式輸出測試資料的編號C(1~T)，若該字串為魔術迴文方陣，請在第二列輸出K(即方陣大小為KxK)，若否則輸出"No magic :("，請參考範例資料。

Sample input

3
sator arepo tenet opera rotas
this sentence is, quite clearly, not a magic square palindrome! but then again, you never know...
muse sun, eve.s e(y)es even use sum.

Sample output

Case #1:
5
Case #2:
No magic :(
Case #3:
5

---

原文出處

11222 - Only I did it!

有三個喜歡解題的朋友，他們傾向於解出另外兩位沒解過的題目。本題請你找出哪一位解出最多其他人沒解過的題目。

Input

輸入第一列有一個整數T(1 <= T <= 20)表示測試資料的組數，每組測試資料有三列，分別表示三個人所解的題目，每一列開頭有一個整數S(0 <= S <= 1000)表示該員所解的題數，之後的S個正整數表示所解的題號，題號小於等於10000。

Output

請輸出每組測試資料的編號，格式為"Case %C:"(C表示資料編號)。接著下一列輸出哪位朋友(1, 2, 或3號朋友)解出最多沒人解過的題目，及共有多少題，接著再依序輸出題號。如果有平手的情況，請依朋友的編號順序輸出每人的解題資料。

Sample input

4
3 1 2 3
4 4 5 6 7
5 8 9 10 11 12
2 1 5
2 2 3
3 2 3 1
6 400 401 402 403 404 405
2 101 100
7 400 401 402 403 404 405 406
1 1
1 2
1 3

Sample output

Case #1:
3 5 8 9 10 11 12
Case #2:
1 1 5
Case #3:
2 2 100 101
Case #4:
1 1 1
2 1 2
3 1 3

---

原文出處

11220 - Decoding the message.

Adrian與Maria是住在不同鎮上的親戚，他們住在農村溝通不便，為了解決溝通不便的問題，他們會請彼此常互相拜訪的父母代為傳遞訊息。

兩人不希望父母讀懂他們的訊息，所以他們決定為訊息作編碼，由於他們年紀還小，所以編碼的方式非常簡單。

一般而言，訊息是基於每個單字中特定的字母，解密的方式是將第一個單字中的第一個字母取出，第二個單字中的第二個字母取出，以此類推，若該單字的字母不夠則取下一個單字，例如要取第三個單字中的第三個字母，如果該單字只有二個字母，則跳到下一個取第四個單字中的第三個字母。

如此解碼每一列會得到一個單字。

Input

輸入的第一列有一個整數T(1 <= T <= 30)表示測試資料的組數，接下來會有一列空行。每組測試資料會有N列(1 <= N <= 100)每列有1~30個單字，單字間以一到多個空白字元隔開，且每個單字包含大小寫最多30個字母(A-Z, a-z)。輸入資料僅包含字母與空白字元。每組測試資料之後都會有一列空行。

Output

請參考範列資料輸出每組解密的資料，每組資料請以空行隔開。

Sample Input

2

Hey good lawyer
as I previously previewed
yam does a soup    

First I give money to Teresa
after I inform dad of
your horrible soup

Sample Output

Case #1:
How
are
you

Case #2:
Fine
and
you

---

原文出處