內容

一年一度的 101 大樓爬樓梯競賽始報名囉，喜歡運動的 StillFantasy (以下簡稱 SF ) 毫不猶豫的馬上報名參加。

現在 101 大樓共有 N 階樓梯，每個參賽者都必須從第 0 階走到最後一階（也就是第 N 階），且主辦單位在某些階樓梯設有休息站（一定要剛好走到那階樓梯），提供礦泉水及 Kinder 巧克力 等零食給選手補充體力。

聰明的 SF 想了一個絕對能贏的方法 :

1. 每步可以選擇走三階（EX 0 -> 3）或走一階（EX 0 -> 1 ）

2. 必須到每個休息站休息及吃一個 Kinder 以維持體力。

現在無聊的 CTF 想知道 SF 完成比賽的方法數，請你寫個程式幫助 CTF 算出答案。

輸入

第一行共兩個數字 n 跟 m ，分別代表 101 大樓的階梯總數及休息站的數量。

(1 <= n <= 100000 , 0 <= m < n)

接下來一行共 m 個數字 a [ i ] ( 1 <= a [ i ] < n ) ，代表每個休息站所在的階梯，且 a [ i ] < a [ i + 1]。

5 1
3

輸出

輸出一個數，代表 SF 完成比賽的方法數。

答案可能很大，請 mod 1000000007 。

2

解題思路

c574 的進化版，不知道移動方法數怎麼算的可以參考那篇，這邊就是把原本的兩步改成三步。

這題的目標是到所有的休息站吃到所有的 Kinder，所以取起點到第一個休息站、第一個休息站到第二個、二到三…倒數第一個到終點的移動距離，查表找到對應的階梯移動方法，將它們數相乘即為答案。

#include <stdio.h>
#define MAX 100001
#define MOD 1000000007

int DP[MAX] = { 1, 1, 1 }, n, m, kinder, pKinder;
long long ans = 1;

int main()
{
    for (int i = 3; i < MAX; i++)
        DP[i] = (DP[i - 1] + DP[i - 3]) % MOD;
    scanf(" %d %d", &n, &m);
    for (int i = 0; i < m; i++)
    {
        scanf(" %d", &kinder);
        ans = (ans * DP[kinder - pKinder]) % MOD;
        pKinder = kinder;
    }
    printf("%lld\n", (ans * DP[n - pKinder]) % MOD);
    return 0;
}

內容

Boook 從國中開始喜歡上了養鴿子，如今已經有了豐富的經驗與技術，今年將代表台灣去日本東京參加『 國際鴿子大賽 IOI 』（ International Olympia In doves keeping ）。

比賽方式如下：

一開始參賽者必須將每隻鴿子隨機標記一個數字代表這隻鴿子的分數，比賽開始後由大會隨機決定一個數字 K ，而每位參賽者都要從他擁有的所有鴿子中選出一些鴿子使這些鴿子的分數總和為 K 的倍數，最快的獲勝。

Boook 想要用程式幫助他能快速的決定要選擇哪些編號的鴿子，才能完成比賽條件。

現在 Boook 給你他每隻鴿子的分值，現在請你寫個程式，告訴 Boook 有沒有可能符合比賽需求，如果可以，要選擇哪些鴿子使 Boook 順利完成比賽。

（本題答案可能有多組解，請輸出任意一組）

輸入

第一行共兩個數字 n 跟 k ，分別代表 Boook 的鴿子數量及比賽要求的數字。

(1 <= n <= 100000 , 2 <= k <= n)

接下來一行共 n 個數字 a [ i ] ( 1 <= a [ i ] <= 2147483647 ) ，代表每隻鴿子的分數。

5 3
7 92 47 5 1

輸出

(答案可能有很多，輸出任何一組即可)

第一行一個數字 m ，代表 Boook 共要選幾隻鴿子。

(如果無法贏得比賽，請輸出 0 )

接下來一行共 m 個數字代表要選的鴿子編號。

2
4 5

解題思路

由於只需輸入任一組，所以用 DFS 遍歷全部可能性，找到第一組時將其記錄下來並跳出遞迴輸出即可。

#include <stdio.h>
#define MAX 100010

int n, k, list[MAX], ans[MAX], aLen;

char dfs(int s, long long sum)
{
    if (!(sum % k) && sum)
        return 1;
    for (int i = s; i <= n; i++)
    {
        if (dfs(i + 1, sum + list[i]))
        {
            ans[aLen++] = i;
            return 1;
        }
    }
    return 0;
}

int main()
{
    while (scanf(" %d %d", &n, &k) == 2)
    {
        aLen = 0;
        for (int i = 1; i <= n; i++)
            scanf(" %d", &list[i]);
        if (dfs(1, 0))
        {
            printf("%d\n", aLen);
            for (int i = 0; i < aLen; i++)
                printf("%d ", ans[i]);
            putchar('\n');
        }
        else
        {
            puts("0");
        }
    }
    return 0;
}

內容

BERT 是個奇怪的人，爬樓梯都不乖乖乖的一次走一格，而是有時走一階，或一次走兩階。
換句話說，假設階梯有三階，那他有三種走法
一： 第一步走一階，第二步走二階。
二： 第一步走二階，第二步走一階。
三： 全程都走一階。

現在請你寫個程式，算出如果是 n 格樓梯，Bert 有幾種走法 ?

輸入

多筆輸入

每行一個數字 N ，代表現在有 N 階樓梯 。

(1 <= Ｎ <= 10000)

3
1

輸出

每行一個數字，代表當樓梯有 N 階時答案。

答案可能很大，請 mod 1000000007

3
1

解題思路

DP 題，看起來有三種可能，但實際上只需考慮走 1 步和走 2 步兩種情況。

而因為只能走兩步，所以如果你想要走到第 n 階，你只有從 n-1 階走一步和 n-2 階走兩步兩種情況需要考慮。也就是說走到第 n 階的可能性就是 n-1 階和 n-2 階的可能性相加。

所以整理出公式

if n <= 1 , s[n] = 1
if n >= 2 , s[n] = s[n-1] + s[n+2]

#include <stdio.h>
#define Mod 1000000007

int list[10001] = { 1, 1 };

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

內容

bert307 從全國賽後，得到了一種神奇的魔力～～

當他看到一個字串( String ) ，就會找尋其中的子序列 [ QAQ ]！

當找到一個 [ QAQ ]，Bert 就會 QQ 一次！

現在請寫個程式算一算 bert307 會 QQ 幾次～～

如果你不知道什麼是子序列，以下舉個範例：

子序列：字串當中由左到右挑取字元所構成的字串。

例如 algo 的子序列一共是： Ø（空集合）, a, l, g, o, al, ag, ao, lg, lo, go, alg, alo, ago, lgo, algo 。

輸入

單筆輸入~~

輸入只有一串字串 ( 長度 <= 100000 )

字串只包含大寫字母 " A " ~ " Z "

// Input 1
QAQAQYSYIOIKKK

// Input 2
QAQQQZZYNOAAA

輸出

寫一個程式算出 Bert 會 QQ 幾次～～

// Output 1
4

// Ouput 2
3

解題思路

由於子序列只包含 Q 和 A，所以其他字元皆不會有想結果，不用理會它們。

先舉幾個例子當參考

• QQQAQ = 3*1

• QQQAQQ = 3*2

• QQQAAQQ = 3*2 + 3*2

• QQQAQAQQ = 3*3 + 4*2

• QQQAQAQQAAQQQ = 3*6 + 4*5 + 6*3 + 6*3

發現要如果要計算 QAQ 子序列總量，就是當遇到 A 的時候把左邊的 Q 和右邊的 Q 相乘，然後把所有遇到 A 的情況相加即是答案。

但這樣子太難給程式計算了，所以在寫程式時要把邏輯反轉一下當變成"遇到 Q 的時候，會新產生多少個 QAQ 子序列"。

#include <stdio.h>

char input[100010];

int main()
{
    long long ans = 0;
    int sumQ = 0, leftQ = 0;
    gets(input);
    for (int i = 0; input[i]; i++)
    {
        if (input[i] == 'Q')
            sumQ++, ans += leftQ;
        else if (input[i] == 'A')
            leftQ += sumQ;
    }
    printf("%lld", ans);
    return 0;
}

內容

現在有 n 個數字，Bert 現在想要找兩個數字，i 跟 j ( i < j )

使 a[ i ] - a[ j ] 儘量大，請你寫個程式幫幫他~~

輸入

第一行有個數字 n (2 <= n <= 100000) 代表現在有 n 個數字~~

接下來一行 a[1] , a[2] …. , a[n]

(1 <= a[i] <= 100000)

2018.03.07 更新

5
5 4 3 2 1

輸出

請輸出一個數字 ans = max( a[ i ] - a[ j ] | i < j )

( i 必須小於 j )

4

解題思路

先整理出規則

1. 因為 i < j ，較大值無法跟在其右邊的較小值組合

2. 當出現一個比前面較大值(n)更大的值(m)後，m 後面所有較小值相對於 n，和 m 的差距一定更大。

所以目標就是遇到新的較大值後，將前面的最大差給記錄起來，然後將較大值設為新的較大值，如此反覆值到陣列結束。

#include <stdio.h>

int main()
{
    int n, max, min, tmp, best;
    while (scanf(" %d", &n) == 1)
    {
        scanf(" %d", &min);
        best = 0, max = min;
        while (--n)
        {
            scanf(" %d", &tmp);
            if (tmp < min)
                min = tmp;
            else if (tmp > max)
            {
                if (max - min > best)
                    best = max - min;
                max = min = tmp;
            }
        }
        printf("%d\n", best < max - min ? max - min : best);
    }
    return 0;
}

內容

記憶體限制『 5MBytes 』

本題記憶體限制 5 MB
請勿使用 #include
請使用 #include <stdio.h> 使用 scanf , printf 輸入輸出

輸入

單筆輸入~~

一開始有個數字 n (1 <= n <= 1048576)

接下來一行 a1 a2 a3 …… an 共　 n 　個數字

(1 <= a[i] <= 100)

5
2 3 4 1 5

輸出

請從小到大輸出所有數字～～

1 2 3 4 5

解題思路

數量大、範圍小，基礎基數排序題。

#include <stdio.h>

int n, tmp, list[101];

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

內容

Bert 有天騎著海豚到了埃及，看到了金字塔不經意的發出『 哇～～ 』

現在 Bert 想請你用程式記下金字塔的樣子～～

現在有一種 n 層的三金字塔，定義如下:

第 i 層要有相對數量的 " * "，請注意要像金字塔一樣向中間對齊

請你寫個程式幫幫 Bert ~~

輸入

單筆輸入~~

輸入只有一個整數 n (1 <= n <= 100)

n 保證為奇數

3

輸出

輸出整個三角形~~

因為空格不好辨識，請以"_" 代替 ~~

__*__
_***_
*****

解題思路

c419 的強化版，一樣先用底線初始化陣列，然後從中心開始每次都向左和右一字元將他們改成'*'後輸出即可。

本題雖說保證為奇數，但實際上不論奇偶都能形成完整的三角形。

#include <stdio.h>

char s[200];

int main()
{
    int n;
    scanf(" %d", &n);
    for (int i = n * 2 - 2; i >= 0; i--)
        s[i] = '_';
    n--;
    for (int i = 0; i <= n; i++)
    {
        s[n - i] = s[n + i] = '*';
        puts(s);
    }
    return 0;
}

內容

Bert 又想要另外一種 n 層的三角形，定義如下:

第 i 層一樣要有 i 個 " * "，但要向右對齊

請你寫個程式幫幫 Bert ~~

輸入

單筆輸入~~

輸入只有一個整數 n (1 <= n <= 100)

3

輸出

輸出整個三角形~~

因為空格不好辨識，請以"_" 代替 ~~

__*
_**
***

解題思路

c418 的類題，只是這題先用底線初始化陣列，'*' 從後面加回來而已。

#include <stdio.h>

char s[101];

int main()
{
    int n;
    scanf(" %d", &n);
    for (int i = 0; i < n; i++)
        s[i] = '_';
    for (int i = n - 1; i >= 0; i--)
    {
        s[i] = '*';
        puts(s);
    }
    return 0;
}

內容

Bert 想要一個 n 層的三角形，第 i 層就要有 i 個 " * "

請你寫個程式幫幫可憐的 Bert ~~

輸入

單筆輸入~~

輸入只有一個整數 n (1 <= n <= 100)

3

輸出

輸出整個三角形~~

*
**
***

解題思路

第一次將 s[0]變成 '*'、輸出("*")
第二次將 s[1]變成 '*'、輸出("**")
第三次將 s[2]變成 '*'、輸出("***")
…

看 n 為幾就用迴圈跑幾次即可。

#include <stdio.h>

char s[101];

int main()
{
    int n;
    scanf(" %d", &n);
    for (int i = 0; i < n; i++)
    {
        s[i] = '*';
        puts(s);
    }
    return 0;
}

內容

文文剛學完了加減乘除四則運算，作業簿上有些練習題，他寫完了練習題可是不知道對不對。麻煩你提供正確解答讓他對一下答案，謝謝！

輸入

每筆測試資料有一行，含有兩個整數，兩個整數中間有一個運算符號 + (加)、- (減)、* (乘)、或 / (除)。整數與運算符號之間有一空白隔開。

12 + 3
101 - 11
13 * 7
111 / 3

輸出

請將每個算式的結果分別輸出於一行。答案均為整數。

15
90
91
37

解題思路

簡單的條件判斷。

#include <stdio.h>

int main()
{
    int a, b;
    char s;
    while (scanf(" %d %c %d", &a, &s, &b) == 3)
    {
        switch (s)
        {
        case '+':
            printf("%d\n", a + b);
            break;
        case '-':
            printf("%d\n", a - b);
            break;
        case '*':
            printf("%d\n", a * b);
            break;
        default:
            printf("%d\n", a / b);
            break;
        }
    }
    return 0;
}