Test Message

a271: 彩色蘿蔔

內容

在一個神奇的國度裡，有一種兔子，它只吃蘿蔔，且每天只吃一個，蘿蔔有四種顏色，分別為：紅蘿蔔，白蘿蔔，黃蘿蔔，發霉的蘿蔔（黑色），兔子吃了蘿蔔之後，體重會有不同的變化，紅蘿蔔吃了胖 xg，白蘿蔔吃了胖 yg，黃蘿蔔吃了瘦 zg(醃黃蘿蔔真難吃…)，發霉的蘿蔔吃了瘦 wg(附加狀態：中毒…)，現在給你 x,y,z,w 問你幾天後，兔子的體重！

p.s.中毒會使兔子每天瘦 ng(中毒當天不算),且中毒狀態可累加，m 是兔子初始的體重。早上先中毒，晚上才吃東西。

上面的敘述很重要，要仔細看！

輸入

第一行是測資的筆數，每筆測資第一行是 x,y,z,w,n,m，第二行是一串數字，1 代表紅蘿蔔，2 代表白蘿蔔，3 代表黃蘿蔔，4 代表黑蘿蔔，0 代表沒吃。這一行中的數字為兔子這段時間內所吃的食物。

4
5 3 2 4 3 10
1 1 2 3 3 3 3 4 3 3
5 3 2 4 3 10
1 1 2 3 3 3 3 4 3 3 2 2 2 2 2 2 2
5 3 2 4 3 10
4 1 3 3 1 1 2 2 1 1 3 1 1 1 1 4
10 3 2 2 1 5
1 4 4 0 0 4 1 2 2 2 0 0 2 2 0

輸出

請輸出兔子在那段時間後所剩的體重，如果體重有在任意時刻少於等於 0 請輸出：”bye~Rabbit”(不含引號)，不然請印出結束時的體重。（詳情參照範例輸入輸出）

有可能問你第一天的體重歐！(就是問初始體重，也就是那行根本沒輸入)
例如如：
13 312 43 432 567
//空一行

輸出為：567

1g
bye~Rabbit
bye~Rabbit
bye~Rabbit

解題思路

完整程式碼

簡單的流程控制和字串處理。

AC (51ms, 108KB)
#include <stdio.h>

int kase, x, y, z, w, n, m, nt, r;
char buffer[1000], * curr;

inline char* sgetInt(char* src, int* dst)
{
    *dst = 0;
    int i = 0, getNum = 0;
    for (; src[i]; i++)
    {
        if (src[i] >= '0' && src[i] <= '9')
            * dst = (*dst << 3) + (*dst << 1) + (src[i] - '0'), getNum = 1;
        else if (getNum)
            return src + i + 1;
    }
    return getNum ? src + i : NULL;
}

int main()
{
    scanf("%d", &kase);
    getchar();
    while (kase--)
    {
        gets(buffer), curr = buffer;
        curr = sgetInt(curr, &x), curr = sgetInt(curr, &y), curr = sgetInt(curr, &z);
        curr = sgetInt(curr, &w), curr = sgetInt(curr, &n), curr = sgetInt(curr, &m);
        gets(buffer), curr = buffer, nt = 0;
        while ((curr = sgetInt(curr, &r)) != NULL)
        {
            if ((m -= nt) <= 0)
                break;
            switch (r)
            {
            case 1:
                m += x;
                break;
            case 2:
                m += y;
                break;
            case 3:
                m -= z;
                break;
            case 4:
                m -= w, nt += n;
                break;
            default:
                break;
            }
        }
        m > 0 ? printf("%dg\n", m) : puts("bye~Rabbit");
    }
    return 0;
}
閱讀更多

a268: 河內塔問題

內容

相信大家都知道著名的河內塔問題。簡單來說，就是有三根柱子，柱子上可以套多個圓盤，圓盤大小都不同，但是每次移動一個圓盤的時候都不能有較大的圓盤在較小的圓盤上。一般來說一開始的初始狀態是所有圓盤都在同一根柱子上，目標是在不違反規則的條件下，至少移動幾次圓盤可使所有圓盤移動到另外一根柱子上。

我們的問題比較複雜一點，給定圓盤的初始狀態以及目標狀態，問至少要移動幾次能從初始狀態到目標狀態。

輸入

每個測資檔包含多筆測資。每筆測資包含三行，第一行是一個正整數 N (1<=N<=10000)，代表圓盤的個數。第二行及第三行分別代表圓盤的初始與目標狀態。每行有 N 個正整數，第 i 個數 Si 代表第 i 小的圓盤是套在 Si 上，其中 Si 只可能是 1 或 2 或 3。當 N=0 時代表輸入結束。

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
31
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
0

輸出

對每筆測資輸出一行，代表從初始狀態到目標狀態至少要移動幾次圓盤。由於答案可能很大，請輸出 mod 1,000,000,007 的結果。

6
7
3
0
147483633

解題思路

b592 的進化版，一樣的解題邏輯就不再寫一遍了。

這題雖然測資比較變態，但只要演算法沒錯、該建的表有建、不要做多餘的操作，時間壓力並不大。

完整程式碼

AC (21ms, 148KB)
#include <stdio.h>
#define MAX 10001
#define MOD 1000000007

int steps, step[MAX] = { 1 }, n, base;
char now[MAX], to[MAX], end[MAX], curr;

int main()
{
    for (int i = 1; i < MAX; i++)
        step[i] = (step[i - 1] << 1) % MOD;
    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 = (steps + step[base]) % MOD, 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 = (steps + step[i - 1]) % MOD;
            }
            printf("%d\n", steps);
        }
        else
        {
            puts("0");
        }
    }
    return 0;
}
閱讀更多

a263: 日期差幾天

內容

給你兩個日期，問這兩個日期相差幾天。

輸入

輸入有多筆測資，每筆測資有兩行，每行有三個整數依序是年、月、日。輸入以 EOF 作為結束，題目保證不會有不符合的測資出現。

2011 10 19
2011 10 18

輸出

輸出兩個日期差幾天。

1

解題思路

把日期轉換成自西元 0 年 0 月 0 日至該日的總天數再相減即可，要注意閏年在處理時有分兩部分 :

  1. 到去年為止共經過幾個閏年
  2. 今年有閏年嗎 ? 是否經過

完整程式碼

AC (5ms, 100KB)
#include <stdio.h>
#define ABS(x) (x) < 0 ? -(x) : (x)

typedef struct node
{
    int Year, Month, Day;
}Date;

Date f, t;

int month[] = { 0 , 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334 };
int fDays, tDays , gap;

inline int Days(Date src)
{
    return src.Year * 365 + (src.Year - 1) / 4 - (src.Year - 1) / 100 + (src.Year - 1) / 400 + month[src.Month - 1] + src.Day
        + ((!(src.Year % 4) && (src.Year % 100) || !(src.Year % 400)) && src.Month > 2);
}

int main()
{
    while (scanf(" %d %d %d %d %d %d", &f.Year, &f.Month, &f.Day, &t.Year, &t.Month, &t.Day) == 6)
    {
        gap = Days(f) - Days(t);
        printf("%d\n", ABS(gap));
    }
    return 0;
}
閱讀更多

a248: 新手訓練 ~ 陣列應用

內容

大家都知道，小算盤的小數運算只能算出小數點後三十幾位

但好奇的桑葉想知道更精準的小數值

請你幫可憐的桑葉做出可以算出精準的小數運算的程式

輸入

每次輸入有三個正整數 a , b , N

1<= a , b <= 2147483647 1 <= N <= 10000

( 輸入不會超過 1000 筆 )

18467 41 10
26500 6334 10
15724 19169 10
10 5 3

輸出

請輸出 a / b 的小數運算結果

精準到小數點後 N 位

第 N 位以後請無條件捨去

450.4146341463
4.1837701294
0.8202827481
2.000

解題思路

除法每當要算下一位小數時會把餘數 * 10 當成被除數繼續給除數除。
所以能得到以下公式 :

這次的被除數 = (上次的餘數 % 除數) * 10

程式部分先把小數點以上的輸出，以下的就用剛才得到的公式配合迴圈去求即可。

完整程式碼

AC (49ms, 100KB)
#include<stdio.h>

int a, b, n;
char output[10010], * oTop;

int main()
{
    while (scanf(" %d %d %d", &a, &b, &n) == 3)
    {
        oTop = output;
        printf("%d.", a / b);
        while (n--)
        {
            a %= b;
            a = (a << 3) + (a << 1);
            *oTop++ = (a / b) + '0';
        }
        *oTop = '\0';
        puts(output);
    }
    return 0;
}
閱讀更多

a244: 新手訓練 ~ for + if

內容

內容就是~

希望學到 for 迴圈和剛開始 coding 的學弟好好加油!!!!

輸入

第一行有一個正整數 N，

代表接下來有 N 行每行有三個正整數 a , b , c

( 1 <= b , c <= 2147483647 )

( 1 <= a <= 4 )

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

輸出

如果 a = 1 請輸出 b+c

如果 a = 2 請輸出 b-c

如果 a = 3 請輸出 b*c

如果 a = 4 請輸出 b/c

結果請用整數輸出

5
-1
6
0

解題思路

簡單的三元運算子判斷。

完整程式碼

AC (6ms, 80KB)
#include <stdio.h>

int n, a;
long long b, c;

int main()
{
    while (scanf(" %d", &n) == 1)
    {
        while (n--)
        {
            scanf(" %d %lld %lld", &a, &b, &c);
            printf("%lld\n", a == 1 ? b + c : a == 2 ? b - c : a == 3 ? b * c : b / c);
        }
    }
    return 0;
}
閱讀更多

a229: 括號匹配問題

內容

最近要開學了! ( ~ 跟題目沒有什麼關係 ) ><

請寫一個程式把所有合法括號匹配方式列出來!

Ex. (())  ,  ((()())) , ()((()))  是合法的匹配方式

    )( , (()))(  , ()(()(  是不合法的匹配方式

    合法匹配的括號 ， 從答案列的開頭到答案列某一點，左括弧次數永遠大於等於右括弧!


    Ex. 合法匹配   ((()()))

    字串 (        左括弧 : 1  >=   右括弧 : 0
    字串 ((        左括弧 : 2  >=   右括弧 : 0
    字串 (((        左括弧 : 3  >=   右括弧 : 0
    字串 ((()        左括弧 : 3  >=   右括弧 : 1
    字串 ((()(        左括弧 : 4  >=   右括弧 : 1
    字串 ((()()        左括弧 : 4  >=   右括弧 : 2
    字串 ((()())        左括弧 : 4  >=   右括弧 : 3
    字串 ((()()))        左括弧 : 4  >=   右括弧 : 4



    Ex. 不合法匹配    (()))(

    字串 (        左括弧 : 1  >=   右括弧 : 0
    字串 ((        左括弧 : 2  >=   右括弧 : 0
    字串 (()        左括弧 : 2  >=   右括弧 : 1
    字串 (())        左括弧 : 2  >=   右括弧 : 2
    字串 (()))        左括弧 : 2  <=   右括弧 : 3
        !!! 右括弧次數大於左括弧了!  (()))( 為不合法匹配

輸入

輸入一個正整數 N ， 1 =< N <= 13 。

N 代表有幾組括號要匹配

Ex.
    N = 1 代表 一組括號 ()

    N = 2 代表有兩組括號  ()()

1
2
3
4

輸出

輸出 N 組括號的所有合法匹配組合

輸出方式請見範例

()

(())
()()

((()))
(()())
(())()
()(())
()()()

(((())))
((()()))
((())())
((()))()
(()(()))
(()()())
(()())()
(())(())
(())()()
()((()))
()(()())
()(())()
()()(())
()()()()

解題思路

標準的遞迴題目，先用 dfs 列舉出所有可能，然後略過不符合的解

而會產生不符合的解有兩種情況

  1. 放入輸出字串的左括弧數 > 目標括弧組數 (這樣如果要產生正確解一定會多一組)

  2. 放入輸出字串的右括弧數 > 放入輸出字串的左括弧數 (當前字串不正確，且後面不管放再多左括弧都不能修正這個問題)

所以當產生以上兩種情況時，就可以直接 return 掉剪枝，又因為所有可能產生不符合的解的情況都被剪枝剪掉了，所以每次輸出必為正確解，就不用再做額外的判斷。

完整程式碼

AC (95ms, 64KB)
#include <stdio.h>

int n, max;
char paren[30];

void dfs(int open, int close, int now)
{
    if (open > n || open < close)
        return;
    if (now == max)
    {
        puts(paren);
        return;
    }
    paren[now] = '(', dfs(open + 1, close, now + 1);
    paren[now] = ')', dfs(open, close + 1, now + 1);
}

int main()
{
    while (scanf(" %d", &n) == 1)
    {
        max = n << 1;
        dfs(0, 0, 0);
        putchar('\n');
    }
    return 0;
}
閱讀更多

a225: 明明愛排列

內容

可惜，沒有下一題叫做「列排愛明明」，明明系列即將在這裡告一段落，謝謝大家這幾天來的支持！

明明喜歡把數字排成一列－－用他自己的方式！
他首先先看個位數，把個位數由小到大排。接著，如果個位數字一樣的話，他會將這些數字，由大至小排。
例如，如果數字有 38 106 98 26 13 46 51 的話，那麼 51 會排最前面，因為個位數字 1 是其中最小的一個。
而 106 26 46 這三個數字，個位數同樣都是 6，所以明明會直接將他們由大至小排，也就是 106 46 26。
所以，排好之後是：51 13 106 46 26 98 38，請你幫他輸出最終結果吧！

輸入

有多組測試資料，以 EOF 結束。
每組測試資料以一個 n(<=1000) 開始，表示明明拿到了幾個數字。接著有 n 個以空白隔開的整數。

7
38 106 98 26 13 46 51
6
1 2 3 4 5 0
5
98 76 12 34 55
6
33 33 88 88 83 38

輸出

請輸出排序後的結果，以空白隔開。

51 13 106 46 26 98 38
0 1 2 3 4 5
12 34 55 76 98
83 33 33 88 88 38

解題思路

兩整數比較時，先 % 10 取個位數判斷，一樣的話則判斷整數大小。

完整程式碼

AC (4ms, 92KB)
#include <stdio.h>
#include <stdlib.h>

int n, list[1010];

int cmp(const void* lhs, const void* rhs)
{
    int res = *(int*)lhs % 10 - *(int*)rhs % 10;
    return res ? res : *(int*)rhs - *(int*)lhs;
}

int main()
{
    while (scanf(" %d", &n) == 1)
    {
        for (int i = 0; i < n; i++)
            scanf(" %d", &list[i]);
        qsort(list, n, sizeof(int), cmp);
        for (int i = 0; i < n; i++)
            printf("%d ", list[i]);
        putchar('\n');
    }
    return 0;
}
閱讀更多

a224: 明明愛明明

內容

一看題名，你就該知道，這次跟迴文脫不了關係！
若你不確定什麼是「迴文」，請看 Google 字典的解釋：

迴文 huíwén

一種修辭方式。
通過詞語反覆迴環使用，表達二者互相依存或彼此制約的關係，
如“人人為我，我為人人”、“饒人不痴漢，痴漢不饒人”。

輸入

一筆測試資料一行，包含許許多多但總數不超過 1000 個的大小寫英文字母和標點符號。
不可思議的是，裡面不會有任何空白字元。

ababa
bbaaa
Level
aaabbbcc
abcdefg
HowAreYouToday
A_man,_a_plan,_a_canal:_Panama.

輸出

如果重新安排順序後，有辦法讓這一堆英文字母變成迴文的話，輸出「yes !」，否則輸出「no…」。
注意，大寫和小寫字母視為相同，即 A 和 a 是一樣的，並且，請忽視所有非英文字母的字元。

yes !
yes !
yes !
no…
no…
no…
yes !

解題思路

先把輸入的字串轉成全大寫，之後遍歷整個字串並記錄所有英文的出現次數，如果出現次數為奇數次的英文超過 1 個，代表不能產生迴文，反之則可以。

完整程式碼

AC (1ms, 60KB)
#include <stdio.h>

char input[1100];

void strupr(char *src)
{
    src--;
    while (*++src)
    {
        if (*src >= 'a' && *src <= 'z')
            *src -= 32;
    }
}

int main()
{
    while (scanf(" %s", input) == 1)
    {
        char count[256] = { 0 }, isPal = 2;
        strupr(input);
        for (int i = 0; input[i]; i++)
            count[input[i]]++;
        for (int i = 'A'; i <= 'Z'; i++)
        {
            if (count[i] & 1)
            {
                isPal--;
                if (isPal == 0)
                    break;
            }
        }
        puts(isPal ? "yes !" : "no...");
    }
    return 0;
}
閱讀更多

a216: 數數愛明明

內容

數數是班上聰明又漂亮的女生，有一天……，她愛上了明明。
她對明明說：「我們的愛，若是錯誤，願你我沒有白白受苦。呃，不是，我們的愛就像是函數！」
明明說，「是啊，我對妳的愛是與日俱增呢！」
數數開心地說，「你的意思是，你在第 n 天對我的愛若用函數 f(n) 來描述，那麼，f(n) = n + f(n-1)。也就是說，每一天都比前一天多了一單位的愛，並且與舊的愛累積起來嗎？」
明明點了點頭，然後問，「那麼，妳呢？」
數數說，「我在第 n 天對你的愛若是 g(n)，則會滿足 g(n) = f(n) + g(n-1) 關係！」
於是，明明笑了笑，摟著數數說，我一定會更加愛妳的！
註：在第一天的時候，f(1) = g(1) = 1。

輸入

輸入以 EOF 結束。每一筆測試資料有一個數字 n，其中 n > 0。
此外，50% 的測資 n <= 500；80% 的測資，n <= 3000；全部的測資 n <= 30000。

1
2
3
5
8
13

輸出

輸出 f(n) 與 g(n)。

1 1
3 4
6 10
15 35
36 120
91 455

解題思路

根據題意建好 f(n)和 g(n)的表，之後查表輸出，注意 g(n)會超過 int 上限，要改用 long long。

完整程式碼

AC (2ms, 452KB)
#include<stdio.h>
#define MAX 30001

int n;
int  f[MAX];
long long g[MAX];

int main()
{
    for (int i = 1; i < MAX; i++)
    {
        f[i] = i + f[i - 1];
        g[i] = f[i] + g[i - 1];
    }
    while (scanf(" %d", &n) == 1)
    {
        printf("%d %lld\n", f[n], g[n]);
    }
    return 0;
}
閱讀更多

a215: 明明愛數數

內容

明明是一個愛數（ㄕㄨ ˇ）數（ㄕㄨ ˋ）的好學生，這天媽媽叫他從 n 開始數，下一個數字是 n+1，再下一個數字是 n+2，以此類推。媽媽想知道，明明數了幾個數字之後，他數過的這些數字的總和會超過 m。請幫助明明的媽媽吧。

輸入

輸入以 EOF 結束。每一筆測試資料有兩個數字，分別為 n 和 m，其中 m-n 不會超過 10^5。

1 5
5 10
100 1000

輸出

輸出如題目敘述。

3
2
10

解題思路

簡單迴圈判斷，注意 n > m 和 負數的情況。

完整程式碼

AC (2ms, 88KB)
#include<stdio.h>

int n, m, sum, count;

int main()
{
    while (scanf(" %d %d", &n, &m) == 2)
    {
        sum = n , count = 1;
        while (sum <= m)
            sum += n + count++;
        printf("%d\n", count);
    }
    return 0;
}
閱讀更多
1…2122232425…27