11401 - Triangle Counting

 

給定 n 個長度不同的桿子，其長度分別為 1, 2, ..., n，從中選出三個不同的桿子以組成一個三角形，請問共有幾種組合方式？

Input

每組測試資料會有一個整數 n (3 <= n <= 1000000)，當 n < 3 表示測試資料結束，且此筆資料無需輸出。

Output

請依題意分別輸出答案。

Sample Input                                                  Output for Sample Input

5 8 0

3 22

---

原文出處

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

---

原文出處