內容

LuLu 在家無聊看電視，突然轉到一台有獎徵答，CallIn 進去答對者可以得到大筆金額，

但答錯了又浪費打電話的錢，所以 LuLu 想請你寫一個程式，幫他拿到大筆金額。

有獎徵答內容：

若給你２枚１０元硬幣，要你算出還有多少種排列組合之總數相同（不包含２枚１０元這組）？

(2/2 9:00 加強測試資料、重新整理題目內容)

輸入

有多組測試資料，每組測試資料佔一行，每行會有 m 個以空白分開的正整數，
若該組測試資料只有 0，請不要對此輸出任何數字。

(每行的總金額不會超過 50000，且數字可為 1,5,10,20,50,100,200,500,1000,2000)

範例:

給了 10,10，所以要算出總數為 20 的所有組合總數(不包含 10,10)。

1
5
10
20
50
100
200
500
1000
2000
1000 1000
1000 500 200 200 100
0

輸出

對每一組測試資料輸出有多少種用"1,5,10,20,50,100,200,500,1000,2000"所排列的組合(不包含輸入的組合)。

範例:

所有組合總數為 20 的排法有:

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
5 5 1 1 1 1 1 1 1 1 1 1
5 5 5 1 1 1 1 1
5 5 5 5
10 1 1 1 1 1 1 1 1 1 1
5 10 1 1 1 1 1
5 5 10
20

共 9 種(不包含 10 10)

所以輸出 9。

0
1
3
9
56
343
3274
135816
3995278
193386179
193386179
193386179

解題思路

經典的背包問題，用 DP 列出所有金額的可能性，而根據題意，輸入最大值為 50000，所以理論上要建一個大小為 50000 的表。

由於 1 在做 DP 時又是特別的存在 ，所以不用將 1 列熱考慮，排出 1 之後，會發現剩下的硬幣皆為 5 的倍數，而這種情況下 DP 表會變成固定每 5 個元素才改變一次，如下表

{ 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 4, 4, 4, 4, 4, 6….. }

而既然知道元素每 5 個一循環的改變那就沒必要算重複出現的元素，將硬幣同除 5 變成

money[] = { 1, 2, 4, 10, 20, 40, 100, 200, 400 }

這時候再建表會就會變成下表

{ 1, 2, 4, 6, 10, 14… }

如此把沒有意義的元素過濾掉，表的大小需求就能從 50000 降至 10000。

因為硬幣被同除 5 了，所以要將輸入除以 5 後查表，再將得到的值減 1 (題意"不包含輸入組合")輸出。

#include <stdio.h>
#define MAX 10001

const int money[] = { 1, 2, 4, 10, 20, 40, 100, 200, 400 };
unsigned long long list[MAX];
int n, tmp;
char input[1000], * st;

inline char* getUInt(unsigned int* dst, char src[])
{
    while (*src < '0')
        if (!*src++) return NULL;
    *dst = *src ^ '0';
    while (*++src >= '0')
        * dst = (*dst << 3) + (*dst << 1) + (*src ^ '0');
    return src;
}

int main()
{
    for (int i = 0; i < MAX; i++)
        list[i] = 1;
    for (int i = 0; i < 9; i++)
    {
        for (int j = money[i]; j < MAX; j++)
            list[j] += list[j - money[i]];
    }
    while (gets(input) && input[0] - '0')
    {
        n = 0, st = input;
        while (st = getUInt(&tmp, st))
            n += tmp;
        printf("%llu\n", list[n / 5] - 1);
    }
    return 0;
}

內容

小涵是妳喜歡的人，可是她現在很無聊，她選了 n 個正整數給你玩，你要從這幾個數中選出 m 個號碼。

她說：如果你能輸出這些選出數字的所有可能，她才會喜歡妳噢。 (m<=n<=100)

PS.姓名純屬杜撰，如有雷同純屬巧合。

輸入

本題有多組測試資料。

每組測試資料有一行，第一個數 n，接下來有 n 個數 A1~An，這些數不會有重覆的 ，最後有一個數 m。

若 n=0 請結束程式，不必輸出任何資料。

3 6 2 5 2
5 5 2 3 9 12 2
0

輸出

你可以輸出:

1.”我一點都不喜歡妳!!” (不含雙引號) 她就會因為過度傷心而讓你得到 WA。

2.由小到大，依序列出從這 n 個數中選出 m 個號碼的所有可能 (請參考範例測資)。她就會因為過度開心而讓你得到 AC。 全部可能輸出後請空一行。

2 5
2 6
5 6

2 3
2 5
2 9
2 12
3 5
3 9
3 12
5 9
5 12
9 12

解題思路

將讀入的數組排序好候用 dfs 遍歷指定長度的所有可能即可。

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

int n, m, list[1000], output[1000];

int cmp(const int* lhs, const int* rhs)
{
    return *lhs - *rhs;
}

void dfs(int lv, int st)
{
    if (lv == m)
    {
        for (int i = 0; i < m; i++)
            printf("%d ", output[i]);
        putchar('\n');
        return;
    }
    for (int i = st; i < n; i++)
    {
        output[lv] = list[i];
        dfs(lv + 1, i + 1);
    }
}

int main()
{
    while (scanf(" %d", &n) == 1 && n)
    {
        for (int i = 0; i < n; i++)
            scanf(" %d", &list[i]);
        qsort(list, n, sizeof(int), cmp);
        scanf(" %d", &m);
        dfs(0, 0);
    }
    return 0;
}

內容

小明為了要保證資料傳輸的隱密性，為檔案設置了一個加密金鑰，並且將金鑰藏進了一個檔案裡。收到檔案的小風得知要解譯出他所使用的加密金鑰，必須將檔案裡所有不含非數字的單字找出，加起來就是加密金鑰。可是，要求出這個金鑰，如果自己慢慢加實在是太慢了，所以請你寫一個程式來幫助他吧！

輸入

每組測資有一行，內含多個單字，每個單字之間會以空格作分隔(每一行的前後都有可能有空格，且分隔單字的空格可能不只一個)。

zerojudge 萬歲
1a6f 6 65afd 15s 1sa 12 115

輸出

請求出所有僅含數字的單字，並且加總後輸出。這些數字的總和不會超過 2 的 16 次方。

0
133

解題思路

先實作一個字串轉整的函式，如果讀到非數字字元回傳 0 ，若皆為數字則回傳轉換後的數字。

將測資用空白分割成各筆資料，再用上面實作的函式轉換各筆資料並將其加入總和，測資結束後輸出總和即可。

#include <stdio.h>
#include <string.h>

int sum;
char input[1000], * tok;

inline int getInt(char src[])
{
    int res = 0;
    for (int i = 0; src[i]; i++)
    {
        if (src[i] >= '0' && src[i] <= '9')
            res = (res << 3) + (res << 1) + (src[i] - '0');
        else
            return 0;
    }
    return res;
}

int main()
{
    while (gets(input) != NULL)
    {
        sum = 0, tok = strtok(input, " ");
        while (tok != NULL)
        {
            sum += getInt(tok);
            tok = strtok(NULL, " ");
        }
        printf("%d\n", sum);
    }
    return 0;
}

內容

今天我們如果將 a=1,b=2,c=3….以此類推下去，
將單字裡的每個文字依照上面規則轉換成數字再相加起來的話。
知識(KNOWLEDGE)只有 96 分，
努力(HARDWORK)只有 98 分，
但態度(ATTITUDE)卻是 100 分。

風台高中的 Norton 看到了上面的文章後並不相信，
他想把它們真的加起來看看，
以找到一個字可以反駁這個「態度最重要」的理論
但卻討厭換來換去的過程，
請幫他寫個程式方便他去做運算。

輸入

輸入英文單字，大小寫不限，當輸入 0 的時候就結束程式。
長度最長為 200 個字。
請參照 Sample Input。

hardwork
KNOWLEDGE
aTtitUdE
C++
0

輸出

輸出將英文單字依照題目的規則轉換成數字後相加的結果，如果中間參雜怪異的符號，請輸出 Fail；但是英文字母的大小寫並不會影響結果，也就是說 A 和 a 所代表的值是相同
的。請參照 Sample Output。

98
96
100
Fail

解題思路

遍歷輸入字串，將總分依題意加上對應的分數，遍歷結束後輸出即可。

#include <stdio.h>

const char a = 'a' - 1, A = 'A' - 1;
int score;
char input[200];

int main()
{
    while (scanf(" %s", input) == 1 && !(input[0] == '0' && input[1] == '\0'))
    {
        score = 0;
        for (int i = 0; input[i]; i++)
        {
            if (input[i] >= 'a' && input[i] <= 'z')
                score += input[i] - a;
            else if (input[i] >= 'A' && input[i] <= 'Z')
                score += input[i] - A;
            else
            {
                puts("Fail");
                score = 0;
                break;
            }
        }
        if (score)
            printf("%d\n", score);
    }
    return 0;
}

內容

蝸牛老師在一個優質高中擔任電腦老師，在學校裡有一個他專用的電腦教室。最近學校有一筆經費要幫這個電腦教室更新電腦。學校的原則是，每個上課的學生都要有自己的電腦，但是不希望購買多餘的電腦。給你蝸牛老師的任教班級數及每班人數，請你幫他算出要買幾部新電腦給學生使用。

輸入

輸入只有兩行。第一行有一個正整數 n，代表蝸牛老師的任教班級數。第二行有 n 個由空白隔開的正整數，代表各班人數。

5
42 39 41 43 30

輸出

輸出需購買的電腦數量。

43

解題思路

遍歷輸入陣列取最大值輸出即可。

#include<stdio.h>

int main()
{
    int n, tmp, max = 0;
    scanf(" %d", &n);
    while (n--)
    {
        scanf("%d", &tmp);
        if (max < tmp)
            max = tmp;
    }
    printf("%d", max);
    return 0;
}

內容

電腦課要同學分組做期末報告，分組的方式為依座號順序，每 3 個人一組。如：1, 2, 3 為第一組，4, 5, 6 為第二組….以此類推。輸入同學的座號，請判斷他在哪一組。

輸入

輸入只有一行，含有一個正整數 n，代表同學的座號。

7

輸出

輸出該同學的組別。

3

解題思路

每 3 人一組所以要除以 3，但因為 1,2 除 3 是餘 0，3 除 3 是餘 1 會不在同組，所以每個數字都加上 2 讓他們會在同一組。

#include <stdio.h>

int main()
{
    int n;
    scanf(" %d", &n);
    printf("%d\n", (n + 2) / 3);
    return 0;
}

內容

承 a004，珊珊終於學成歸國了，文文的考驗時刻也到了。走出了迎客大廳，珊珊問：「What type of year was I born in?」文文很有自信的回答：「閏年！」可是珊珊卻說：「No, It was a LEAP YEAR!」看來文文要娶到珊珊，還得先把英文練一練。

輸入

輸入的第一行有一個整數 n。接下來的 n 行每行有一個正整數 y，代表珊珊生日的西元年份。

4
1992
1993
1900
2000

輸出

對於所輸入的每個 y，要各別輸出一行。每一行由「Case i: 」開頭，其中的 i 代表第 i 筆測試資料，若 y 是閏年，請於該行接著輸出「a leap year」，否則請輸出「a normal year」。請參閱範例輸出。

Case 1: a leap year
Case 2: a normal year
Case 3: a normal year
Case 4: a leap year

解題思路

簡單的條件判斷。

#include<stdio.h>

int main()
{
    int kase, y;
    scanf(" %d", &kase);
    for (int i = 1; i <= kase; i++)
    {
        scanf(" %d", &y);
        if (!(y % 400) || !(y % 4) && (y % 100))
            printf("Case %d: a leap year\n", i);
        else
            printf("Case %d: a normal year\n", i);
    }
    return 0;
}

內容

承 a004，珊珊終於學成歸國了，文文的考驗時刻也到了。走出了迎客大廳，珊珊問：「What type of year was I born in?」文文很有自信的回答：「閏年！」可是珊珊卻說：「No, It was a LEAP YEAR!」看來文文要娶到珊珊，還得先把英文練一練。

輸入

輸入有若干行。輸入的每一行有一個正整數 y，代表珊珊生日的西元年份。輸入以 EOF 作為結束。

1992
1993
1900
2000

輸出

對於所輸入的每個 y，要各別輸出一行。若 y 是閏年，請於該行輸出「a leap year」，否則請輸出「a normal year」。

a leap year
a normal year
a normal year
a leap year

解題思路

簡單的條件判斷。

#include<stdio.h>

int main()
{
    int y;
    while (scanf(" %d", &y) != EOF)
    {
        if (!(y % 400) || !(y % 4) && (y % 100))
            puts("a leap year");
        else
            puts("a normal year");
    }
    return 0;
}

內容

承 a004，珊珊終於學成歸國了，文文的考驗時刻也到了。走出了迎客大廳，珊珊問：「What type of year was I born in?」文文很有自信的回答：「閏年！」可是珊珊卻說：「No, It was a LEAP YEAR!」看來文文要娶到珊珊，還得先把英文練一練。

輸入

輸入的每一行有一個正整數 y，代表珊珊生日的西元年份。輸入的最後一行有一個 0，代表輸入的結束，這個數字請勿做任何處理。

1992
1993
1900
2000
0

輸出

對於所輸入的每個 y，要各別輸出一行。若 y 是閏年，請於該行輸出「a leap year」，否則請輸出「a normal year」。

a leap year
a normal year
a normal year
a leap year

解題思路

簡單的條件判斷。

#include<stdio.h>

int main()
{
    int y;
    while (scanf(" %d", &y) == 1 && y)
    {
        if (!(y % 400) || !(y % 4) && (y % 100))
            puts("a leap year");
        else
            puts("a normal year");
    }
    return 0;
}

內容

承 a004，珊珊終於學成歸國了，文文的考驗時刻也到了。走出了迎客大廳，珊珊問：「What type of year was I born in?」文文很有自信的回答：「閏年！」可是珊珊卻說：「No, It was a LEAP YEAR!」看來文文要娶到珊珊，還得先把英文練一練。

輸入

輸入的第一行有一個整數 n。接下來的 n 行每行有一個正整數 y，代表珊珊生日的西元年份。

4
1992
1993
1900
2000

輸出

對於所輸入的每個 y，要各別輸出一行。若 y 是閏年，請於該行輸出「a leap year」，否則請輸出「a normal year」。

a leap year
a normal year
a normal year
a leap year

解題思路

簡單的條件判斷。

#include<stdio.h>

int main()
{
    int kase, y;
    scanf(" %d", &kase);
    while (kase--)
    {
        scanf("%d", &y);
        if (!(y % 400) || !(y % 4) && (y % 100))
            puts("a leap year");
        else
            puts("a normal year");
    }
    return 0;
}