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

---

原文出處