【目錄】ACM Online Judge

ACM Online Judge - 試題解題一覽


相關介紹

What's This
How to Start
What's Wrong


題目中譯

Lucky 貓的 ACM 園地
星子 ACM 小窩
ACM problemset 題目中譯


Volume I

100：The 3n + 1 problem
101：The Blocks Problem
102：Ecological Bin Packing
103：Stacking Boxes
104：Arbitrage - coming soon...
105：The Skyline Problem
107：The Cat in the Hat - coming soon...
108：Maximum Sum - coming soon...
116：Unidirectional TSP - coming soon...
147：Dollars - coming soon...
166：Making Change - coming soon...


Volume II

272：TeX Quotes
275：Expanding Fractions - coming soon...


Volume III

340：Master-Mind Hints - coming soon...
357：Let Me Count The Ways - coming soon...
392：Polynomial Showdown - coming soon...


Volume IV

406：Prime Cuts
412：Pi - coming soon...
458：The Decoder
476：Points in Figures: Rectangles
477：Points in Figures: Rectangles and Circles
483：Word Scramble
488：Triangle Wave
494：Kindergarten Counting Game


Volume V

544：Heavy Cargo - coming soon...
572：Oil Deposits
579：Clock Hands
591：Box of Bricks


Volume IX

913：Joana and the Odd Numbers


Volume C

10018：Reverse and Add
10025：The ? 1 ? 2 ? ... ? n = k problem - coming soon...
10035：Primary Arithmetic
10038：Jolly Jumpers
10055：Hashmat the brave warrior
10056：What is the Probability? - coming soon...
10062：Tell me the frequencies!
10071：Back to High School Physics
10082：WERTYU


Volume CI

10107：What is the Median?
10110：Light, more light - coming soon...
10141：Request for Proposal


Volume CII

10209：Is This Integration?
10222：Decode the Mad man


Volume CIII

10300：Ecological Premium
10340：All in All
10370：Above Average


Volume CIV

10473：Simple Base Conversion
10499：The Land of Justice


Volume CV

10550：Combination Lock
10589：Area


Volume CVI

10673：Play with Floor and Ceil
10696：f91


Volume CVII

10783：Odd Sum
10789：Prime Frequency


Volume CVIII

10812：Beat the Spread!
10878：Decode the tape


Volume CIX

10903：Rock-Paper-Scissors - coming soon...
10924：Prime Words
10929：You can say 11
10963：The Swallowing Ground


Volume CX

11059：Maximum Product


Volume CXI

11172：Relational Operators
11185：Ternary

【解題】Play with Floor and Ceil

ACM Volume CVI 10673 - Play with Floor and Ceil


The Problem

For any two integers x and k there exists two more integers p and q such that:



It’s a fairly easy task to prove this theorem, so we’d not ask you to do that. We’d ask for something even easier! Given the values of x and k, you’d only need to find integers p and q that satisfies the given equation.


Input

The first line of the input contains an integer, T (1≤T≤1000) that gives you the number of test cases. In each of the following T lines you’d be given two positive integers x and k. You can safely assume that x and k will always be less than 108.


Output

For each of the test cases print two integers: p and q in one line. These two integers are to be separated by a single space. If there are multiple pairs of p and q that satisfy the equation, any one would do. But to help us keep our task simple, please make sure that the values,



and



fit in a 64 bit signed integer.


Sample Input

3
5 2
40 2
24444 6


Sample Output

1 1
1 1
0 6


解題思考

　　由於這一題的解其實不只存在一組，所以每個人的解法可能各有差異。在這裡我只提出我的解法。


　　首先，我的想法是，先設 x = c × k + r，其中 0 ≤ r < k。換句話說，就代表 r = x mod k (r 為 x / k 的餘數)。且題目中：



　　的值為 c，而：



　　在 k 不可整除 x 的情況(即 r 不等於 0)為 c + 1；而在 k 可整除 x 的情況為 c。


　　先考慮 k 不可整除 x 的情況：x = c × p + (c + 1) × q = c × (p + q) + q = c × k + r。而在 k 可整除 x 的情況：x = c × p + c × q = c × (p + q) = c × k。

　　要讓兩種情況皆成立，則 q = r，p = k - q = k - r。

　　再將此式代入程式，這一題的答案就呼之欲出了。


參考解答(C++)

#include <iostream>

using namespace std;

int main(void)
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        int x, k;
        cin >> x >> k;

        cout << k - (x % k) << " " << (x % k) << endl;
    }

#ifndef ONLINE_JUDGE
    system("pause");
#endif

    return 0;
}

【解題】The Skyline Problem

ACM Volume I 105 - The Skyline Problem


Background

With the advent of high speed graphics workstations, CAD (computer-aided design) and other areas (CAM, VLSI design) have made increasingly effective use of computers. One of the problems with drawing images is the elimination of hidden lines -- lines obscured by other parts of a drawing.


The Problem

You are to design a program to assist an architect in drawing the skyline of a city given the locations of the buildings in the city. To make the problem tractable, all buildings are rectangular in shape and they share a common bottom (the city they are built in is very flat). The city is also viewed as two-dimensional. A building is specified by an ordered triple (L_i, H_i, R_i) where L_i and R_i are left and right coordinates, respectively, of building i and H_i is the height of the building. In the diagram below buildings are shown on the left with triples (1,11,5), (2,6,7), (3,13,9), (12,7,16), (14,3,25), (19,18,22), (23,13,29), (24,4,28)

the skyline, shown on the right, is represented by the sequence: (1, 11, 3, 13, 9, 0, 12, 7, 16, 3, 19, 18, 22, 3, 23, 13, 29, 0).




The Input

The input is a sequence of building triples. All coordinates of buildings are positive integers less than 10,000 and there will be at least one and at most 5,000 buildings in the input file. Each building triple is on a line by itself in the input file. All integers in a triple are separated by one or more spaces. The triples will be sorted by R_i, the left x-coordinate of the building, so the building with the smallest left x-coordinate is first in the input file.


The Output

The output should consist of the vector that describes the skyline as shown in the example above. In the skyline vector (v₁, v₂, v₃, ..., v_n-2, v_n-1, v_n) , the v_i such that i is an even number represent a horizontal line (height). The v_i such that i is an odd number represent a vertical line (x-coordinate). The skyline vector should represent the ``path'' taken, for example, by a bug starting at the minimum x-coordinate and traveling horizontally and vertically over all the lines that define the skyline. Thus the last entry in the skyline vector will be a 0. The coordinates must be separated by a blank space.

Sample Input

1 11 5
2 6 7
3 13 9
12 7 16
14 3 25
19 18 22
23 13 29
24 4 28


Sample Output

1 11 3 13 9 0 12 7 16 3 19 18 22 3 23 13 29 0


解題思考

　　這一題我採用暴力法來解決，即是直接紀錄每個 x 座標上的最高高度，再依題目要求輸出。

　　所以，一開始我就直接根據 x 座標建立「最大高度」陣列，即 height[i] 代表 x = i 時的大樓最大高度，並在讀入每一筆大樓資料時更新這個陣列。

　　接著，用一個變數以記錄當前高度，並初始化為 0 (沒有大樓)。再利用迴圈去判斷某 x 軸的最大高度是否不等於當前高度。若是，則輸出該點的 x 座標與其高度。並於更新當前高度後繼續執行迴圈。

　　看起來好像這樣，這一題就完成了。


　　但是，讓我們先想想看，若是把 Sample Input 第六行的 (19 18 22) 改成 (19 13 22)，使之與其間隔為一的第七行大樓的 (23 13 29) 高度相同。

　　這時，如果是正確的程式輸出結果，應該要是：

1 11 3 13 9 0 12 7 16 3 19 13 22 3 23 13 29 0

　　結果呢，你發現實際的輸出結果竟然是：

1 11 3 13 9 0 12 7 16 3 19 13 29 0

　　怎麼了？為什麼會錯呢？

　　主因是因為，以目前的紀錄法在讀入第六行的 (19 13 22) 時，height[19] 至 height[22] 的值會被更新為 13。而在讀入第七行的 (23 13 29) 時，height[23] 至 height[29] 的值會也被更新為 13。

　　(哎呀！)看出問題了嗎？在利用迴圈檢查當前高度是否相等時，由於 height[22] 與 height[23] 的值都是 13，所以原本像這樣子的結果：



　　就會被誤判為下面這樣：




　　那麼該怎麼解決呢？

　　其實，只要將 height[i] 的意義改成「介在 x = i 與 x = i + 1 間的最大高度」。

　　就這麼簡單，就可以修正這個問題囉。


參考解答(C++)

#include <iostream>

#define MAX_WEIGHT 10000

using namespace std;

int main(void)
{
    int height[MAX_WEIGHT + 1];
    memset(height, 0, sizeof(int) * (MAX_WEIGHT + 1));

    // 直接紀錄每個 x 的最大高度
    int l, h, r, bound = 0;
    while (cin >> l >> h >> r)
    {
        if (r > bound) { bound = r; }

        for (int i = l; i < r; i++)
        {
            if (h > height[i])
            {
                height[i] = h;
            }
        }
    }

    int current = 0;
    for (int i = 0; i < bound; i++)
    {
        // 尋找不同於當前高度的位置
        if (height[i] != current)
        {
            cout << i << " " << height[i] << " ";
            current = height[i];
        }
    }

    cout << bound << " " << height[bound] << endl;

#ifndef ONLINE_JUDGE
    system("pause");
#endif

    return 0;
}

【解題】Word Scramble

ACM Volume IV 483 - Word Scramble


The Problem

Write a program that will reverse the letters in each of a sequence of words while preserving the order of the words themselves.


Input

The input file will consist of several lines of several words. Words are contiguous stretches of printable characters delimited by white space.


Output

The output will consist of the same lines and words as the input file. However, the letters within each word must be reversed.


Sample Input

I love you.
You love me.
We're a happy family.


Sample Output

I evol .uoy
uoY evol .em
er'eW a yppah .ylimaf


解題思考

　　首先，避免麻煩，一開始我們就一次讀入一整行，並存在一個字串中。

　　接著，由於要顛倒次序的只有單個單字的字母順序，每個單字還是要依照順序輸出，所以我接著將原始字串以空白字元切割成多個子字串。

　　最後，將每一個單字的字母順序顛倒輸出，這一題就完成了。


參考解答(C++)

#include <iostream>
#include <cstring>

#define MAX_SIZE 1024

using namespace std;

int main(void)
{
    char line[MAX_SIZE];
    while (cin.getline(line, MAX_SIZE))
    {
        // 根據空白切割字串
        char *token = strtok(line, " ");
        while (token)
        {
            // 顛倒印出字串
            int length = strlen(token);
            for (int i = length - 1; i >= 0; i--)
            {
                cout << token[i];
            }

            token = strtok(NULL, " ");
            if (token) { cout << " "; }
        }

        cout << endl;
    }

#ifndef ONLINE_JUDGE
    system("pause");
#endif

    return 0;
}

【解題】The Swallowing Ground

ACM Volume CIX 10963 - The Swallowing Ground


The Problem

Now that the wicked is punished, there is still work to do. For example, the ground needs to seal itself up. (Otherwise, good people will accidentally fall into Hell, which is not good.)

The ground swallowed Don Giovanni by collapsing: Part of the ground collapsed--fell off to Hell--and this created a gap that swallowed Don Giovanni. The only way the ground can be fixed is by sliding landmasses to close up the gap. Here is an example. The left diagram shows the ground with a ravine. Assume that the ground extends infinitely to the north and to the south, and there are seams on the east and west ends; so the northern block can slide southward, and the southern block can slide northward. The right diagram shows the gap closed.



Here is another example. The ravine in the left diagram cannot be closed perfectly by sliding the ground northward and southward. The right diagram shows the result of the best effort: there is still a hole.



Write a program to determine if the gap can be closed. The ground is a grid with rows (a row runs east-west) and columns (a column runs north-south). Holes are cells on the grid, and the gap consists of holes.


Input

The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.

The first line contains the number of columns W of the ground to be considered. Then W lines follow, specifying the boundary of the gap by columns: a line represents a column, and the order of the lines follows the east-to-west order. Each line contains y₁, the north-most row of the gap in this column, and y₂, the south-most row of the gap in this column. Row numbers are integers between -100 and 100 inclusive.

The input specifies a valid gap: the holes separate the ground into exactly a northern block and a southern block. There are no holes embedded inside a block. There are no islands.

Note: The sample input below corresponds to the first diagram.


Output

For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line.

Output the line

yes

if the gap can be closed by sliding blocks north and south; and

no

otherwise.


Sample Input

1

5
2 1
0 -1
1 0
1 0
2 1


Sample Output

yes


解題思考

　　其實這一題分析起來，所謂的「裂口是否能接合」，即要你判斷是否每一行的 y₁ - y₂ 皆相等。

　　只要利用這個想法，用迴圈進行判定，就是題目要求的答案了。


參考解答(C++)

#include <iostream>

using namespace std;

int main(void)
{
    int n;

    cin >> n;
    for (int i = 0; i < n; i++)
    {
        if (i) { cout << endl; }

        int w;
        cin >> w;

        int y[2];
        cin >> y[0] >> y[1];

        int hole = y[0] - y[1];
        bool ok = true;
        for (int j = 1; j < w; j++)
        {
            // 判斷洞口距離是否都相等
            cin >> y[0] >> y[1];
            if (j && ok)
            {
                ok = ((y[0] - y[1]) == hole);
            }
        }

        cout << (ok ? "yes" : "no") << endl;
    }

#ifndef ONLINE_JUDGE
    system("pause");
#endif
}

【解題】You can say 11

ACM Volume CIX 10929 - You can say 11


The Problem

Your job is, given a positive number N, determine if it is a multiple of eleven.


Input

The input is a file such that each line contains a positive number. A line containing the number 0 is the end of the input. The given numbers can contain up to 1000 digits.


Output

The output of the program shall indicate, for each input number, if it is a multiple of eleven or not.


Sample Input

112233
30800
2937
323455693
5038297
112234
0


Sample Output

112233 is a multiple of 11.
30800 is a multiple of 11.
2937 is a multiple of 11.
323455693 is a multiple of 11.
5038297 is a multiple of 11.
112234 is not a multiple of 11.


解題思考

　　雖然這一題只需要判斷某數字是否為 11 的餘數，但是由於輸入的數字會高達 1000 位數，所以「直接將輸入值存入整數變數，再求得除以 11 的餘數以判斷是否為 11 的倍數」這個方法是勢必行不通的。

　　取而代之的，我們需要用字串的方式來儲存輸入的數字。所以接下來的問題就是：該如何判斷這個數字是否為 11 的倍數？

　　在這裡，我們需要用到一個關於 11 倍數的小常識，那就是：11 倍數的「奇數位數字和」與「偶數位數字和」兩者的差必定為 11 的倍數。

　　因此，採用迴圈的方式來計算奇數位數與偶數位數的和，再利用這個概念來判斷兩者的差是否為 11 的倍數，就能順利得出答案了。


參考解答(C++)

#include <iostream>
#include <string>

using namespace std;

int main(void)
{
    string s;
    while (1)
    {
        cin >> s;
        if (s == "0") { break; }

        // 計算奇數位與偶數位的和
        long sum[2] = {0, 0};
        for (int i = 0; i < s.length(); i++)
        {
            sum[i % 2] += s[i] - '0';
        }

        bool multiple = !((sum[0] - sum[1]) % 11);
        cout << s << " is " << (multiple ? "" : "not ");
        cout << "a multiple of 11." << endl;
    }

#ifndef ONLINE_JUDGE
    system("pause");
#endif
}

【解題】Prime Words

ACM Volume CIX 10924 - Prime Words


The Problem

A prime number is a number that has only two divisors: itself and the number one. Examples of prime numbers are: 1, 2, 3, 5, 17, 101 and 10007.

In this problem you should read a set of words, each word is composed only by letters in the range a-z and A-Z. Each letter has a specific value, the letter a is worth 1, letter b is worth 2 and so on until letter z that is worth 26. In the same way, letter A is worth 27, letter B is worth 28 and letter Z is worth 52.

You should write a program to determine if a word is a prime word or not. A word is a prime word if the sum of its letters is a prime number.


Input

The input consists of a set of words. Each word is in a line by itself and has L letters, where 1 ≤ L ≤ 20. The input is terminated by enf of file (EOF).


Output

For each word you should print: It is a prime word., if the sum of the letters of the word is a prime number, otherwise you should print: It is not a prime word..


Sample Input

UFRN
contest
AcM


Sample Output

It is a prime word.
It is not a prime word.
It is not a prime word.


解題思考

　　對於這一題，可以分成兩個步驟來求解。

　　首先，根據題目定義，我們需要先將輸入字串中的字母轉成數字並相加，並存在變數 sum 中。

　　完成之後，再利用迴圈從 2 到 √sum 中尋找是否有 sum 的因數(判別是否可以整除，即餘數是否為 0)。若有，則代表 sum 不是一個質數。反之，則代表 sum 是一個質數。

　　最後按照題目的要求輸出，就可以了。


參考解答(C++)

#include <iostream>
#include <string>

using namespace std;

int main(void)
{
    string s;
    while (cin >> s)
    {
        // 將字母轉換為數字
        int sum = 0;
        for (int i = 0; i < s.length(); i++)
        {
            if (s[i] >= 'a' && s[i] <= 'z')
            {
                sum += s[i] - 'a' + 1;
            }
            else if (s[i] >= 'A' && s[i] <= 'Z')
            {
                sum += s[i] - 'A' + 27;
            }
        }

        // 判斷是否為質數
        bool prime = true;
        for (int i = 2; i * i <= sum; i++)
        {
            if (sum % i == 0)
            {
                prime = false;
                break;
            }
        }

        cout << "It is " << (prime ? "" : "not ") << "a prime word." << endl;
    }

#ifndef ONLINE_JUDGE
    system("pause");
#endif

    return 0;
}

【解題】Ternary

ACM Volume CXI 11185 - Ternary


The Problem

You will be given a decimal number. You will have to convert it to its ternary (Base 3) equivalent.


Input

The input file contains at most 100 lines of inputs. Each line contains a non-negative decimal integer N(N<1000000001). Input is terminated by a line containing a negative value. This line should not be processed.


Output

For each line of input produce one line of output. This line contains the ternary equivalent of decimal value N.


Sample Input

10
100
1000
-1


Sample Output

101
10201
1101001


解題思考

　　這一題要將十進位數字轉成三進位。所以，我們要利用一個迴圈來得出這個答案。

　　在每一輪迴圈中，我們將輸入的數字 n / 3，在第 i 輪迴圈所得的餘數就代表此三進位數字的第 i 位數字。一直重複相同的步驟，直到 n 變為零為止。

　　得出每一位數字之後，再將結果輸出，就是答案了。


參考解答(C++)

#include <iostream>
#include <string>

using namespace std;

int main(void)
{
    while (1)
    {
        int n;
        cin >> n;

        if (n < 0) { break; }

        string ans;
        do
        {
            ans = static_cast<char>(n % 3 + '0') + ans;
            n /= 3;
        } while (n);

        cout << ans << endl;
    }

#ifndef ONLINE_JUDGE
    system("pause");
#endif
}

【解題】Maximum Product

ACM Volume CX 11059 - Maximum Product


The Problem

Given a sequence of integers S = {S₁, S₂, ..., S_n}, you should determine what is the value of the maximum positive product involving consecutive terms of S. If you cannot find a positive sequence, you should consider 0 as the value of the maximum product.


Input

Each test case starts with 1 ≤ N ≤ 18, the number of elements in a sequence. Each element S_i is an integer such that -10 ≤ S_i ≤ 10. Next line will have N integers, representing the value of each element in the sequence. There is a blank line after each test case. The input is terminated by end of file (EOF).


Output

For each test case you must print the message: Case #M: The maximum product is P., where M is the number of the test case, starting from 1, and P is the value of the maximum product. After each test case you must print a blank line.


Sample Input

3
2 4 -3

5
2 5 -1 2 -1


Sample Output

Case #1: The maximum product is 8.

Case #2: The maximum product is 20.


解題思考

　　對於這一題，直接利用暴力法就可以爆出來了。

　　換句話說，就是採用窮舉法，把所有連續數字的乘積都算出來，並從中找出最大值，就是答案了。


參考解答(C++)

#include <iostream>

using namespace std;

int main(void)
{
    int m = 1, n;
    while (cin >> n)
    {
        int *num = new int[n];
        for (int i = 0; i < n; i++)
        {
            cin >> num[i];
        }

        // 暴力法求解
        long long maximum = 0;
        for (int i = 0; i < n; i++)
        {
            long long product = 1;
            for (int j = i; j < n; j++)
            {
                product *= num[j];
                if (product > maximum)
                {
                    maximum = product;
                }
            }
        }

        cout << "Case #" << m++ << ": The maximum product is ";
        cout << maximum << "." << endl << endl;
    }

#ifndef ONLINE_JUDGE
    system("pause");
#endif
}

【解題】Beat the Spread!

ACM Volume CVIII 10812 - Beat the Spread!


The Problem

Superbowl Sunday is nearly here. In order to pass the time waiting for the half-time commercials and wardrobe malfunctions, the local hackers have organized a betting pool on the game. Members place their bets on the sum of the two final scores, or on the absolute difference between the two scores.

Given the winning numbers for each type of bet, can you deduce the final scores?


Input

The first line of input contains n, the number of test cases. n lines follow, each representing a test case. Each test case gives s and d, non-negative integers representing the sum and (absolute) difference between the two final scores.


Output

For each test case, output a line giving the two final scores, largest first. If there are no such scores, output a line containing "impossible". Recall that football scores are always non-negative integers.


Sample Input

2
40 20
20 40


Sample Output

30 10
impossible


解題思考

　　假設兩隊分數分別為 a、b(a ≧ b)，則兩隊分數總和為 s = a + b、兩隊分數差為 d = a - b。

　　以此便可以得出：a = (s + d) / 2、b = (s - d) / 2。

　　又因為 s + d = 2a (或是 s - d = 2b)，且 s 必大於等於 d。

　　所以在 s + d 或 s - d 為奇數，或是 s 小於 d 都輸出 "impossible"。否則則依照上面的公式輸出結果，就達成題目要求了。


參考解答(C++)

#include <iostream>

using namespace std;

int main(void)
{
    int n;

    cin >> n;
    for (int i = 0; i < n; i++)
    {
        long s, d;
        cin >> s >> d;

        // s 必大於等於 d, 且 s, d 的差(和)必為偶數
        if (s < d || ((s - d) % 2))
        {
            cout << "impossible" << endl;
        }
        else
        {
            cout << (s + d) / 2 << " " << (s - d) / 2 << endl;
        }
    }

#ifndef ONLINE_JUDGE
    system("pause");
#endif

    return 0;
}

【解題】Decode the tape

ACM Volume CVIII 10878 - Decode the tape


The Problem

Your boss has just unearthed a roll of old computer tapes. The tapes have holes in them and might contain some sort of useful information. It falls to you to figure out what is written on them.


Input

The input will contain one tape.


Output

Output the message that is written on the tape.


Sample Input

___________
| o   .  o|
|  o  .   |
| ooo .  o|
| ooo .o o|
| oo o.  o|
| oo  . oo|
| oo o. oo|
|  o  .   |
| oo  . o |
| ooo . o |
| oo o.ooo|
| ooo .ooo|
| oo o.oo |
|  o  .   |
| oo  .oo |
| oo o.ooo|
| oooo.   |
|  o  .   |
| oo o. o |
| ooo .o o|
| oo o.o o|
| ooo .   |
| ooo . oo|
|  o  .   |
| oo o.ooo|
| ooo .oo |
| oo  .o o|
| ooo . o |
|  o  .   |
| ooo .o  |
| oo o.   |
| oo  .o o|
|  o  .   |
| oo o.o  |
| oo  .  o|
| oooo. o |
| oooo.  o|
|  o  .   |
| oo  .o  |
| oo o.ooo|
| oo  .ooo|
|  o o.oo |
|    o. o |
___________

Sample Output

A quick brown fox jumps over the lazy dog.


解題思考

　　我個人認為，這題還滿有意思的。

　　雖然題目什麼都沒有告訴你，不過仔細觀察還是可以發現：tape 上的每一行其實都代表一個 ASCII 碼。


　　首先，我做了一個合理的假設：tape 上是以 'o' 代表 1、' ' 代表 0 的方式描述一個二進制的數字。而中間的 '.' 字元，則留待分析完這個二進制數字之後再來判斷用途。

　　所以，我試著將 tape 上的第一行轉換成數字：01000001，換成十進制就是 65。很明顯就是大寫 'A' 的 ASCII 碼。接著，我在將 tape 上的第二行轉換成數字：00100000，換成十進制就是 32，也就是空白字元 ' ' 的 ASCII 碼。

　　接續拿第三行、第四行做實驗之後，便可以得出一個結論：tape 上的符號，正如假設中為一個以 'o' 代表 1、' ' 代表 0 的二進制數字。而這個數字本身即代表字元的 ASCII 碼。而且，中間的 '.' 字元純粹用來混淆視聽，沒有任何用途。

　　得到這個結論，再透過程式實現，就解出這一題囉。


參考解答(C++)

#include <iostream>
#include <cstring>

using namespace std;

int main(void)
{
    char line[12];

    // 跳過第一行
    cin.getline(line, 12);

    while (1)
    {
        cin.getline(line, 12);

        // 結尾行跳出
        if (strcmp(line, "___________") == 0) { break; }

        // 將每一行轉換為 ASCII 碼
        char ch = 0;
        for (int i = 1; i <= 9; i++)
        {
            if (i == 6) { continue; }

            ch <<= 1;
            if (line[i] == 'o') { ch += 1; }
        }

        cout << ch;
    }

#ifndef ONLINE_JUDGE
    system("pause");
#endif

    return 0;
}

【解題】Prime Frequency

ACM Volume CVII 10789 - Prime Frequency


The Problem

Given a string containing only alpha-numerals (0-9, A-Z and a-z) you have to count the frequency (the number of times the character is present) of all the characters and report only those characters whose frequency is a prime number. A prime number is a number, which is divisible by exactly two different integers. Some examples of prime numbers are 2, 3, 5, 7, 11 etc.


Input

The first line of the input is an integer T (0 < T < 201) that indicates how many sets of inputs are there. Each of the next T lines contains a single set of input.

The input of each test set is a string consisting alpha-numerals only. The length of this string is positive and less than 2001.


Output

For each set of input produce one line of output. This line contains the serial of output followed by the characters whose frequency in the input string is a prime number. These characters are to be sorted in lexicographically ascending order. Here ``lexicographically ascending" means ascending in terms of the ASCII values. Look at the output for sample input for details. If none of the character frequency is a prime number, you should print `empty' (without the quotes) instead.


Sample Input

3
ABCC
AABBBBDDDDD
ABCDFFFF


Sample Output

Case 1: C
Case 2: AD
Case 3: empty


解題思考

　　看到質數，就知道要把埃氏篩法(Sieve of Eratosthenes)拿出來用啦。

　　也就是：要找到小於等於 n 的所有質數，需從最小質數 2 開始，將所有小於等於 n 的 2 的倍數標記為「非質數」。再從下一個質數 3 開始，進行相同的步驟，將所有小於等於 n 的 3 的倍數標記為「非質數」。接著再找下一個質數，不斷重複，直到找出所有小於等於 n 的質數為止。


　　通過以上方法，我先建立了所有小於 2000 的質數表。

　　接著在讀入每一筆資料、統計完不同字元的出現次數之後，再直接查表判斷出現次數是否為質數。

　　照著題目進行要求輸出，結果就出來了。


參考解答(C++)

#include <iostream>
#include <string>

#define MAX_SIZE 2000
#define WORD_NUM 62

using namespace std;

int main(void)
{
    // 預先建立質數表
    bool prime[MAX_SIZE];
    memset(prime, 1, MAX_SIZE);
    prime[0] = false;
    for (int i = 2; i * i < MAX_SIZE; i++)
    {
        if (prime[i - 1])
        {
            for (int j = 2; (i * j) < MAX_SIZE; j++)
            {
                prime[i * j - 1] = false;
            }
        }
    }

    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        string s;
        cin >> s;

        // 計算每個字元的出現次數
        int frequency[WORD_NUM];
        memset(frequency, 0, sizeof(int) * WORD_NUM);
        for (int j = 0; j < s.length(); j++)
        {
            // '0' - '9' => 0 - 9
            if (s[j] >= '0' && s[j] <= '9')
            {
                frequency[s[j] - '0']++;
            }
            // 'A' - 'Z' => 10 - 35
            else if (s[j] >= 'A' && s[j] <= 'Z')
            {
                frequency[s[j] - 'A' + 10]++;
            }
            // 'a' - 'z' => 36 - 61
            else if (s[j] >= 'a' && s[j] <= 'z')
            {
                frequency[s[j] - 'a' + 36]++;
            }
        }

        // 輸出次數為質數的字元
        cout << "Case " << i << ": ";
        bool empty = true;
        for (int j = 0; j < WORD_NUM; j++)
        {
            if (frequency[j] && prime[frequency[j] - 1])
            {
                empty = false;

                // 轉換為字元輸出
                if (j < 10)
                {
                    cout << static_cast<char>(j + '0');
                }
                else if (j < 36)
                {
                    cout << static_cast<char>(j - 10 + 'A');
                }
                else
                {
                    cout << static_cast<char>(j - 36 + 'a');
                }
            }
        }

        if (empty) { cout << "empty"; }

        cout << endl;
    }

#ifndef ONLINE_JUDGE
    system("pause");
#endif

    return 0;
}

【解題】Combination Lock

ACM Volume CV 10550 - Combination Lock


The Problem

Now that you're back to school for another term, you need to remember how to work the combination lock on your locker. A common design is that of the Master Brand, shown at right. The lock has a dial with 40 calibration marks numbered 0 to 39. A combination consists of 3 of these numbers; for example: 15-25-8. To open the lock, the following steps are taken:

• turn the dial clockwise 2 full turns
• stop at the first number of the combination
• turn the dial counter-clockwise 1 full turn
• continue turning counter-clockwise until the 2nd number is reached
• turn the dial clockwise again until the 3rd number is reached
• pull the shank and the lock will open.

Given the initial position of the dial and the combination for the lock, how many degrees is the dial rotated in total (clockwise plus counter-clockwise) in opening the lock?


Input

Input consists of several test cases. For each case there is a line of input containing 4 numbers between 0 and 39. The first number is the position of the dial. The next three numbers are the combination. Consecutive numbers in the combination will be distinct. A line containing 0 0 0 0 follows the last case.


Output

For each case, print a line with a single integer: the number of degrees that the dial must be turned to open the lock.


Sample Input

0 30 0 30
5 35 5 35
0 20 0 20
7 27 7 27
0 10 0 10
9 19 9 19
0 0 0 0


Sample Output

1350
1350
1620
1620
1890
1890


解題思考

　　這題看起來好像有點複雜，不過找出公式之後問題便可以迎刃而解。(不過感覺很怪異，似乎是題目把順時針跟逆時針寫反了？)


　　讓我們先分別求出題目五個步驟的角度值。

　　首先，假設每一筆輸入資料的四個號碼分別為 d₀、d₁、d₂、d₃。且由於轉盤共有 40 個刻度，所以一個刻度的角度值恰好為 9。

• 第一步，我們順時針旋轉兩圈。所以旋轉的角度值為：720 度。
• 第二步，我們由起始數字 d₀ 順時針旋轉到第一個號碼 d₁。所以若是 d₀ > d₁，旋轉的角度值為：(d₀ - d₁) × 9 度；若是 d₀ < d₁，旋轉的角度值為：(d₀ - d₁ + 40) × 9 度。
• 第三步，我們逆時針旋轉一圈。所以旋轉的角度值為：360 度。
• 第四步，我們由第一個數字 d₁ 逆時針旋轉到第二個號碼 d₂。所以若是 d₂ > d₁，旋轉的角度值為：(d₂ - d₁) × 9 度；若是 d₂ < d₁，旋轉的角度值為：(d₂ - d₁ + 40) × 9 度。
• 第五步，我們從第二個號碼 d₂ 順時針旋轉到第三個號碼 d₃。所以若是 d₂ > d₃，旋轉的角度值為：(d₂ - d₃) × 9 度；若是 d₂ < d₃，旋轉的角度值為：(d₂ - d₃ + 40) × 9 度。

　　利用程式將以上這些結果相加，就是答案了。


參考解答(C++)

#include <iostream>

using namespace std;

int main(void)
{
    while (1)
    {
        int d[4];
        cin >> d[0] >> d[1] >> d[2] >> d[3];

        if (d[0] == 0 && d[1] == 0 && d[2] == 0 && d[3] == 0)
        {
            break;
        }

        // 計算角度
        int degree = 120;
        degree += (d[0] - d[1] + 40) % 40;
        degree += (d[2] - d[1] + 40) % 40;
        degree += (d[2] - d[3] + 40) % 40;

        cout << degree * 9 << endl;
    }

#ifndef ONLINE_JUDGE
    system("pause");
#endif

    return 0;
}

【解題】Relational Operators

ACM Volume CXI 11172 - Relational Operators


The Problem

Some operators checks about the relationship between two values and these operators are called relational operators. Given two numerical values your job is just to find out the relationship between them that is (i) First one is greater than the second (ii) First one is less than the second or (iii) First and second one is equal.


Input

First line of the input file is an integer t (t<15) which denotes how many sets of inputs are there. Each of the next t lines contain two integers a and b (|a|,|b|<1000000001).


Output

For each line of input produce one line of output. This line contains any one of the relational operators “>”, “<” or “=”, which indicates the relation that is appropriate for the given two numbers.


Sample Input

3
10 20
20 10
10 10


Sample Output

<
>
=


解題思考

　　a 小於 b 輸出 "<"、a 大於 b 輸出 ">"、a 等於 b 輸出 "="。

　　我想，這題怎麼寫也不用多提了吧。


參考解答(C++)

#include <iostream>

using namespace std;

int main(void)
{
    int n;

    cin >> n;
    for (int i = 0; i < n; i++)
    {
        long a, b;
        cin >> a >> b;

        if (a < b)      { cout << "<"; }
        else if (a > b) { cout << ">"; }
        else            { cout << "="; }

        cout << endl;
    }

#ifndef ONLINE_JUDGE
    system("pause");
#endif

    return 0;
}

【解題】Odd Sum

ACM Volume CVII 10783 - Odd Sum


The Problem

Given a range [a, b], you are to find the summation of all the odd integers in this range. For example, the summation of all the odd integers in the range [3, 9] is 3 + 5 + 7 + 9 = 24.


Input

There can be at multiple test cases. The first line of input gives you the number of test cases, T (1 ≤ T ≤ 100). Then T test cases follow. Each test case consists of 2 integers a and b (0 ≤ a ≤ b ≤ 100) in two separate lines.


Output

For each test case you are to print one line of output - the serial number of the test case followed by the summation of the odd integers in the range [a, b].


Sample Input

2
1
5
3
5


Sample Output

Case 1: 9
Case 2: 8


解題思考

　　對於這一題的解，我們可以將之視為一個等差級數：首項為大於等於 a 的最小奇數 a'、末項為小於等於 b 的最大奇數 b'、項數為 (b' - a' + 2) / 2。

　　根據以上，我們便可以直接利用等差級數和的公式：[(a' + b') × (b' - a' + 2) / 2] / 2 = (a' + b') × (b' - a' + 2) / 4。

　　套用這個公式，答案就出來囉。


參考解答(C++)

#include <iostream>

using namespace std;

int main(void)
{
    int t;
    cin >> t;
    for (int i = 1; i <= t; i++)
    {
        int a, b;
        cin >> a >> b;

        if (a % 2 == 0) { a++; }
        if (b % 2 == 0) { b--; }

        cout << "Case " << i << ": " << ((a + b) * (b - a + 2)) / 4 << endl;
    }

#ifndef ONLINE_JUDGE
    system("pause");
#endif

    return 0;
}

【解題】f91

ACM Volume CVI 10696 - f91


Background

McCarthy is a famous theorician of computer science. In his work, he defined a recursive function, called f91, that takes as input a positive integer N and returns a positive integer defined as follows:

• If N ≤ 100, then f91(N) = f91(f91(N+11));
• If N ≥ 101, then f91(N) = N-10.

The Problem

Write a program, that computes McCarthy's f91.


Input

The input tests will consist of a series of positive integers, each integer is at most 1,000,000. There will be at most 250,000 test cases. Each number is on a line on its own. The end of the input is reached when the number 0 is met. The number 0 shall not be considered as part of the test set.


Output

The program shall output each result on a line by its own, following the format given in the sample output.


Sample Input

500
91
0


Sample Output

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


解題思考

　　這一題並不難，直接照著題目定義，用遞迴寫也可以 AC。

　　不過若是仔細分析下來，其實可以發現：當 N 小於等於 100 時，f91(N) 必等於 91。

　　總而言之，這題其實連遞迴都不需要用，只需要一個 if 條件判別就行了。


參考解答(C++)

#include <iostream>

using namespace std;

int main(void)
{
    while (1)
    {
        unsigned int n;
        cin >> n;
        if (n == 0) { break; }

        if (n <= 100)
        {
            // 若 n 小於 100, f91(n) 必等於 91
            cout << "f91(" << n << ") = 91" << endl;
        }
        else
        {
            cout << "f91(" << n << ") = " << n - 10 << endl;
        }
    }

#ifndef ONLINE_JUDGE
    system("pause");
#endif

    return 0;
}

【解題】Area

ACM Volume CV 10589 - Area


The Problem

Measuring the area of a certain shape is an important part of certain geometric problems. When the shape becomes complex it often becomes very difficult to measure the area of that geometric shape. In some of these cases some randomized algorithms helps us immensely to find the area roughly. In this problem we will find such an area with randomized algorithm.



Look at the picture above. ABCD is a square whose sides are a. A circle is drawn (1/4 th of a circle I should say) considering A as its center. Its radius is a. Three similar circles are drawn considering B, C, D as centers. Using an algorithm based on random numbers (The random number generator may be biased) you will have to find the area of the striped region.

The idea is that you will be given N pairs of random coordinates within the rectangle. If M of them are within the striped region then the approximate area of the striped region A = (M*a²/N). You are to find the approximate area using this concept.


Input

The input file contains several sets of inputs. The description of each set is given below.

The first line of each set contains two integers N (N can always be written in the form 10^k, where k is a non-negative integer less than 6), a (100>a>=10). Each of the next N lines contains two floating-point numbers, which indicates the coordinate of a point. These floating-point numbers always have seven digits after the decimal point and the coordinates are always within the rectangle. Points just on the boundaries of the striped region are considered within the striped region. Points just outside are considered out of the striped region and vice versa. Assume that the lower left corner of the rectangle is (0, 0) and top right corner is (a, a) as shown in the figure above.

Input is terminated by a set whose N is zero.


Output

For each of input you should produce one line of output. This line should contain the area of the striped region according to the formula specified above. Your answer must be exact and no floating-point errors will be tolerated. That means precision of calculation must be infinite or precision error must be zero. Output numbers should always have five digits after the decimal point.


Sample Input

1 10
5.0000000 5.0000000
0 0


Sample Output

100.00000


解題思考

　　對於這一題，我們需要做的不是去計算圖形的斜線面積，而是根據判斷輸入資料中，點位在虛線區域中的比例乘上整個方形面積來求出來的。

　　那麼，要如何得知點是否位在虛線區域中呢？其實只要運用距離公式 (√((x₂ - x₁)² + (y₂ - y₁)²) 判斷點與四個端點 (0, 0), (0, a), (a, 0), (a, a) 的距離。若是距離都小於半徑 a，就代表這個點在斜線區域中。

　　得知有幾個點在區域中，答案就不難得出囉。


參考解答(C++)

#include <iostream>
#include <iomanip>

#define SQUARE(x) (x)*(x)

using namespace std;

int main(void)
{
    // 設定顯示至小數點第五位
    cout << setiosflags(ios::fixed) << setprecision(5);

    int n, a;
    while (1)
    {
        cin >> n >> a;
        if (!n && !a) { break; }

        int p = 0;
        for (int i = 0; i < n; i++)
        {
            double x, y;
            cin >> x >> y;

            // 判斷是否在區域中
            if (SQUARE(x) + SQUARE(y) <= SQUARE(a) &&
                SQUARE(a - x) + SQUARE(y) <= SQUARE(a) &&
                SQUARE(x) + SQUARE(a - y) <= SQUARE(a) &&
                SQUARE(a - x) + SQUARE(a - y) <= SQUARE(a))
            {
                p++;
            }
        }

        cout << static_cast<double>(p) * a * a / static_cast<double>(n) << endl;
    }

#ifndef ONLINE_JUDGE
    system("pause");
#endif

    return 0;
}

【解題】The Land of Justice

ACM Volume CIV 10499 - The Land of Justice


The Problem

In the Land of Justice the selling price of everything is fixed all over the country. Nobody can buy a thing and sell it in double price. But, that created problems for the businessmen. They left their business and went to the production. So, after some days everybody was in production and nobody in business. And the people didn’t get their necessary things though the country was self-sufficient in every sector.

The government became very much anxious. But, they were intelligent enough to call the mathematicians.

The mathematicians gave a solution. They suggested setting the surface area of an object as its selling-unit instead of its volume. Actually the clever mathematicians were very much interested to establish their own business.

Now, the government asks the programmers to build the software that would calculate the profit things.

Here your job is to calculate the business profit for a solid sphere. A businessman buys a complete sphere and to maximize his profit he divides it in n equal parts. All cut should go through the axis of the sphere. And every part should look like the picture below:




Input

You are given a sequence of integers N (0 < N < 2³¹), indicating the numbers of parts of the sphere. The input file is terminated with a negative number. This number should not be processed.


Output

Calculate the profit over the sold pieces. The result should be in percentage and rounded to the nearest integer.


Sample Input

2
2
-1


Sample Output

50%
50%


解題思考

　　這一題是數學題，根本不需要什麼特別的方法。


　　首先我們知道，一個半徑為 R 的球體表面積公式為 4π × R²。而且，一個半徑為 R 的圓面積公式為 π × R²。

　　又因為，若是一顆球被切割成兩等分時，其表面積會增加四個半圓，也就是 2π × R²；而若是一顆球被切割成三等分時，其表面積會增加六個半圓，也就是 3π × R²。所以我們可以推得，若是一顆球被切割成 n 等分時，其表面積會增加 2n 個半圓，也就是 n × π × R²。

　　根據以上，我們便可以得到，當球被切成 n 等分時，表面積(利潤)將會是原來的 (n × π × R²) ÷ (4π × R²) = n / 4 = n × 25%。將這個結果寫成程式，答案就呼之欲出了。


參考解答(C++)

#include <iostream>

using namespace std;

int main(void)
{
    while (1)
    {
        long long n;
        cin >> n;

        if (n < 0) { break; }

        if (n == 1) { cout << "0%" << endl; }
        else        { cout << n * 25 << "%" << endl; }
    }

#ifndef ONLINE_JUDGE
    system("pause");
#endif

    return 0;
}

【解題】Simple Base Conversion

ACM Volume CIV 10473 - Simple Base Conversion


The Problem

In this problem you are asked to write a simple base conversion program. You will be given a hexadecimal or decimal integer number as input. You will have to output the corresponding decimal or hexadecimal number. Hexadecimal numbers always starts with a `0x' and all other numbers are to be considered as decimal numbers. There will be no invalid numbers in the input.


Input

The input file contains several lines of input. Each line contains a single non-negative number, which may be a decimal or hexadecimal number as explained in the problem statement. The decimal value of this number will be less than 2³¹. A line containing a negative decimal number terminates input. This number should not be processed. Input numbers will contain no space within them.


Output

For each line of input (Except the last one) produce one line of output. This line should contain the decimal or hexadecimal representation of the corresponding hexadecimal or decimal number. Like the input, the hexadecimal numbers in the output should be preceded by a `0x'.


Sample Input

4
7
44
0x80685
-1


Sample Output

0x4
0x7
0x2C
525957


解題思考

　　這一題要求我們做 10 進位(decimal)與 16 進位(hexadecimal)的轉換。


　　首先，我們需要直接以字串的方式讀入數字。接著，再根據字串的頭兩個字元，以判斷這個輸入數字的基底。

　　若是 16 進位轉 10 進位，則我們只需要將這個 16 進位數字中的每一位數字(其中 A 為 10、B 為 11、以此類推到 F)乘上 16 的位數 - 1 次方，再把得到的結果相加，就是這個 16 進位數字的 10 進位表示法了。

　　而若是 10 進位轉 16 進位，則我們首先需要將字串轉成整數型別儲存。轉成整數型別之後，我們將這個數字除以 16，得到的餘數就是這個數字 16 進位表示法的第一位數字。接著，再將這個數字除以 16 的餘數，即為這個數字 16 進位表示法的第二位數字。不斷重覆相同的動作，直到這個數字為 0 為止。

　　轉換完成之後，將結果輸出就達成題目要求囉。


參考解答(C++)

#include <iostream>
#include <string>

using namespace std;

int main(void)
{
    while (1)
    {
        string s;
        cin >> s;

        if (s[0] == '-') { break; }

        if (s.length() > 2 && s[0] == '0' && s[1] == 'x' )
        {
            // 將十六進位轉成十進位
            int ans = 0;
            for (int i = 2; i < s.length(); i++)
            {
                ans *= 16;
                if (s[i] >= '0' && s[i] <= '9')
                {
                    ans += s[i] - '0';
                }
                else
                {
                    ans += s[i] - 'A' + 10;
                }
            }

            cout << ans << endl;
        }
        else
        {
            cout << "0x";

            // 將字串轉為數字
            int num = 0;
            for (int i = 0; i < s.length(); i++)
            {
                num = num * 10 + s[i] - '0';
            }

            // 將十進位轉成十六進位
            string ans;
            while (num)
            {
                int r = num % 16;
                num /= 16;

                if (r < 10)
                {
                    ans = static_cast<char>(r + '0') + ans;
                }
                else
                {
                    ans = static_cast<char>(r - 10 + 'A') + ans;
                }
            }

            cout << ans << endl;
        }
    }

#ifndef ONLINE_JUDGE
    system("pause");
#endif

    return 0;
}

【解題】Triangle Wave

ACM Volume IV 488 - Triangle Wave


The Problem

In this problem you are to generate a triangular wave form according to a specified pair of Amplitude and Frequency.


Input and Output

The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.

Each input set will contain two integers, each on a separate line. The first integer is the Amplitude; the second integer is the Frequency.

For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line.

For the output of your program, you will be printing wave forms each separated by a blank line. The total number of wave forms equals the Frequency, and the horizontal ``height'' of each wave equals the Amplitude. The Amplitude will never be greater than nine.

The waveform itself should be filled with integers on each line which indicate the ``height'' of that line.

NOTE: There is a blank line after each separate waveform, excluding the last one.


Sample Input

1

3
2


Sample Output

1
22
333
22
1

1
22
333
22
1


解題思考

　　這一題本身不難，不過我的上傳卻不斷地 Time limit exceeded。


　　我的方法是，分別建立每一行要印出的字串。由於波浪的每一行都是相同的個位數字，所以我可以直接利用 memset() 函式，快速建立每一行要印出的字串。

　　接著，我將每一行字串直接組成一個「波浪字串」之後，再根據頻率重複印出字串，就達到題目的要求了。


參考解答(C++)

#include <iostream>
#include <string>

using namespace std;

int main(void)
{
    int n;
    cin >> n;

    bool first = true;
    for (int i = 0; i < n; i++)
    {
        int a, f;
        cin >> a >> f;

        string wave;
        char number[10];

        // 畫出上波浪
        for (int j = 1; j < a; j++)
        {
            memset(number, (j + '0'), j);
            number[j] = '\0';

            wave += number;
            wave += '\n';
        }

        // 畫出下波浪
        for (int j = a; j > 0; j--)
        {
            memset(number, (j + '0'), j);
            number[j] = '\0';

            wave += number;
            wave += '\n';
        }

        for (int j = 0; j < f; j++)
        {
            // 判別是否該換行
            if (first)  { first = false; }
            else        { cout << endl; }

            // 輸出波浪
            cout << wave;
        }
    }

#ifndef ONLINE_JUDGE
    system("pause");
#endif

    return 0;
}