d049: 中華民國萬歲！

2019-08-26

內容

國父孫中山於 1911 年武昌起義推翻滿清創立中華民國，並訂次年 (1912) 年為中華民國元年。從此國民政府便以中華民國國號記年至今。請寫一程式，將輸入的西元年份轉換成民國年份後輸出。

輸入

輸入僅有一行，其中包含一個西元年份 y (1912 ≤ y ≤ 2147483647)。

2008

輸出

輸出所算出的民國年份。

97

解題思路

西元年 - 1911 = 民國年。

完整程式碼

AC (2ms, 116KB)

#include <stdio.h>

int main()
{
    int n;
    while (scanf(" %d", &n) == 1)
    {
        printf("%d\n", n - 1911);
    }
    return 0;
}

d018: 字串讀取練習

2019-08-26

內容

練習字串的分析與處理

輸入

一個字串，內部包含數組資料，每組資料有一個序號，及一個實數。

格式如下：序號:實數

請注意，序號有可能跳號

1:12.5 2:12 3:13.1 4:13.0
1:1.2 3:2.3

輸出

請求出所有序號為奇數的實數的和減掉所有序號為偶數的實數，並印出結果。

0.6
3.5

解題思路

每筆測資以空白作為各資料的分割點，再以冒號作為各資料中序號及實數的分割點。

處理完字串後按題意對最終答案進行加或減即可。

完整程式碼

AC (2ms, 100KB)

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

double num, sum;
int idx;
char input[10000], * tok;

int main()
{
    while (gets(input) != NULL)
    {
        sum = 0, tok = strtok(input, " ");
        while (tok != NULL)
        {
            sscanf(tok, "%d:%lf", &idx, &num);
            sum += idx & 1 ? num : -num;
            tok = strtok(NULL, " ");
        }
        printf("%g\n", sum);
    }
    return 0;
}

d016: 後序運算法

2019-08-26

內容

後序運算式(postfix)有別於我們習慣的算式寫法(infix)，是把運算子寫在運算元之後，雖然對人來說可讀性很低，可是對電腦來說卻是很方便的運算式子。運算式用後序表示法的好處還有不用去考慮中序式的先乘除後加減的問題以及免除所有的括號。

比如我們習慣 3 + 5 這樣的式子，就是中序運算式

同一個式子改成後序寫法即為 3 5 +

現在給你一個後序運算式，請求出這個式子的結果。

輸入

輸入一個後序運算式的字串包含數個運算子及運算元，為了方便讀取，所有的運算元與運算子之間都以空格隔開。

運算子包含 + - * / % 等五個

運算元則為 0 ~2³¹ -1 的整數

3 5 +
6 3 / 1 4 - * 3 + 8 -

輸出

輸出該後序運算式的結果。

為避免小數誤差問題，運算結果必定為整數，運算過程中也必定不會出現小數的結果，因此請放心使用整數來進行運算

8
-11

解題思路

後序轉中序輸出。

完整程式碼

AC (2ms, 100KB)

#include <stdio.h>
#define MAX 10000

long long stack[MAX];
int sTop;
char postfix[MAX];

long long cale(long long lhs, long long rhs, char op)
{
    switch (op)
    {
    case '+': return lhs + rhs;
    case '-': return lhs - rhs;
    case '*': return lhs * rhs;
    case '/': return lhs / rhs;
    case '%': return lhs % rhs;
    }
    return -1;
}

long long postfixToInt(char* postfix)
{
    stack[0] = sTop = 0;
    char* now = postfix - 1;
    for (int i = 0; postfix[i]; i++)
    {
        if (postfix[i] >= '0' && postfix[i] <= '9')
            stack[sTop] = (stack[sTop] << 3) + (stack[sTop] << 1) + (postfix[i] - '0');
        else if (postfix[i] == ' ')
            sTop++;
        else
        {
            sTop -= 2;
            stack[sTop] = cale(stack[sTop], stack[sTop + 1], postfix[i]);
            stack[sTop + 1] = 0;
        }
    }
    return stack[0];
}

int main()
{
    while (gets(postfix) != NULL)
    {
        printf("%lld\n", postfixToInt(postfix));
    }
    return 0;
}

線上解題
ZeroJudge
d010: 盈數、虧數和完全數

d010: 盈數、虧數和完全數

2019-08-26

內容

對一個正整數 N 而言，將它除了本身以外所有的因數加起來的總和為 S，如果 S>N，則 N 為盈數，如果 S<N，則 N 為虧數，而如果 S=N，則 N 為完全數(Perfect Number)。例如 10 的因數有 1、2、5、10，1+2+5=8<10，因此 10 為虧數，而 12 的因數有 1、2、3、4、6、12，1+2+3+4+6=16>12，因此 12 為盈數。至於 6 的因數有 1、2、3、6，1+2+3=6，所以 6 是完全數(它也是第一個完全數)。

現在請你寫一個程式，輸入一個正整數 N，然後印出它是盈數、虧數還是完全數。

輸入

30
26
28

輸出

盈數
虧數
完全數

解題思路

輸入數組不大，用迴圈試除找因數相加判斷即可。

完整程式碼

AC (2ms, 72KB)

#include<stdio.h>

int main()
{
    int n, k;
    while (scanf(" %d", &n) == 1)
    {
        k = 0;
        for (int i = n - 1; i > 0; i--)
        {
            if (!(n % i))
                k = k + i;
        }
        if (k < n)
            puts("虧數");
        else if (k > n)
            puts("盈數");
        else
            puts("完全數");
    }
    return 0;
}

線上解題
ZeroJudge
c929: 蝸牛老師的點名單-續

c929: 蝸牛老師的點名單-續

2019-08-26

內容

繼第一堂課之後同學們因為太無聊了，開始在他們的名字之間空格改成各種不同的字串，例如” and “(不含引號)，假設有兩位同學名字分別是”apple”及”banana”則他們會把點名單寫成”apple and banana”(不含引號)，蝸牛老師很頭痛，希望你幫他寫一個程式把大家的名字分成一行一行的。

輸入

第一行為一個字串 s 代表大家名字中間的字串，第二行為蝸牛老師拿到的點名單。(字元範圍為 ASCII 32~126) 字串長度皆小於 1000

範例一:
and
appleandbanana

範例二
,
baluteshih ,leo , alan

輸出

請將同學們名字分成一行一行輸出。

範例一:
apple
banana

範例二:
baluteshih
leo
alan

解題思路

簡單的字串處理。

完整程式碼

AC (2ms, 92KB)

#include <stdio.h>
#define SIZE 2000

int oLen;
char spilt[SIZE], input[SIZE], output[SIZE];

inline int strspt(int* idx, char* spilt)
{
    int i = 0;
    for (; spilt[i]; i++)
    {
        if (input[*idx + i] != spilt[i] || !input[*idx + i])
            return 0;
    }
    *idx += i - 1;
    return 1;
}

int main()
{
    gets(spilt), gets(input);
    for (int i = 0; input[i]; i++)
    {
        if (strspt(&i, spilt))
            output[oLen++] = '\n';
        else
            output[oLen++] = input[i];
    }
    puts(output);
    return 0;
}

c782: PC. 孤單值量測

2019-08-25

內容

在一條馬路上有 n 個人，每個人都站在一個位置 a_i，都有一個孤單評測值 w_i。現在里長想計算這些人的孤單值總和，如果第 i 個人和第 j 個人的位置相差大於 k 公尺，那麼他們會對總孤單值 S 貢獻 w_i*w_j。現在，請你幫我求出 S。

輸入

輸入第一行有一個正整數 t(t≤5)，表示一共有 t 筆測資。
每筆測資的第一行有兩個正整數 n(n≤2000000),k(k≤1000000000)，第二行有 n 個整數 a_i(0≤ai≤1000000000,1≤i≤n)，輸入保證從小到大。
第三行有 n 個整數 w_i(−1000≤w_i≤1000,1≤i≤n)。

1
5 3
1 2 3 4 5
2 3 4 5 6

輸出

對每一筆測資，請輸出一個正整數 S。

12

解題思路

依據題意"輸入保證從小到大"所以當 i < j 時 a[i] 必小於 a[j]，因此可以假設當第 i 項可以與第 j 項產生孤單值時，第 1~i 項都可以和第 j 項產生孤獨值，因為比 i 小的值與 j 的距離必定比 i 更遠。

所以先找到距離 j 點最近但距離又大於 k 的 i 點，並將所有 i 點紀錄至陣列 v[]，如此一來之後要算孤獨單值時就不用再從 0 開始遍歷，直接查表 v[] 就好。

接下來計算孤獨值，因為孤獨值是互相的，所以只算往前的孤獨值避免重複計算。
假如 j = 5、 i = 3，且 j 和 i 可以產生孤獨值，那點 j 的的孤獨值就是

w[1] * w[5] + w[2] * w[5] + w[3] * w[5]

而根據乘法的分配律，可以將上式轉為

(w[1] + w[2] + w[3]) * w[5]

這樣在算孤獨值時只要先將答案加上 w[v[i]] * w[i]，再把 w[i]加上 w[i-1]，就可以省下迴圈做連續乘法的時間了。

本題輸入測資非常大，輸入優化可以壓掉不少時間。

完整程式碼

正常版

AC (0.3s, 23MB)

#include <stdio.h>
#define MAX 2000010

long long sum, w[MAX];
int kase, n, k;
int a[MAX], v[MAX];

int main()
{
    scanf(" %d", &kase);
    while (kase--)
    {
        sum = 0;
        scanf(" %d %d", &n, &k);
        for (int i = 1; i <= n; i++)
            scanf(" %d", &a[i]);
        for (int i = 1, s = 1; i <= n; i++)
        {
            while (a[i] - a[s] > k)
                s++;
            v[i] = s - 1;
        }
        for (int i = 1; i <= n; i++)
        {
            scanf(" %d", &w[i]);
            sum += w[v[i]] * w[i];
            w[i] += w[i - 1];
        }
        printf("%lld\n", sum);
    }
    return 0;
}

輸入優化版

AC (41ms, 24MB)

#pragma GCC optimize(3)
#include <stdio.h>
#define MAX 2000010
#define BUFMAX 1048576

long long sum, w[MAX];
int kase, n, k, length = BUFMAX, a[MAX], v[MAX];
char buf[BUFMAX], tmp, * pt = buf, * end = buf;

inline char freadChar()
{
    if (pt == end)
    {
        if (length < BUFMAX)
            return EOF;
        length = fread(buf, 1, BUFMAX, stdin);
        end = buf + length;
        pt = buf;
    }
    return *pt++;
}

inline void freadUInt(int* val)
{
    while ((tmp = freadChar()) < '0')
        if (tmp == EOF) return;
    *val = tmp - '0';
    while ((tmp = freadChar()) >= '0')
        * val = (*val << 3) + (*val << 1) + (tmp - '0');
}

inline void freadLongLong(long long* val)
{
    while ((tmp = freadChar()) < '-')
        if (tmp == EOF) return;
    if (tmp == '-')
    {
        *val = freadChar() - '0';
        while ((tmp = freadChar()) >= '0')
            * val = (*val << 3) + (*val << 1) + (tmp - '0');
        *val = -*val;
    }
    else
    {
        *val = tmp - '0';
        while ((tmp = freadChar()) >= '0')
            * val = (*val << 3) + (*val << 1) + (tmp - '0');
    }
}

int main()
{
    scanf(" %d", &kase);
    while (kase--)
    {
        sum = 0;
        freadUInt(&n), freadUInt(&k);
        for (int i = 1; i <= n; i++)
            freadUInt(&a[i]);
        for (int i = 1, s = 1; i <= n; i++)
        {
            while (a[i] - a[s] > k)
                s++;
            v[i] = s - 1;
        }
        for (int i = 1; i <= n; i++)
        {
            freadLongLong(&w[i]);
            sum += w[v[i]] * w[i];
            w[i] += w[i - 1];
        }
        printf("%lld\n", sum);
    }
    return 0;
}

線上解題
ZeroJudge
c760: 蝸牛老師的點名單 (再續)

c760: 蝸牛老師的點名單 (再續)

2019-08-25

內容

蝸牛老師新開了一門課，第一堂課時拿了一張白紙讓學生簽到。現在他需要用簽到單上的名字製作一份點名單。當他開始這個工作時，他發現現在的學生實在太偷懶，連寫名字時字首都沒大寫。

輸入

輸入只有一行，含有 n 個 (1 ≤ n ≤ 30) 以空白隔開的學生名字。所有名字均由小寫字母組成。

john mary steve david

輸出

將每個名字單獨輸出於一行，並將字首改成大寫。

John
Mary
Steve
David

解題思路

簡單的輸入輸出。

完整程式碼

AC (2ms, 92KB)

#include <stdio.h>

char s[1000];

int main()
{
    while (scanf(" %s", s) == 1)
    {
        s[0] -= 32;
        puts(s);
    }
    return 0;
}

c726: K-I-S-S-I-N-G (一行版)

2019-08-25

內容

在美國有一首童謠的歌詞如下：

(女孩名) and (男孩名) sitting in the tree
K-I-S-S-I-N-G!
First comes love
Then comes marriage
Then comes baby
In a baby carriage!

當孩子們玩在一起時，如果發現某個女孩或男孩有喜歡某個異性的跡象時，他們就會把兩個人的名字套到歌詞的第一行，用來取笑當事人，讓他們覺得不好意思。電影「汽車總動員」中，脫線就是用這首童謠來取笑莎莉和麥坤的。

給你一個女孩名和男孩名，要請你把它們套在第一行的歌詞裡。

輸入

輸入只有一行，含有兩個由空白隔開的名字，第一個為女孩名，第二個為男孩名。名字中間不會有空白。

Sally McQueen

輸出

把女孩名和男孩名套入第一行歌詞後輸出。

Sally and McQueen sitting in the tree

解題思路

簡單的輸入輸出。

完整程式碼

AC (2ms, 104KB)

#include <stdio.h>

char g[100], b[100];

int main()
{
    scanf(" %s %s", g, b);
    printf("%s and %s sitting in the tree\n", g, b);
    return 0;
}

c717: You can say that again!

2019-08-25

內容

在英文的世界裡，當你同意對方的說法時，會要求對方再講一次。(誤

輸入

輸入只有一行，含有要輸出的敘述。

Snail is handsome.

輸出

輸出所輸入的敘述兩次於同一行。

Snail is handsome. Snail is handsome.

解題思路

簡單的輸入輸出。

完整程式碼

AC (2ms, 84KB)

#include <stdio.h>

char str[1000];

int main()
{
    gets(str);
    printf("%s %s\n", str, str);
    return 0;
}

c716: Johnny B. Goode

2019-08-25

內容

(Johnny B. Goode) (參考譯名 (強尼·B·古德)) 是一首 1958 年的搖滾 (rock and roll) 歌曲，最初由查克·貝里創作和表演。這首歌當時在黑人和白人聽眾群中都很流行，在《公告牌》的「節奏布魯斯／嘻哈音樂排行榜」上最高達到第二位，在「公告牌百強單曲榜」上排名第八位。

該曲是貝里最著名的歌曲之一，被許多音樂人翻唱，並收穫了一系列的榮譽和嘉獎。它也被認為是音樂史上辨識度最高的歌曲之一。

查克·貝里在 1955 年寫出這首歌，內容是關於一個貧窮的鄉村男孩，他「就像搖一隻鈴鐺」那樣彈奏吉他 (“just like ringing a bell”)，希望有一天能「成名」(“name in lights”)。

(取自 Wikipedia)

歌曲中的副歌中一直重覆著 “Go, Johny, go go”，意思當然就是「強尼加油！」。現在就請你寫一支程式，為其他的人加油！

輸入

輸入只有一行，含有你要加油的人的名字。

Johnny

輸出

輸出「Go, 人名, go go」，請參考範例輸出。

Go, Johnny, go go

解題思路

簡單的輸入輸出，注意輸入有空格在裡面即可。

完整程式碼

AC (2ms, 92KB)

#include <stdio.h>

char str[1000];

int main()
{
    gets(str);
    printf("Go, %s, go go", str);
    return 0;
}