Test Message

d460: 山六九之旅

內容

小華每年都會到「山六九」主題樂園去玩，但是隨著年齡的增加，每年要買的門票也不太一樣。給你小華的年齡，請你告訴我他今年的門票多少錢？

「山六九」主題樂園的票價表如下：

0 ~ 5 歲兒童免票

兒童票 (6 ~ 11 歲)：590 元

青少年票 (12 ~ 17 歲)：790 元

成人票 (18 ~ 59 歲)：890 元

敬老票 (60 歲以上)：399 元

輸入

輸入只有一行，內含一個整數 a (0≤a≤2147483647) 代表小華的年齡。

15

輸出

依「山六九」的票價表，輸出一個整數，代表小華今年的門票價格。

790

提示

你可以只用算術及關係運算子，而不用 if、switch、或 ? : 來寫出這題嗎？ (這是「挑戰」而不是「限制」，因為出題者不是系統管理員，不能限制你用這些指令。)

解題思路

利用關係運算子成立時為 1 ，不成立時為 0 的特性用乘法判斷。

完整程式碼

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

int main()
{
    int n;
    scanf("%d", &n);
    printf("%d", (n >= 6 && n < 12) * 590 + (n >= 12 && n < 18) * 790
        + (n >= 18 && n < 60) * 890 + (n >= 60) * 399);
    return 0;
}
閱讀更多

d392: 讀取練習——強大的加法！

內容

說是強大的加法，其實也並沒有那麼可怕。

你的工作很容易，就是把一行輸入的數字加起來就可以啦！

輸入

每行都有一大堆數字，但都很 kind，不會刁難你的，用 longint 就可以了，而且都不是負數。

1 2
2 5  8 8 8              5

輸出

輸出這一行中出現的所有的數字的和並換行。

3
36

解題思路

簡單的字串處理。

完整程式碼

AC (3ms, 68KB)
#include <stdio.h>

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;
}

char input[10000];

int main()
{
    int sum, tmp;
    char* st;
    while (gets(input))
    {
        sum = 0 , st = input;
        while (st = getUInt(&tmp , st))
            sum += tmp;
        printf("%d\n", sum);
    }
    return 0;
}
閱讀更多

d326: 程式設計師的面試問題(二)

內容

位元運算常會有 machine dependant 的問題,
直接定義 1 byte = 8 bits, int 型態為 32 bits.

某甲碰到一個面試問題:

==============================================
輸入三個有號數 v, a, b,型態都是 int.
v 是介於-2147483647 到 2147483647 的整數值.
a 是代表這個整數的第 a 個 bit.
b 如果是 1,表示要將 v 的第 a bit 設成 1.
b 如果是 0,表示要將 v 的第 a bit 設成 0.

這個題目大意就是將 v 的第 a bit 設成 0 或 1.

請將程式運算的結果轉成二進位並輸出到螢幕上.

==============================================

某甲很快的 build 出大略的雛形如下:

#include <stdio.h>

/* set bit b to 1 */
int set_bit(int v, int b)
{

}

/* set bit b to 0 */
int unset_bit(int v, int b)
{

}

/* check_bit b is 1 or 0 */
int check_bit(int v, int a, int b)
{

}

int main(void)
{
    int i, v, bit, isSet;

    while(scanf("%d %d %d",&v,&bit,&isSet)==3)
    {
        if(isSet)
            v = set_bit(v, bit);
        else
            v = unset_bit(v, bit);

        for(i=31;i>=0;--i)
            printf( "%d", check_bit(v, 32, i) );
        putchar('\n');
    }


    return 0;
}

但是他還沒有把 function 完成.
現在請你完成這個程式,請嚴格要求自己每個 function 只用一行完成.
也就是每個 function 只有 return 運算;

當然,如果你有更快的做法也可以,只要通過 judge 的測資就可以了.

輸入

每行輸入三個有號整數,v, a, b, 用一個空白字元隔開.
v 的範圍為-2147483647 到 2147483647.
a 的範圍為 0 到 31.
b 不是 0 就是 1.
全部測資以 EOF 做為結束.

0 0 1
1 0 0
2147483647 31 1
-1 31 0
4 0 1
4 0 0

輸出

請對每一行測資輸出一行答案轉二進位數,也就是說會有 32 個整數,其整數不是 0 就是 1.
最左邊為最高位元, 最右邊為最低位元.
請參考範例測資和答案.

00000000000000000000000000000001
00000000000000000000000000000000
11111111111111111111111111111111
01111111111111111111111111111111
00000000000000000000000000000101
00000000000000000000000000000100

解題思路

位元運算題，

將 a 位元設成 b，而 b 有兩種情況

  1. b = 1，先將要改變的位元設成 1，然後和 b 做 OR

    v | (1 << a)

  2. b = 0，先將要改變的位元設成 1，將該數用位元 NOT('~')使目標位元變成 0，其他位源都變為 1 後再和 b 做 AND

    v & ~(1 << a)

改變好後用將第 32~1 位元依次右移到第 1 位元，再和 1 做 AND 使除了第 1 位元其他位源都變成 0，最後輸出答案即可。

完整程式碼

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

int main()
{
    int v, a, b;
    while (scanf(" %d %d %d", &v, &a, &b) == 3)
    {
        v = b ? (v | (1 << a)) : (v & ~(1 << a));
        for (int i = 31; ~i; i--)
            putchar(((v >> i) & 1) + '0');
        putchar('\n');
    }
    return 0;
}
閱讀更多

d299: 程式設計師的面試問題

內容

程式設計師的面試到底有多困難？

請推理出以下 10 個字母所代表的數字( 0 ~ 9 )。

重複的字母為相同的阿拉伯數字。

  FORTY

  　TEN

+)  TEN
_______

  SIXTY

請以 XXXXX + XXX + XXX = XXXXX 的格式輸出所有可能(這些 X 就是數字)。

請複製上述格式再將 X 改為數字,避免因為空白的關係而造成 WA 。

輸入

本題沒有輸入

無

輸出

每組輸出為一行，格式為

XXXXX + XXX + XXX = XXXXX

(這些 X 就是數字)

(略)

解題思路

用 dfs 窮舉所有可能，出現答案之後不再進行判斷快速跳出遞迴。

完整程式碼

AC (55ms, 76KB)
#include <stdio.h>

int ans[10], isUse[10];

char dfs(int now, int step)
{
    int i, j;

    if (step == 10)
    {
        if (ans[1] * 10000 + ans[4] * 1000 + ans[5] * 100 + ans[7] * 10 + ans[9]
            + 2 * (ans[7] * 100 + ans[0] * 10 + ans[3])
            == ans[6] * 10000 + ans[2] * 1000 + ans[8] * 100 + ans[7] * 10 + ans[9])
        {
            printf("%d%d%d%d%d + %d%d%d + %d%d%d = %d%d%d%d%d\n",
                ans[1], ans[4], ans[5], ans[7], ans[9],
                ans[7], ans[0], ans[3],
                ans[7], ans[0], ans[3], ans[6], ans[2], ans[8], ans[7], ans[9]);
            return 1;
        }
        return 0;
    }
    for (i = 0; i < 10; i++)
    {
        if (isUse[i]) continue;
        ans[step] = i;
        isUse[i] = 1;
        if (dfs(i, step + 1))
            return 1;
        isUse[i] = 0;
    }
    return 0;
}

int main()
{
    dfs(0, 0);
    return 0;
}
閱讀更多

d277: 矩形對角線

內容

同學們要在廣場上佈置一個矩形花壇，計畫用“串紅”擺成對角線。如果一條對角線用了 N 盆，還需要多少盆“串紅”呢？

輸入

每行一個 N(0<n<2^31).

38

輸出

輸出還需多少盆。

38

解題思路

題意為當有一矩形花壇從左上到右下對角線擺放了 n 個花盆，那求從右上到左下對角線還要再擺幾盆花盆才能形成一個叉。

Ex: n = 3

x o o
o x o
o o x

這時候就還需要右上和左下兩個才能變成

x o x
o x o
x o x

本題重點在中心交叉處是否重疊，若 n 為偶數項不會重疊、奇數項最中間那個重疊。
所以判斷輸入為偶數或奇數，偶數直接輸出、奇數減一後輸出即可。

完整程式碼

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

int main()
{
    int n;
    while (scanf(" %d", &n) == 1)
    {
        printf("%d\n", n & 1 ? n - 1 : n);
    }
    return 0;
}
閱讀更多

d244: 一堆石頭

內容

可愛的潘潘有著一堆石頭，每顆石頭上面都有一個正整數編號。接著，她又利用複製機器把每顆石頭都複製了兩個，而編號當然跟原來那個一樣。

可是有一天，她不小心掉了一顆石頭，現在她想要找出她掉的那一顆石頭的編號。

輸入

只有一筆測資給你她現在所擁有的石頭的編號，用空格分開。

當然，個數一定是三的倍數減一個。

9 8 6 9 8 2 3 5 2 1 6 8 1 5 1 2 3 3 5 9

輸出

輸出她掉的那一顆石頭的編號。

6

解題思路

讀入資料後查表判斷是有有儲存過，然後會出現以下任一種情況

  1. 沒儲存過 → 將資料存到末項之後一個元素，次數設為 1 ，陣列長度 + 1
  2. 有儲存過，次數為 1 → 將次數 + 1
  3. 有儲存過，次數為 2 → 將元素和末項交換，將陣列長度 - 1 代表該筆資料作廢

按照上表對應處理所有元素，由於只會有一組只有兩個，剩下的都會有 3 個，而 3 個石頭又會觸發狀態 3，所以最後不管兩個石頭的那組原本在哪都會被換到首項，因此輸出時不用再遍歷一次，直接輸出即可。

下面另外提供一個雜湊表版本的，雜湊版本在能克服測資更大更極端的情況，不過由於本題測資不強所以耗時反而比陣列版更久就是了。

完整程式碼

陣列版

AC (6ms, 1.1MB)
#include <stdio.h>
#define BUFSIZE 1048576

int stone[BUFSIZE], cont[BUFSIZE];

inline char readChar()
{
    static char buffer[BUFSIZE], * now = buffer + BUFSIZE, * end = buffer + BUFSIZE;
    if (now == end)
    {
        if (end < buffer + BUFSIZE)
            return EOF;
        end = (buffer + fread(buffer, 1, BUFSIZE, stdin));
        now = buffer;
    }
    return *now++;
}

inline char readUInt(unsigned int* dst)
{
    register char ch;
    while ((ch = readChar()) < '0')
        if (ch == EOF) return 0;
    *dst = ch ^ '0';
    while ((ch = readChar()) >= '0')
        * dst = (*dst << 3) + (*dst << 1) + (ch ^ '0');
    return 1;
}

int main()
{
    unsigned int tmp, len = 0;
    while (readUInt(&tmp))
    {
        for (int i = 0; i < len; i++)
        {
            if (stone[i] == tmp)
            {
                if (cont[i] == 2)
                    stone[i] = stone[--len], cont[i] = cont[len];
                else
                    cont[i]++;
                goto end;
            }
        }
        stone[len] = tmp, cont[len++] = 1;
    end:;
    }
    printf("%d", stone[0]);
    return 0;
}

雜湊表版

AC (9ms, 1.1MB)
#include <stdio.h>
#define BUKCNT 9887
#define BUKSIZ 1000000
#define BUFSIZE 1048576

typedef struct
{
    unsigned int Key, Value, Next;
} Node;

unsigned int buckets[BUKCNT], freeBuk, lastNode;
Node dict[BUKSIZ];

inline char readChar()
{
    static char buffer[BUFSIZE], * now = buffer + BUFSIZE, * end = buffer + BUFSIZE;
    if (now == end)
    {
        if (end < buffer + BUFSIZE)
            return EOF;
        end = (buffer + fread(buffer, 1, BUFSIZE, stdin));
        now = buffer;
    }
    return *now++;
}

inline char readUInt(unsigned int* dst)
{
    register char ch;
    while ((ch = readChar()) < '0')
        if (ch == EOF) return 0;
    *dst = ch ^ '0';
    while ((ch = readChar()) >= '0')
        * dst = (*dst << 3) + (*dst << 1) + (ch ^ '0');
    return 1;
}

void setNode(int Key)
{
    int targetBuk = Key % 9887, currNode = buckets[targetBuk];
    while (currNode)
    {
        if (dict[currNode].Key == Key)
        {
            if (dict[currNode].Value == 2)
            {
                int del = dict[currNode].Next;
                dict[currNode] = dict[del];
                //
                if (del)
                {
                    dict[del].Next = freeBuk;
                    freeBuk = del;
                }
                return;
            }
            dict[currNode].Value++;
            return;
        }
        currNode = dict[currNode].Next;
    }
    if (freeBuk)
        currNode = freeBuk, freeBuk = dict[freeBuk].Next;
    else
        currNode = ++lastNode;
    dict[currNode].Next = buckets[targetBuk];
    buckets[targetBuk] = currNode;
    dict[currNode].Key = Key;
    dict[currNode].Value = 1;
}

int getAns()
{
    int currNode;
    for (int i = 0; i < BUKCNT; i++)
    {
        currNode = buckets[i];
        while (currNode)
        {
            if (dict[currNode].Value == 2)
                return dict[currNode].Key;
            currNode = dict[currNode].Next;
        }
    }
}

int main()
{
    int tmp;
    while (readUInt(&tmp))
        setNode(tmp);
    printf("%d", getAns());
    return 0;
}
閱讀更多

d212: 東東爬階梯

內容

東東有個嗜好，爬階梯不是一次走一階，就是一次走兩階。

換句話說，假設階梯有三階，那他有三種走法

一：第一步走一階，第二步走二階。

二：第一步走二階，第二步走一階。

三：全程都走一階。

這題要問你，假設階梯有 n 階，那東東有幾種走法?

輸入

第一行有一個正整數 n，0<n<100，表示階梯有 n 階。

1
2
5

輸出

請輸出 n 個階梯有幾種走法。

1
2
8

解題思路

和 c547 同一題，本題沒有使用 MOD 運算，因此最後幾項即使使用 unsigned long long 存也會溢位，這邊可以用萬進制的想法開另一個陣列去存進位的值，輸出時判斷是否有進位到新陣列來選擇不同的格式輸出即可。

完整程式碼

AC (1ms, 60KB)
#include <stdio.h>
#define SIZE 100
#define MAX 10000000000000000000ULL

unsigned long long list[SIZE] = { 1, 1 };
int list2[SIZE];

int main()
{
    int n;
    for (int i = 2; i < SIZE; i++)
    {
        list[i] = list[i - 1] + list[i - 2];
        list2[i] = list2[i - 1] + list2[i - 2];
        if (list[i] >= MAX)
            list[i] -= MAX, list2[i]++;
    }
    while (scanf(" %d", &n) == 1)
    {
        if (list2[n]) printf("%d%012llu\n", list2[n], list[n]);
        else printf("%llu\n", list[n]);
    }
    return 0;
}
閱讀更多

d166: 反轉表

內容

由 1 開始之連續數字 a1.a2.a3…an 相對有一反轉表：b1.b2…bm。其 bm 代表意思為：數字 m 的位置前面有幾個比大個個數。

2 3 6 4 0 2 2 1 0
第 1 個 2 為 1 前面有 2 個比它大的數
第 2 個 3 為 2 前面有 3 個比它大的數
第 3 個 6 為 3 前面有 6 個比它大的數….以此類推
所以答案為
5 9 1 8 2 6 4 7 3
數字 1 前面有 2 個比它大的數 5 9
數字 2 前面有 3 個比它大的數 5 9 8

輸入

輸入的每一行含有一個由 m 個數所組成的數列(反轉表) 1<=m<=50，

單獨一個 -1 在一行代表測試資料的結束

2 3 6 4 0 2 2 1 0

-1

輸出

請輸出從 1 到 m 所代表的數列

5 9 1 8 2 6 4 7 3

解題思路

從小到大將項目數新增至陣列，並在前面保留輸入值個元素讓後面更大的元素可以放進去。

以測資為範例

  1. [輸入] 2 3 6 4 0 2 2 1 0
    [答案] 0 0 1 0 0 0 0 0 0

  2. [輸入] 2 3 6 4 0 2 2 1 0
    [答案] 0 0 1 0 2 0 0 0 0

  3. [輸入] 2 3 6 4 0 2 2 1 0
    [答案] 0 0 1 0 2 0 0 0 3

  4. [輸入] 2 3 6 4 0 2 2 1 0
    [答案] 0 0 1 0 2 0 4 0 3

  5. [輸入] 2 3 6 4 0 2 2 1 0
    [答案] 5 0 1 0 2 0 4 0 3

  6. [輸入] 2 3 6 4 0 2 2 1 0
    [答案] 5 0 1 0 2 6 4 0 3

  7. [輸入] 2 3 6 4 0 2 2 1 0
    [答案] 5 0 1 0 2 6 4 7 3

  8. [輸入] 2 3 6 4 0 2 2 1 0
    [答案] 5 0 1 8 2 6 4 7 3

  9. [輸入] 2 3 6 4 0 2 2 1 0
    [答案] 5 9 1 8 2 6 4 7 3

完整程式碼

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

char input[10000];

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()
{
    while (gets(input) && input[0] != '-')
    {
        char* st = input;
        int ans[MAX] = { 0 }, tmp, j;
        for (int i = 0; st = getUInt(&tmp, st); i++)
        {
            for (j = 0; tmp || ans[j]; j++)
                if (!ans[j]) tmp--;
            ans[j] = i + 1;
        }
        for (int i = 0; ans[i]; i++)
            printf("%d ", ans[i]);
        putchar('\n');
    }
    return 0;
}
閱讀更多

d124: 3的倍數

內容

20XX 年，pascal 語言有多了一種新的整型 int128。它能夠運算 10000 位的超大數據。

今天我們的任務就是：輸入一個類型為　 int128 　的數字　ｎ　（-10^10001<=n<=10^10001）。

判斷它是否為 3 的倍數。

輸入

輸入檔中有多個數據，每組數據佔一行，是輸入的數 n 。

3
-7
0

輸出

輸出 n 是否為 3 的倍數。

若是，輸出 yes ；若不是，輸出 no 。

yes
no
yes

解題思路

由於當一數的各位數字和為 3 的倍數時，該數即為 3 的倍數，所以將輸入的字元加總起來和 3 取餘即可。

完整程式碼

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

char input[10010];

int main()
{
    int sum;
    while (scanf(" %s", input) == 1)
    {
        sum = 0;
        for (int i = 0; input[i]; i++)
            sum += input[i] - '0';
        puts(sum % 3 ? "no" : "yes");
    }
    return 0;
}
閱讀更多

d122: Oh! My Zero!!

內容

階乘運算是很令人頭疼的，因此我們要想方設法地把它簡化。

輸入

輸入檔可能有大量的數據。
每一個輸入檔輸入一個不算很大的數 n （請用 longint）。

1
2
10

輸出

輸出 n！的末尾零的個數。

0
0
2

解題思路

數字尾端要出現 0 必須是 10 的倍數，而要產生 10 的倍數就必須要有 1 個 5 和 1 個偶數，偶數在階層出現頻率一定比 5 還高，所以簡化下來答案算該數在因式分解時 5 的次方項。

完整程式碼

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

int main()
{
    int n, ans;
    while (scanf(" %d", &n) == 1)
    {
        ans = 0;
        while (n /= 5)
            ans += n;
        printf("%d\n", ans);
    }
    return 0;
}
閱讀更多
1…89101112…27