本題和 a268 基本上是同一題，只是那題測資比較變態要取 MOD，但題目是敘述是中文，可以移駕過去看完題目再回來解。

內容

The Tower of Hanoi problem is a popular one in computer science. Briefly speaking, the problem is to transfer all the disks from peg-A to peg-C using peg-B as intermediate one in such a way that at no stage a larger disk is above a smaller disk. The minimum number of moves is required for this task.

It is so well studied that one can find the sequence of moves for smaller number of disks such as 3 or 4. A trivial computer program can find the case of large number of disks also. Here we have made your task little bit difcult by making the problem more flexible. Here the disks can be placed in any peg initially.

If more than one disk is in a certain peg, then they will be in a valid arrangement (larger disk will not be on smaller ones). We will give you two such arrangements of disks. Your task is to find out the minimum number of moves which will transform the first arrangement into the second one. Of course you always have to maintain the constraint that smaller disks must be upon the larger ones.

輸入

The input data consists of several test cases. Each test case contains three lines.

The first line contains a positive number n, 1 <= n <= 30, which denotes the number of disks. The two arrangements are denoted by the next two lines. Each arrangement will be represented by n integers. The value of integer is 1, 2 or 3, which denote the disk is placed in peg-A, peg-B and peg-C respectively. For example, if the i-th (1 <= i <= n) integer is 1, the i-th disk is in peg-A. The figure shown below is an example of test case. It can be described as follows and the minimum number of moves is 6.

4
1 1 1 1
1 2 2 1

Input is terminated by a case where the value of n is zero. This case should not be processed.

4
1 1 1 1
1 2 2 1
3
1 1 1
2 2 2
3
1 2 3
3 2 1
4
1 1 1 1
1 1 1 1
0

輸出

For each test case, output the minimum number of moves as specified in the problem statement.

6
7
3
0

解題思路

本題要使用 DP 來做，所以先我們把規律整理好。

河內塔的規律

1. 由於大盤絕不在小盤上面的關係，所以每一柱都會是排序好的，只是中間會有空缺。

2. 當你要將一個高度為 n 的塔完整地從 A 柱移動至 B 柱時的最少步驟必為 2ⁿ - 1
   Ex: 移動高度為 3 的塔

   零　　　　一　　　　二　　　三　　　　四　　　　五　　　　六　　　七
   1 x x 　　 x x x 　　 x x x 　　 x x x 　　 x x x 　　 x x x 　　 x x x 　　 x 1 x
   2 x x 　　 2 x x 　　 x x x 　　 x x 1 　　 x x 1 　　 x x x 　　 x 2 x 　　 x 2 x
   3 x x 　　 3 1 x 　　 3 1 2 　　 3 x 2 　　 x 3 2 　　 1 3 2 　　 1 3 x 　　 x 3 x

   會是 2ⁿ-1 是因為每要移動高度為 n 的塔，都必須先把高度為 n-1 的塔搬開，移動盤子 n，再把搬開的 n-1 塔般回 n 上，而要移動盤子 n-1 又要移動 n-2 塔…以此類推直到 n 為盤子 1 時，移動他只需要一步(上面沒有盤子了)，接者再逆推回去
   n = 2 塔：[塔 1] + 1 + [塔 1] = 1 + 1 + 1 = 3、
   n = 3 塔：[塔 2] + 1 + [塔 2] = 3 + 1 + 3 = 7、
   n = 4 塔：[塔 3] + 1 + [塔 3] = 7 + 1 + 7 = 15、
   之後以此類推 ([]為移動該塔的步驟數)
   然後就能發現 塔 n = 2^n-1 * 2 + 1 也就等於 2ⁿ - 1。

3. 想移動下面的盤子一定要先把上面的盤子都移開，所以最下面的盤子一定是最後一個動的。

4. 因為河內塔只有三根柱子、且大盤不能放到小盤上，所以如果你要把第 n 盤從 A 柱移動到 B 柱時，那你就必須要把所有比 n 還小的盤子都放到 C 柱上，換句話說，所有比 n 小的盤子都必須要移動到不是盤子 n 原本的柱或目標柱(也就是剩下的那柱)，而如果 n 原本的柱子就是目標柱，那就要把比 n 小的盤子堆到 n 所在的柱子上，維持塔的完整性，這樣之後下面的盤子才動的了。

5. 承 1 和 4，既然已經排序好、且比 n 小的都在 C 柱上，那 C 柱就一定會有一個 n-1 的子塔(從 n-1 ~ 1，排好、且中間無空缺的塔)

規律分析

1. 因為最下面的最後才能動，所以 DP 要由上而下

2. 每要移動 n 就會把 n 以上的盤子堆成一座 n-1 的子塔

3. 隨著不斷的 DP，要移動的就越底層，子塔就會越高

4. n 子塔的位子要在 不是 n+1 盤子的位子或目的地的最後一處，如果盤子的位置和目的地相同，那 n 子塔則也要和他們在相同位子，這裡有個技巧，用如果用 1,2,3 來表示柱子，這時候

   [n 子塔的位子] = 6 - [n-1 盤當前位子] - [n-1 盤目標位子]

   至於原因…因為 1 + 2 + 3 = 6，所以 6 減任意兩數(柱)就必然會剩下最後一個沒被用到的數(柱)，而當 6 - 2 - 2 時輸出為 2，一樣符合條件，不過 當前位子 = 目標位子 的情況在實作時都會在前面被過濾掉就是了。

5. 所以 DP 要做的就是從底部開始找出每層的目標位置，再從頂部開始把每層移動至目標位置 (子塔會在配合移動時越建越高，最後高度必是底部 - 1 ~ 1)。

到此為止是快速求出混亂河內塔還原回一個完整塔所需步驟的方法，但根據題目的目標也可能是混亂的，所以排好之後又要打亂，但好消息是打亂遠比還原輕鬆得多，從底部開始，如果”盤 n”的目標柱跟當前柱不一樣，就把”塔 n-1”搬到剩下的柱，把”盤 n”移至目標位置，如此反覆直到最頂層即可。

一些雜項

1. 本題 DP 的其實就是這 4 個部分 : 做好的子塔的高度和位置、要移動的盤子的初始位置和目標位置，然後從上到下排好、再從下到上放到目標位置。

2. 從頂層開始起始陣列有可能會連續好幾個一樣
   Ex:

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

   這時候直接把 3 開始當子塔可以省掉一些判斷時間。

3. 從底部開始陣列有可能起始位置 = 目標位置，這些都是不用排的，一樣可以在開始過濾掉。

4. 雖然上面多次提到要移動子塔，但由於子塔一定只會在某一柱上，所以不用真的把陣列的元素都改到子塔位置，用一個元素代表子塔位置即可。

5. 河內塔邏輯比較複雜，多用紙筆模擬幾次情境會比較好理解上述的規律和流程。

#include <stdio.h>

unsigned long long steps;
int step[35], n, base;
char now[35], to[35], end[35], curr;

int main()
{
    for (int i = 0; i < 31; i++)
        step[i] = 1 << i;
    while (scanf(" %d", &n) == 1 && n)
    {
        steps = 0, base = 1;
        for (int i = 1; i <= n; i++)
            scanf(" %d", &now[i]);
        for (int i = 1; i <= n; i++)
            scanf(" %d", &end[i]);
        while (now[n] == end[n] && n)
            n--;
        if (n)
        {
            while (now[base + 1] == now[1] && base < n - 1)
                base++;
            to[n] = end[n];
            for (int i = n; i > 1; i--)
                to[i - 1] = now[i] == to[i] ? to[i] : 6 - now[i] - to[i];
            curr = now[base];
            for (int i = base + 1; i <= n; i++)
            {
                if (now[i] == to[i]) continue;
                if (now[i] + to[i] + curr == 6)
                    steps++;
                else
                    steps += step[base], base = i - 1, curr = 6 - now[i] - to[i];
            }
            curr = to[n - 1];
            for (int i = base; i; i--)
            {
                if (curr == end[i]) continue;
                curr = 6 - curr - end[i];
                steps += step[i - 1];
            }
            printf("%llu\n", steps);
        }
        else
        {
            puts("0");
        }
    }
    return 0;
}

內容

有天，下完資訊課回家的路上，傑克發現他不小心忘了東西在電腦教室，他想要回去拿，卻怕趕不上公車，請你寫一個程式判斷他要不要回去拿。

輸入

第一行為數字 N，代表底下有 N 行測資，接下來 N 行給你你目前時間 H1 M1，與公車發車時間 H2 M2，再給你從現在的地點回去電腦教室，再去公車站的時間 M3(0<=H1,H2<24,0<=M1,M2<60,時間不會跨日)

2
21 00 21 15 13
20 55 21 12 20

輸出

如果趕得及回去的話，請輸出 Yes，否則請輸出 No

Yes
No

解題思路

開始和結束時間轉成只有分鐘，加上往返電腦教室的時間後相比即可。

#include <stdio.h>

int main()
{
    int kase, h1, m1, h2, m2, t;
    scanf("%d\n", &kase);
    while (kase--)
    {
        scanf(" %d %d %d %d %d", &h1, &m1, &h2, &m2, &t);
        m1 += h1 * 60 + t;
        m2 += h2 * 60;
        puts(m1 > m2 ? "No" : "Yes");
    }
    return 0;
}

內容

有一個數列，第一項的值為 1，第二項的值為第一項加 1，第三項的值為第二項加 2，第四項的值為第三項加 3 … 第 k 項的值為第 k-1 項的值加上 k-1。

給一個數字 n，請印出這個數列的第 n 項。

輸入

本題為重複輸入，有多筆測資。

每筆輸入有一個數字 n，1<=n<=500。

1
4

輸出

印出數列的第 n 項。

1
7

解題思路

簡單的動態規劃，根據題意打好答案表，之後查表輸出。

也可以不打表用數學解的方式，公式如下

f(n) = 1 + n * (n - 1) / 2

#include <stdio.h>
#define MAX 500

int list[MAX - 1] = { 0,1 };

int main()
{
    int n;
    for (int i = 1; i < MAX; i++)
        list[i + 1] = list[i] + i;
    while (scanf(" %d", &n) == 1)
    {
        printf("%d\n", list[n]);
    }
    return 0;
}

內容

你今天有 N 個長度不等的木棒，而你想知道這些木棒能組合出幾種直角三角形。

輸入

第一行有一數字 T ，代表有幾組測試資料 (1<=T<= 50)

每組測試資料包含兩行

第一行有一數字 N ，代表有幾根木棒 (1<=N<=100)

第二行有 N 個數字 a_i 以空白隔開，代表木棒的長度(1<=a_i<=100)

3
3
3 4 5
6
3 3 4 4 5 5
3
3 4 6

輸出

對於每筆測試資料輸出一行，每行包含一個數字 x 代表可以組成幾種直角三角形。

1
8
0

解題思路

1. 每種相同組合的出現個數為該組合的各棍子個數相乘

   假設: 5cm 兩個 4cm 兩個 3cm 三個
   那組合出 △543 的次數就會是 2 * 2 * 3 = 12 次

2. 計算過程中會頻繁的出現 1² ~ 100²，所以在程式開始時先打好 1~100 的次方表，之後直接取用。

3. 採用基數排序的方式儲存，所以陣列中會有部分元素為 0，沒有棍子就不可能產生組合，用 continue 跳過避免無謂的計算。

#include <stdio.h>
#define MAX 100

int main()
{
    int kase, n, tmp, p2List[110], count;
    for (int i = 1; i <= MAX; i++)
        p2List[i] = i * i;
    scanf(" %d", &kase);
    while (kase--)
    {
        count = 0;
        int list[MAX + 1] = { 0 };
        scanf(" %d", &n);
        for (int i = 0; i < n; i++)
        {
            scanf(" %d", &tmp);
            list[tmp]++;
        }
        for (int i = MAX; i > 2; i--)
        {
            if (!list[i]) continue;
            for (int j = i - 1; j > 1; j--)
            {
                if (!list[j]) continue;
                for (int k = j - 1; k; k--)
                {
                    if (list[k] && p2List[i] == p2List[j] + p2List[k])
                        count += list[i] * list[j] * list[k];
                }
            }
        }
        printf("%d\n", count);
    }
    return 0;
}

內容

上次老師的教甄題後，就想說出個分數的加、減、乘、除，也許有人出過類似題，但還是想出這題為下一題準備

輸入

每組測資有多列以 EOF 結束，每列四個整數 -9999 <=a,b,c,d <=9999 一個字元{ + - * / }以空白隔開
代表兩個分數 a/b @ c/d ，其中@為加減乘除之一。{b,d 不為 0，若為除法運算則 c 亦不為 0}

-1 2 4 -3 +
1 1 1 1 -
1 1 1 2 +
2 3 1 2 *
2 3 2 3 /

輸出

對輸入的每一列，輸出 1 個 分數的運算結果且為最簡分數 p/q ，若 p 被 q 整除，則只顯示一個整除後的整數。

-11/6
0
3/2
1/3
1

解題思路

輸入很小，直接乘法擴分，算完之後再約分回來，注意負號處理即可。

#include <stdio.h>
#define SWAP(x, y) x^=(y^=(x^=y))

int gcd(int m, int n)
{
    while (n)
    {
        m %= n;
        SWAP(m, n);
    }
    return m;
}

int main()
{
    int a, b, c, d, e, f, g;
    char op;
    while (scanf(" %d %d %d %d %c", &a, &b, &c, &d, &op) == 5)
    {
        switch (op)
        {
        case '+':
            e = a * d + c * b;
            f = b * d;
            break;
        case '-':
            e = a * d - c * b;
            f = b * d;
            break;
        case '*':
            e = a * c;
            f = b * d;
            break;
        case '/':
            e = a * d;
            f = b * c;
            break;
        default:
            break;
        }
        g = gcd(e, f);
        e /= g, f /= g;
        if (f < 0)
        {
            e = -e;
            f = -f;
        }
        if (f == 1)
            printf("%d\n", e);
        else
            printf("%d/%d\n", e, f);
    }
    return 0;
}

內容

今天是週六，但是要上課，同學還有不少人沒來，老師在白板上寫了一個題目讓我們殺時間。

f(1)=1，對>=2 的整數 k , 若 k 為偶數則 f(k) =1+ f(k/2)，k 為奇數則 f(k) = 1/f(k-1)， 問 f(k) = 30/11 時，k 為多少？

輸入

每組測資有多列以 EOF 結束，每列兩個正數數 a,b 代表 f(k)的值 a/b， 1<= a,b <= 60 ，a 及 b 以空白隔開

1 1
2 1
1 2
3 1
1 3
3 2
2 3
4 1
1 4
4 3
30 11

輸出

對每一列輸入的 a , b 輸出一列，為一個正整數 k，使 f(k) = a/b

1
2
3
4
5
6
7
8
9
10
236

解題思路

情況觀察:

當 k 為 1 時 f(k) = 1 → f(k) = 1

當 k 為偶數時 f(k) = f(k/2) + 1 → ，f(k) > 1

當 k 為奇數時 f(k) = 1 / f(k-1) → ，f(k) < 1

發現可以用 1 和 f(k) 比較來判斷 k 的奇偶，也能透過此方法推出 k 是透過哪個式子轉化成 f(k)。

可以判斷是來自哪種式子的話就可以反推原本的輸入。

當 g(k) = N 時 → g(k) = 2^k-1 (N 代表整數)

當 g(k) > 1 時 → g(k) = (g(k) + 1) * 2^floor(k)

當 g(k) < 1 時 → g(k) = g(1/k) + 1

再把 k 轉換成題目給的 a 和 b

當 a = b 時 → g(k) = 2^(a/b)-1

當 a > b 時 → g(k) = (g(a/b) + 1) * 2^floor(a/b)

當 a < b 時 → g(k) = g(b/a) + 1

用遞迴套用公式就可以逆推回剛開始的數字(答案)了。

#include <stdio.h>

long long getK(int a, int b)
{
    if (b < a)
    {
        int shift = a / b;
        a %= b;
        return a ? (getK(b, a) + 1) << shift : 1LL << (shift - 1);
    }
    else
    {
        return a == b ? 1 : getK(b, a) + 1;
    }
}

int main()
{
    int a, b;
    while (scanf(" %d %d", &a, &b) == 2)
    {
        printf("%lld\n", getK(a, b));
    }
    return 0;
}

內容

輸入兩個向量，計算向量內積值。兩個向量的內積，是各項相乘然後加總。例如 [1,2,3] 和 [4,5,6] 內積是 14+25+3*6 = 32

我們考慮高維度的稀疏向量，也就是大多數的元素都是零，只有少數不為零。資料的表示方式如下 dim1: value1 dim2: value2 dim3:value3 … 0:0 最後以 0:0 結束。例如

向量 [0,5,0,0,9,0,0,33] 是一個 8 維向量，可表示成
2:5 5:9 8:33 0:0

值為 0 的維度都可以忽略不需描述，只需記錄非零的維度。利用上述的表示法，讀取兩個向量，然後算出它們的內積。

輸入

輸入兩行，分別對應到兩個整數向量。向量維度最高不超過 2 的 31 次方。記憶體用量不超過 32 MB。每一行都是以 0:0 結束

1:5 1000:55 1000000:555 0:0
10:6 10000:66 100000:666 1000000:2 0:0

輸出

內積值
最後記得換行

1110

解題思路

輸入 HashTable 時由於 dim 不超過 2³¹所以直接把輸入的 dim 當作當 key。

因為輸入的 value 不為負值且兩項量的任意 dim 最多都只會出現一次，而只有在都出現時該 dim 才會是需要計算成內積的，所以用負負得正的觀念，第一次存入 value 時存-value，第二次又出現(兩個向量都有)時再 *-value，就會變成正值，最後在輸出時沒出現過的會是 0，只出現過一次的會是負值，出現過兩次的才是正值。就可以過濾出兩項量都出現的情況，最後將過濾出的值相加即可。

#include <stdio.h>
#include <stdlib.h>

typedef struct Hash
{
    unsigned int Key;
    int Value;
    struct Hash* Next;
}Hash;

Hash HashTable[1024];

inline void AddHash(int key, int value)
{
    Hash* now = &HashTable[key & 1023];
    while (now->Key != key)
    {
        if (now->Next == NULL)
        {
            now = now->Next = malloc(sizeof(Hash));
            now->Key = key;
            now->Next = NULL;
            now->Value = -value;
            return;
        }
        now = now->Next;
    }
    now->Value *= -value;
}

int getInner()
{
    int res = 0;
    Hash* now, * tmp;
    for (int i = 0; i < 1024; i++)
    {
        if (HashTable[i].Next != NULL)
        {
            now = HashTable[i].Next;
            do
            {
                if (now->Value > 0)
                    res += now->Value;
                tmp = now;
                now = now->Next;
                free(tmp);
            } while (now != NULL);
            HashTable[i].Next = NULL;
        }
    }
    return res;
}

int main()
{
    int n, m, v = 1;
    while (scanf(" %d:%d", &n, &m) == 2)
    {
        if (n + m)
            AddHash(n, m);
        else if (v)
            v = 0;
        else
            printf("%d\n", getInner()), v = 1;
    }
    return 0;
}

內容

輸入不同面值的銅板，然後輸入一個金額，將全部可能的找零方式列出。譬如有 3 種銅板面值分別是 1 元、5 元、10 元，假設要湊出 17 元，如果把找零方法表示成 “(1 元個數,5 元個數,10 元個數)”，總共會有下列幾種方法

(2,1,1)
(2,3,0)
(7,0,1)
(7,2,0)
(12,1,0)
(17,0,0)

排列順序的規則: 例如 (7,0,1) 先於 (12,1,0) 因為 7 比 12 小；而 (7,0,1) 和 (7,2,0) 的順序，因為第一個數目 7 和 7 相等，這時候就要比第二個數目，而由於 0 小於 2 所以 (7,0,1) 先於 (7,2,0)。

輸入

輸入有三行
第一行一個數字 N 代表有幾種不同面值的銅板 (N <= 5)
第二行就是 N 個整數，表示 N 種對應的銅板面值
第三行一個數字是要需要找零的金額

銅板面值和金額都是不超過 100 的正整數。（補充 by liouzhou_101）

3
1 5 10
17

輸出

列出每一種找零方法，用括號框住每個銅板的數量，數量之間用逗號隔開，每一種找零方法後面要換行。不同的找零方法的排列順序要依照題目的規定。

(2,1,1)
(2,3,0)
(7,0,1)
(7,2,0)
(12,1,0)
(17,0,0)

解題思路

把它想像成一棵樹，錢的種類數就是層數，錢的數量則是該子節點的數量，以範例測資為例就會變成 :

[]             (根)
[0 1 2 ... 17] (1元 => 個這層有17節點)
[0 1 2 ... 4]  (5元 => 這層有 17 * 4 = 68 個節點)
[0 1]          (10元 => 這層有 68 * 2 = 136 個節點)

如果依序走訪第 2 第 3 第 0 個節點，那(2,3,0)走訪的結果就為 1 * 2 + 5 * 3 + 10 * 0 = 17 元。

由於輸出排序為

(0,0,0) → (0,0,n) → (0,n,n) → (n,n,n)

所以用前序走訪的方式來走訪整個樹，到底部時就判斷走訪的結果是否為目標值。

剪枝 :

因為每在走訪時同一層的結果只會越來越大，所以當該層的走訪結果大於目標值時，當前和其後面的節點都必大於目標值，故可直接返回上一層。

同樣以範例測資為例：

當走訪至 (10,2) 節點時，因為是採用前序走訪的方式，所以 (10,1) 和其子節點都已經走訪過了，只剩 (10,2) , (10,3) , (10,4) 沒走訪，而 (10,2) 節點結果為 1 _ 10 + 5 _ 2 = 25，超過目標值 17，而 (10 , 3) , (10 , 4) 節點又大於 (10 , 2)，也就必定大於目標值，所以可以直接返回上一層 (也就是從 (11) 開始繼續走訪 )。

#include <stdio.h>

const char strfmt[6][20] = { "" , "(%d)\n" , "(%d,%d)\n" , "(%d,%d,%d)\n" , "(%d,%d,%d,%d)\n"  , "(%d,%d,%d,%d,%d)\n" };
int n, m, max, coin[5], cont[5];

void dfs(int sum, int lv)
{
    for (int i = 0; sum < m; i++)
    {
        if (lv < max)
            dfs(sum, lv + 1);
        sum += coin[lv];
        cont[lv]++;
    }
    if (sum == m)
        printf(strfmt[n], cont[0], cont[1], cont[2], cont[3], cont[4]);
    cont[lv] = 0;
}

int main()
{
    while (scanf(" %d", &n) == 1)
    {
        for (int i = 0; i < n; i++)
            scanf(" %d", &coin[i]);
        scanf(" %d", &m);
        max = n - 1;
        dfs(0, 0);
    }
    return 0;
}

內容

在一個(M+N) x (M+N) 的棋盤上放 M 個皇后 N 個城堡，皇后可走直走斜(八個方向的米字)，城堡只能走直(四個方向的十字)，所有的棋子互相不能吃掉對方。輸出有幾種合法的放法。

輸入

相加不大於 10 的正整數 M 和 N，表示在(M+N) x (M+N) 的棋盤上放置 M 個皇后 N 個城堡。

3 1

輸出

輸出總共有多少種安全的放法，記得答案輸出完加上換行

8

解題思路

用一個二維矩陣模擬棋盤，之後用 dfs 窮舉所有可能性。

每次都找陣列為元素值為 0 的地方放棋子，下棋後將這個棋子可以吃到的位置+1 (城堡十字、皇后米字)，重複此情況直到棋子下完(一個解)或是沒地方放棋子(無法繼續)時返回。

回收棋子時一樣找到他們能吃到的位置將它們-1 減回來。

例外情況

如果先放下城堡，又要在它的斜角處放皇后時，會因為記錄城堡時只調整十字區域的關係而無法正確的判斷，因此當要放皇后時，要反過來往左上和右上區間檢查是否有城堡存在，如果有就跳過這個。

剪枝和優化

1. 如果下棋時該位置元素 > 0 代表有至少一個棋子能吃到它，所以可以直接跳過這個元素。

2. 由於城堡和皇后都可以吃橫向的棋子，所以當某一行(row)已經有棋子時就不可能能放另一顆，故放完之後可以直接跳到下一行繼續窮舉。

3. 因為是由上而下進行判斷，且剪枝時已經把同一 row 的情況剪掉了，所以在規劃二為矩陣時，可以只調整目標位置可以吃到的左下、下、右下區間(城堡只需調整下)。

雖然說棋盤最大值為 10，但似乎沒有極端測資(Ex: 2 皇后 8 城堡)，所以測試時不要用極端測資做測試。

#include <stdio.h>

int max, count, table[11][11];

void dfs(int i, int m, int n)
{
    if (i == max)
    {
        count++;
        return;
    }
    for (int j = 0; j < max; j++)
    {
        if (table[i][j])
            continue;
        for (int k = i + 1; k < max; k++)
            table[k][j]++;
        if (m)
        {
            for (int k = i - 1, l = j - 1; k >= 0 && l >= 0; k--, l--)
                if (table[k][l] == -1) goto end;
            for (int k = i - 1, l = j + 1; k >= 0 && l < max; k--, l++)
                if (table[k][l] == -1) goto end;
            for (int k = i + 1, l = j - 1; k < max && l >= 0; k++, l--)
                table[k][l]++;
            for (int k = i + 1, l = j + 1; k < max && l < max; k++, l++)
                table[k][l]++;
            dfs(i + 1, m - 1, n);
            for (int k = i + 1, l = j - 1; k < max && l >= 0; k++, l--)
                table[k][l]--;
            for (int k = i + 1, l = j + 1; k < max && l < max; k++, l++)
                table[k][l]--;
        end:;
        }
        if (n)
            table[i][j] = -1, dfs(i + 1, m, n - 1), table[i][j] = 0;
        for (int k = i + 1; k < max; k++)
            table[k][j]--;
    }
}

int main()
{
    int m, n;
    while (scanf(" %d %d", &m, &n) == 2)
    {
        max = m + n, count = 0;
        dfs(0, m, n);
        printf("%d\n", count);
    }
    return 0;
}

內容

由文件給出 N 個 1 到 30000 間無序數正整數，其中 1≤N≤10000，同一個正整數可能會出現多次，出現次數最多的整數稱為眾數。求出它的眾數及它出現的次數。

輸入

輸入文件第一行是正整數的個數 N，第二行開始為 N 個正整數。每兩個正整數之間用一個空格隔開。

12
2 4 2 3 2 5 3 7 2 3 4 3

輸出

輸出文件有若干行（因為眾數可能不唯一）

每行兩個數（之間用 1 個空格隔開），第 1 個是眾數，第 2 個是眾數出現的次數。

2 4
3 4

解題思路

基本的基數排序，在輸入時判斷最大值可以少用一個迴圈找最大值。

本題範例輸出有誤，數字間應為一個空白。

#include <stdio.h>
#define MAX 30000

int num[MAX + 1];

int main()
{
    int n, tmp, max = 0;
    scanf(" %d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf(" %d", &tmp);
        num[tmp]++;
        if (max < num[tmp])
            max = num[tmp];
    }
    for (int i = 1; i <= MAX; i++)
        if (num[i] == max) printf("%d %d\n", i , max);
    return 0;
}