d984: 棄保效應

2019-09-03

內容

台灣的選舉法令禁止各陣營及媒體在投票日前的一個星期內公佈民調結果，其中最重要的一個因素是要避免「棄保效應」。所謂的「棄保效應」是指選民在得知自己所支持的候選人當選無望時，有可能會把票投給其他比較可能當選的人，以免浪費了自己的一票。假設某選舉有三位候選人來競選一個職位，在「棄保效應」發揮到極致的情形下，所有民調第三名的候選人的支持者都會把票投民調第二名的候選人，也就是他們都會「棄三保二」。給你 A, B, C 三個候選人的支持者人數，請判斷誰會當選？

輸入

輸入有若干筆測試資料，每筆一行。每行有三個以空白隔開的整數 a, b, c 代表候選人 A, B, C 的支持者人數，0 ≤ a, b, c ≤ 2147483647。你可以假設在「棄保效應」之後，不會有相同票數的情形發生。

3 4 5
1 3 5

輸出

請輸出將會當選的人是 A, B 或 C。

B
C

解題思路

只有 3 個人，用巢狀 if 判斷即可，注意人數相加會超過 int 範圍要使用 unsigned 或 long long。

完整程式碼

AC (1ms, 88KB)

#include <stdio.h>

int main()
{
    long long a, b, c;
    while (scanf(" %lld %lld %lld", &a, &b, &c) == 3)
    {
        if (a > b && a > c)
        {
            if (a > b + c)puts("A");
            else if (b > c)puts("B");
            else puts("C");
        }
        else if (b > a && b > c)
        {
            if (b > a + c)puts("B");
            else if (a > c)puts("A");
            else puts("C");
        }
        else
        {
            if (c > a + b)puts("C");
            else if (a > b)puts("A");
            else puts("B");
        }
    }
    return 0;
}

d881: 作業苦多

2019-09-03

內容

學校作業何其多~~老二為此苦惱了許久，現在又有一份數學作業，他想節省時間，所以想找一個程式來解決此問題，你能幫嗎?詳細題目如下:
計算一級數
每項的差形成一個等差數列
每一題給定一等差數列的公差
此等數列有 50 項，第一項為 1
輸出此數列和(1+到 50 項)
例如輸入為 1(此為各項差形成的等差級數的公差)
答案要輸出 1+2+4+7+11+……(到 50 項)
若輸入為 2
答案要輸出 1+2+5+10+17+26+37…… (到五十項)

輸入

每次輸入一個測資 d，代表公差(d<=100)

1

輸出

輸出級數和(1+到 50 項)

20875

解題思路

用迴圈模擬題目算式算道第 50 項輸出即可。

完整程式碼

AC (1ms, 72KB)

#include <stdio.h>

int main()
{
    int n, now, ans, gap;
    while (scanf(" %d", &n) == 1)
    {
        now = gap = 1, ans = 0;
        for (int i = 0; i < 50; i++)
            ans += now, now += gap, gap += n;
        printf("%d\n", ans);
    }
    return 0;
}

d827: 買鉛筆

2019-09-03

內容

鉛筆一支 5 元，一打 50 元。小明需要幫班上每位同學買一枝鉛筆，請問要多少錢？由於小明很注重環保，他絕不會為了省錢而多買任何不需要的東西。也就是說，小明買的鉛筆數量一定等於班上的人數。

輸入

輸入只有一行，含有小明班上的人數 n，1 ≤ n ≤ 200。

42

輸出

請輸出一個數字，代表這次採購的金額。

180

解題思路

簡單的四則運算。

完整程式碼

AC (2ms, 108KB)

#include <stdio.h>

int main()
{
    int n;
    scanf(" %d", &n);
    printf("%d", (n / 12) * 50 + (n % 12) * 5);
    return 0;
}

d732: 二分搜尋法

2019-09-03

內容

給你一個嚴格遞增的數列 A1,A2,A3…..An(1<=n<=100000),

&下面有幾個問題的詢問數 k(1<=K<=100000),

以及 k 個詢問的整數 x,求數列中是否存在一個 Ai(1<=i<=n)的值與 X 相等?

輸入

第一行包含兩個整數 n,k 分別表示數列長度以及詢問數,

第二行包含 n 個整數第 i(1<=i<=n)個整數依序為數列中 Ai 的值,

第三行包含 k 個詢問的整數 x.

5 5
1 3 4 7 9
3 1 9 7 -2

輸出

對於每個詢問整數 x 對應一行輸出:

輸出 i 的值

其中 1<=i<=n 且 Ai=x

若沒有這樣的 i 值請輸出 0 代替.

2
1
5
4
0

解題思路

實作二分搜索法，輸入輸出很大做 IO 優化可以壓不少時間。

完整程式碼

AC (16ms, 1.5MB)

#include <stdio.h>
#include <stdlib.h>
#define BUFSIZ 1048576
#define MAX 100010

int list[MAX];

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

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

inline void putUInt(register unsigned int src, const char suffix)
{
    register unsigned int div;
    char buffer[12], * st = buffer + 10;
    *st = suffix, * (st + 1) = 0;
    do
    {
        *(--st) = src - ((div = src / 10) << 3) - (div << 1) + '0';
    } while (src = div);
    fputs(st, stdout);
}

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

int main()
{
    int n, m, key, * idx;
    scanf(" %d %d", &n, &m);
    for (int i = 0; i < n; i++)
        readInt(&list[i]);
    while (m--)
    {
        readInt(&key);
        if (idx = (int*)bsearch(&key, list, n, sizeof(int), cmp))
           putUInt(idx - list + 1, '\n');
        else
            puts("0");
    }
    return 0;
}

d710: parking lot

2019-09-03

內容

國防大學的停車場上，

停了許多各式各樣的車子，

有 Ford 的小轎車，

有 Toyota 的柴電混合車，

還有 BMW 的休旅車，

此外，

有藍色的車、紅色的車、白色的車 …

看完以上敘述，

你知道今天要寫什麼程式了嗎？

給一些車子的顏色和廠牌，

再依照指示列出有哪些車子符合要求。

輸入

第一部分有兩個數字 n, m ，( 0 < n, m ≤ 20 )

代表有 n 輛車子，

m 個指示。

第二部分有 n 行，

每行包含兩個字串：廠牌、顏色。( 以空白隔開，廠牌全部大寫，顏色全部小寫 )

第三部份有 m 行，

每行包含兩個字串，

分為兩種情況：brand XXXX 或 color xxxxx 。( 廠牌全部大寫，顏色全部小寫 )

每組測試資料間有一空行。

5 2
NISSAN red
BMW white
ROLLSROYCE black
TOYOTA white
TOYOTA blue
brand TOYOTA
color white

3 1
LEXUS pink
FORD green
PORSCHE gray
color pink

輸出

brand XXXXX 的意思是列出 XXXXX 廠牌的車子，

color xxxxx 的意思是列出 xxxxx 顏色的車子。

每行格式為 “廠牌顏色”

保證一定有資料輸出。

列出順序以讀入先後為主。

每組測試資料間請留一空行。

TOYOTA white
TOYOTA blue
BMW white
TOYOTA white

LEXUS pink

解題思路

資料量不大，將資料存入陣列後，輸出時用線性比對出相符的資料輸出即可。

完整程式碼

AC (2ms, 100KB)

#include <stdio.h>
#include <string.h>
#define MAX 25

typedef struct Node
{
    char brand[MAX], color[MAX];
}Car;

Car list[MAX];

int main()
{
    int n, m;
    char type[MAX], target[MAX];
    while (scanf(" %d %d", &n, &m) == 2)
    {
        for (int i = 0; i < n; i++)
            scanf(" %s %s", &list[i].brand, &list[i].color);
        while (m--)
        {
            scanf(" %s %s", type, target);
            if (type[0] == 'b')
            {
                for (int i = 0; i < n; i++)
                {
                    if (!strcmp(target, list[i].brand))
                        printf("%s %s\n", list[i].brand, list[i].color);
                }
            }
            else
            {
                for (int i = 0; i < n; i++)
                {
                    if (!strcmp(target, list[i].color))
                        printf("%s %s\n", list[i].brand, list[i].color);
                }
            }
            putchar('\n');
        }
    }
    return 0;
}

d693: 最小公倍數

2019-09-03

內容

這題並不是要你算兩個數的最小公倍數，

因為大家都知道：

( from wiki )

It is too easy!

想請大家算出 n 個數的最小公倍數！

輸入

每組測試資料兩行

第一行有一整數 N ( 2 ≤ N ≤ 10 )

第二行包含 N 個正整數 ( 每個數 ≤ 100 )

當 N 為 0 時請結束程式

2
3 5
0

輸出

每組測試資料輸出一行

請輸出 N 個正整數的最小公倍數

答案保證小於 2³¹-1

15

解題思路

最大公因數可以用輾轉相除法求得，最小公倍數則將兩數相乘去除以最大公因數即可。

lcm = (n * m) / gcd(n, m)

先求前兩數的 lcm，接下來重複和下一個讀取到的值求 lcm 直到結束後輸出 lcm 即可。

注意！題目雖然保證答案必在 int 範圍內但 n 和 m 相乘時式有機會超過的，所以要用 long long。

完整程式碼

AC (2ms, 108KB)

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

inline int lcm(long long m, int n)
{
    long long res = m * n;
    while (n)
    {
        m %= n;
        SWAP(m, n);
    }
    return res / m;
}

int main()
{
    int n, ans, tmp;
    while (scanf(" %d %d", &n, &ans) == 2 && n)
    {
        while (--n)
        {
            scanf(" %d", &tmp);
            ans = lcm(ans, tmp);
        }
        printf("%d\n", ans);
    }
    return 0;
}

d681: BinaryCount

2019-09-03

內容

對一個二進位的數字每一個位元進行 & 、| 運算

運算規則如下

1 & 1 = 1

1 & 0 = 0

0 & 1 = 0

0 & 0 = 0

1 | 1 = 1

1 | 0 = 1

0 | 1 = 1

0 | 0 = 0

輸入

輸入為一個二進位字串加上運算子 and 或 or

輸入的二進位字串<32 (5 bit)

且保證每個二進位字串長度一樣(5bit)

在每一行的最後會有一個空白

例如

10001 or 10000 and 11101 and 01001

  ^   ^    ^    ^    ^    ^    ^

依序是一個運算元+空白+運算子+空白+運算元+…最後是運算元+一個空白

每個運算元的長度都是 5bit ,但不一定都是 5 個運算元+4 個運算子

10001 or 10000 and 11101 and 01001
10111 or 10111 or 10010 or 00101
01000 and 01001 or 10011 and 11101
10111 and 00011 or 10010 or 11011
01001 and 10110 or 10010 and 11101

輸出

10001||10000&&11101&&01001 = 00001
10111||10111||10010||00101 = 10111
01000&&01001||10011&&11101 = 11001
10111&&00011||10010||11011 = 11011
01001&&10110||10010&&11101 = 10000

解題思路

整數型態比較好做位元運算，但輸出要把 input 格式化後重新輸出一遍，所以再將輸入的 2 進制字串轉換成整數做位元運算的同時順便做格式化存到 output，讀取到 input 字串結束後將得到解結果字串化進 output 輸出即可。

完整程式碼

AC (5ms, 72KB)

#include <stdio.h>

int ans, tmp;
char input[1100], output[1100], * iTop, * oTop;

void getBin(int* src)
{
    *src = 0;
    for (int i = 4; ~i; i--)
    {
        *src += ((*iTop - '0') << i);
        *oTop++ = *iTop++;
    }
}

int main()
{
    while (gets(input))
    {
        iTop = input, oTop = output, getBin(&ans);
        for (;;)
        {
            if (iTop[1] == 'o')
            {
                iTop += 4;
                *oTop++ = '|', * oTop++ = '|';
                getBin(&tmp);
                ans |= tmp;
            }
            else if (iTop[1] == 'a')
            {
                iTop += 5;
                *oTop++ = '&', * oTop++ = '&';
                getBin(&tmp);
                ans &= tmp;
            }
            else break;
        }
        *oTop++ = ' ', * oTop++ = '=', * oTop++ = ' ';
        for (int i = 0; i < 5; i++)
            * oTop++ = ((ans >> (4 - i)) & 1) + '0';
        *oTop = '\0';
        puts(output);
    }
    return 0;
}

d649: 數字三角形

2019-09-03

內容

小米是個喜歡畫三角形的小朋友

上課時小米覺得無聊都會在課本的一角畫三角形

首先畫了

＊

接著是

＊

＊＊

再來

＊

＊＊

＊＊＊

就這樣一直畫到下課

但是這樣太簡單而且太無聊了

小米想：為何我不向右對齊呢?

但就在下一節課小米嘗試畫出新三角形時

小米怎麼樣也沒辦法向右對齊

就請大家幫小米這個忙吧!

輸入

輸入一數字 N （0 ≤ N ≤ 1000）

代表小米想畫出高度為 N 的三角形

當 N 為 0 時結束程式，不需處理這行輸入

3
5
0

輸出

請輸出一個高為 N ，底也為 N 的三角形

每組輸出請用空行隔開

空白請用 '_' 代替

星號請用 '+' 代替

__+
_++
+++

____+
___++
__+++
_++++
+++++

解題思路

和 c419 基本上是同意題，將'*'換成'+'，陣列調大，輸入改成多筆測資輸入即可。

完整程式碼

AC (3ms, 116KB)

#include <stdio.h>

char s[1001];

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

d643: 勞動的符咒

2019-09-03

內容

繼上次你解決了梅蘭城符咒室的災難之後，
現在法師們又有新的問題了。
「想新符咒真是麻煩__」
於是法師們想出一個絕妙的辦法來產生新符咒
叫做「勞動的符咒」
假設有一長度為 8 的符咒 bcadefpa，
取數字 2 表示兩個字一組分成 bc,ad,ef,pa
然後將這四組字按照 ASCII 的順序排列成為 adbcefpa
這樣就可以製造出新符咒了
雖然省去了想新符咒的麻煩，
但是作這樣的分解排列卻讓法師們陷入另外一場混亂中，
你可以寫個程式幫幫他們嗎？

輸入

每個測資點的測資僅一列。即原符咒內容。
(字元長度不超過 100000 個字元，僅包含小寫英文字母)
假設符咒長度是 12 個字元，
那麼你必須由小到大列出 1、2、3、4、6 個字元一組的所有符咒
(也就是 12 的因數。當然了不必列 12，因為和原符咒一樣)
萬一發生分解排列後符咒與原本相同的話，
那麼就不用輸出該符咒。

efpabcad

輸出

輸出數種不同類型的符咒。一條符咒一列。
萬一無法產生新的符咒，
請輸出 bomb!

aabcdefp
adbcefpa
bcadefpa

解題思路

簡單的排序，用一個指標陣列去映射對應的位置來排序減少記憶體操作次數，輸出時先存到陣列裡再一併輸出減少調用 putchar()函式的時間。

完整程式碼

AC (60ms, 1.2MB)

#include <stdio.h>
#include <stdlib.h>
#define MAX 100010

int len, len2;
char input[MAX], * sort[MAX], output[MAX], * oTop;

int cmpsrc(int strLen)
{
    int k = 0;
    for (int i = 0; i < len2; i++)
    {
        for (int j = 0; j < strLen; j++)
        {
            if (sort[i][j] != input[k++])
                return 1;
        }
    }
    return 0;
}

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

int main()
{
    gets(input);
    for (len = 0; input[len]; len++)
        ;
    for (int i = 1; i < len; i++)
    {
        if (!(len % i))
        {
            len2 = len / i;
            for (int j = 0; j < len2; j++)
                sort[j] = &input[j * i];
            qsort(sort, len2, sizeof(char**), cmp);
            if (cmpsrc(i))
            {
                oTop = output;
                for (int j = 0; j < len2; j++)
                {
                    for (int k = 0; k < i; k++)
                        * oTop++ = sort[j][k];
                }
                *oTop = '\0';
                puts(output);
            }
        }
    }
    if (!oTop) puts("bomb!");
    return 0;
}

d637: 路過的鴨duck

2019-09-02

內容

有一天
有一隻路過的鴨 duck

牠…太餓結果就死了囧…

當他到天國的時候，
遇到了先前駕崩的鴨子王(duck king)，
牠變成了管理鴨子靈魂的神(duck king god，簡稱 duckingod)

duckingod 生前是一隻非常聰明的神鴨，
所以 duckingod 給這隻路過的鴨一個復活的機會。
給牠一袋鴨飼料，裡面的每顆飼料有不同的體積和飽足感
只要路過的鴨能夠在有限的食量內吃得最飽，
那牠就能復活了！

快寫個程式幫幫路過的鴨吧！呱呱呱！

輸入

每個測資點僅一組測資，不必 EOF 讀檔。
第一行有正整數 n(1<n<=10000)表示有 n 顆鴨飼料
接下來的 n 行，每行有 ab 兩個正整數，
a 代表這顆鴨飼料的體積，b 代表飽足感(1<=a<=100 , 1<=b<=5000)
並且鴨子最多可以吃滿 100 體積的飼料。

6
10 8
25 25
65 75
25 29
25 17
15 20

輸出

請輸出這袋鴨飼料能帶給路過的鴨的最大飽足感！

112

解題思路

經典的背包問題，飼料不能重複使用所以每種飼料從最大(100)飽足感 DP 到最小(飼料)飽足感。

完整程式碼

AC (4ms, 116KB)

#include <stdio.h>

int DP[101];

int main()
{
    int n, a, b;
    scanf(" %d", &n);
    while (n--)
    {
        scanf(" %d %d", &a, &b);
        for (int i = 100; i >= a; i--)
        {
            if (DP[i] < DP[i - a] + b)
                DP[i] = DP[i - a] + b;
        }
    }
    printf("%d", DP[100]);
    return 0;
}