e272: gcd(Fm,Fn)

2019-09-04

內容

給你 n,m,求 gcd(Fm,Fn)

*Fx 代表 Fibonacci 數列第 x 項

2019/6/8 時限調降至 0.5s

輸入

輸入有多行

每行有 m,n 兩數(m,n<=10000)

1 2
3 6

輸出

答案(保證可以用 unsigned long long 存)

1
2

解題思路

假設要求 GCD(f(25),f(20))，先展開 f(25)

= [1 * f(25-1)] + [1 * f(25-2)] ( f(m-1) = f(m-2) + f(m-3) )
= [2 * f(25-2)] + [1 * f(25-3)]
= [3 * f(25-3)] + [2 * f(25-4)] ( 2 * f(m-2) = [2 * ( f(m-3) + f(m-4) )] = 2 * f(m-3) + 2 * f(m-4) )
= [5 * f(25-4)] + [3 * f(25-5)]
= [8 * f(25-5)] + [5 * f(25-6)]

這時候可以發現兩件事

觀察*號左邊發現剛好會是費式數列，所以轉換成公式

f(m) = [f(m-n+1) * f(n)] + [f(m-n) * f(n-1)]

所以上面的式子就能轉換成 [f(6) * f(20)] + [f(5) * f(19)]
8 * f(20) 必為 f(20) 倍數，所以不必討論，也就是說接下來只需討論 '+' 右側的 f(5) * f(19) 和 f(20) 的最大功倍數，而此時因為 f(n) 和 f(n-1) 必定互質的關係 f(19) 也不必討論，只要求 GCD(f(5) , f(20)) 即可。

把以上兩個結論總和成一個公式 :

GCD(f(m) , f(n)) = GCD(f(m-n) , f(n))

然後發現每次轉換都會得到一組比較小的 GCD(f(m),f(n))，所以繼續用開頭的方式轉換新的 GCD(f(5),f(20))

展開 f(20) = [f(16) * f(5)] + [f(15) * f(4)]
轉換後變成 : GCD((f(15) , f(5))
展開 f(15) = [f(11) * f(5)] + [f(10) * f(4)]
轉換後變成 : GCD(f(10) , f(5))
展開 f(10) = [f(6) * f(5)] + [f(5) * f(4)]
轉換後變成 : GCD(f(5) , f(5)) = f(5) = 5

然後就會發現 GCD(f(m),f(n)) 就是再求 f(GCD(m,n))…

而題目保證答案可以用 unsigned long long 存，而費式數列第 94 項會超出 unsigned long long 的範圍，所以先建好 1~93 的費式數列表，之後查 F[GCD(m,n)] 輸出即可。

完整程式碼

正常版

AC (40ms, 88KB)

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

unsigned long long F[MAX] = { 0, 1 };

inline int GCD(int n, int m)
{
    while (n)
    {
        m %= n;
        SWAP(m, n);
    }
    return m;
}

int main()
{
    int m, n;
    for (int i = 2; i < MAX; ++i)
        F[i] = F[i - 1] + F[i - 2];
    while (scanf(" %d %d", &m, &n) == 2)
        printf("%llu\n", F[GCD(m, n)]);
    return 0;
}

AC (15ms, 1MB)

IO 優化版

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

unsigned long long F[MAX] = { 0, 1 };

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

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

inline int GCD(int n, int m)
{
    while (n)
    {
        m %= n;
        SWAP(m, n);
    }
    return m;
}

int main()
{
    int m, n;
    for (int i = 2; i < MAX; ++i)
        F[i] = F[i - 1] + F[i - 2];
    while (readUInt(&n), readUInt(&m))
        putULongLong(F[GCD(m, n)], '\n');
    return 0;
}

e189: 3的倍數 - 面試題

2019-09-04

內容

3 的倍數？沒有錯~又是 3 的倍數！

大家都知道判斷 3 的倍數就是把每一位相加，如果是 3 的倍數就能被 3 整除

那你知道如何不用除法” / “，取餘數” % “來判斷是否為 3 的倍數嗎？

輸入

每一行有一個數字 n，0 <= n <= 2147483647

EOF 結束

1
2
3

輸出

輸出該數字是否為三的倍數

如果是，輸出”YES”

否則，輸出”NO”

NO
NO
YES

解題思路

當一數的二進制偶數位和奇數位相差為 3 的倍數，則該數為 3 的倍數。

完整程式碼

AC (2ms, 96KB)

#include <stdio.h>

char mult3(int src)
{
    int res = 0;
    do
    {
        res += src & 1;
        src >>= 1;
        res -= src & 1;
    } while (src >>= 1);
    if (res < 0)
        res = -res;
    return res == 0 || res == 3 || res == 9 || res == 12 || res == 15 ||
        res == 18 || res == 21 || res == 24 || res == 27 || res == 30;
}

int main()
{
    int n;
    while (scanf(" %d", &n) == 1)
    {
        puts(mult3(n) ? "YES" : "NO");
    }
    return 0;
}

e163: 01地圖問題 1

2019-09-04

內容

小屮發現一張紙條，上面密密麻麻地寫滿了字。

經過研究，他發現紙條其實是張地圖，一共用了 64 種符號來編寫。

ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/

而編碼和解碼的對應能以下圖表示。

由於手動解碼過於費時，小屮希望你能幫忙將紙條上的文字還原。

輸入

第一行有兩個正整數 N, M (1 <= N, M <= 1200 且 M 為 6 的倍數)，代表地圖的長寬。

第 2 ~ N + 1 行分別有 M / 6 個字元，為紙條記載的內容。

3 12
L7
v/
Xe

輸出

輸出 N 行解碼後的內容。

001011111011
101111111111
010111011110

解題思路

先建好一個 000000 ~ 111111 的字串陣列，再用一個指標陣列按照索引映射到對應的位置上 (Ex: 65 (‘A’) 就映射到第 0 項 (“000000”))

建好表之後依照題意依序查表映射出對應答案輸出即可。

完整程式碼

AC (14ms, 84KB)

#include <stdio.h>
#include <memory.h>

char list[64][7], * map[256];

void setList(char list[][7], char* map[])
{
    register char* now = list;
    char tmp[5];
    for (int i = '0'; i <= '1'; i++)
    {
        tmp[0] = i;
        for (int j = '0'; j <= '1'; j++)
        {
            tmp[1] = j;
            for (int k = '0'; k <= '1'; k++)
            {
                tmp[2] = k;
                for (int l = '0'; l <= '1'; l++)
                {
                    tmp[3] = l;
                    for (int m = '0'; m <= '1'; m++)
                    {
                        tmp[4] = m;
                        memcpy(now, tmp, 5);
                        now[5] = '0', now += 7;
                        memcpy(now, tmp, 5);
                        now[5] = '1', now += 7;
                    }
                }
            }
        }
    }
    for (int i = 0; i < 26; i++)
        map['A' + i] = list[i];
    for (int i = 0; i < 26; i++)
        map['a' + i] = list[26 + i];
    for (int i = 0; i < 10; i++)
        map['0' + i] = list[52 + i];
    map['+'] = list[62];
    map['/'] = list[63];
}

int main()
{
    int n;
    char input[210];
    setList(list, map);
    scanf(" %d %*d", &n);
    getchar();
    for (int i = 0; i < n; i++)
    {
        gets(input);
        for (int j = 0; input[j]; j++)
            fputs(map[input[j]], stdout);
        putchar('\n');
    }
    return 0;
}

d586: 哈密瓜美語

2019-09-02

內容

「什麼？指導老師哈密瓜…這哪招阿！」
這不是重點，反正哈密瓜老師出來開幼兒美語補習班了。
哈密瓜老師為了加強小朋友的數字和英文字母對應能力，
他出了一道邪惡的謎題…

一般英文字母的排列是 abcdefghijklmnopqrstuvwxyz(a~z)
有種密碼是這樣的，
假如明文是 16 5 14 7 21 9 14，
那麼它的密文就是 penguin。
為什麼呢？因為 p 是第 16 個英文字母，e 是第五個，n 是第 14 個…以此類推

現在邪惡的哈密瓜把英文字母的排列給洗亂了，
並且出了雙向的謎題。
如果題目是由數字組成，就要解出英文單字
如果題目是由小寫字母組成，就要解出數字的總合
假設現在的字母排列是：jvkixcpomtfgdyhesrlzbqnwua
那麼整理出對應表如下：
1 j
2 v
3 k
4 i
5 x
6 c
7 p
8 o
9 m
10 t
11 f
12 g
13 d
14 y
15 h
16 e
17 s
18 r
19 l
20 z
21 b
22 q
23 n
24 w
25 u
26 a
數字：7 16 23 12 25 4 23 答案是 penguin
英文：p e n g u i n 答案是 7+16+23+12+25+4+23=110

–

好了，照慣例哈密瓜的智商有限，現在他自己也解不出他自己出的謎題了。

輸入

本題有兩個測資點。
第一行有整數 n(1<n<=100)，表示總共有幾條謎題
接下來的 n 行，每行有整數 m(1<=m<=10000)，
表示接下來有 m 個數字/英文字母要解密。
每個數字或是英文字母會以空格隔開，
並且數字一定在 1~26(包含)
英文字母必定是小寫
並且請注意…
如果題目是數字，程式要轉換成英文字母時，
必須使用的字母排列是：mjqhofawcpnsexdkvgtzblryui
相反的，如果題目給你英文字母，要算出對應數字總和時，
必須使用這套字母排列：uzrmatifxopnhwvbslekycqjgd

2
7 p e n g u i n
7 10 13 11 18 25 26 11

輸出

對應連續的數字，請按照規則排列輸出英文單字(連續無空格)
對應連續的字母，請按照規則排列輸出數字總合
(對範例測資來說，第一筆輸入 penguin 對應的數列是
11 19 12 25 1 7 12，總和是 87)

87
penguin

解題思路

依照題意建好數轉英、英轉數的表，而由於英轉數中的英是被打亂過的哈密瓜英文，所以再用一個正常序列的指標陣列去映射哈密瓜英文(ex : 第 0 項(正常的'a')就映射到哈密瓜英的第 4 項 (哈密瓜英文的'a'))。

建好表之後依照題意做字串處理和判斷即可。

完整程式碼

AC (2ms, 116KB)

#include <stdio.h>

const char n2e[] = "mjqhofawcpnsexdkvgtzblryui", e2n[] = "uzrmatifxopnhwvbslekycqjgd";
const char* e2e[] = { e2n + 4, e2n + 15, e2n + 21, e2n + 25, e2n + 18, e2n + 7, e2n + 24, e2n + 12,
            e2n + 6, e2n + 23, e2n + 19, e2n + 17, e2n + 3, e2n + 11, e2n + 9, e2n + 10, e2n + 22,
            e2n + 2, e2n + 16, e2n + 5, e2n + 0, e2n + 14, e2n + 13, e2n + 8, e2n + 20, e2n + 1 };
char input[30030], output[10010];

inline char* getUInt(char buffer[], unsigned int* dst)
{
    while (*buffer < '0')
        if (!*buffer++) return NULL;
    *dst = *buffer ^ '0';
    while (*++buffer >= '0')
        * dst = (*dst << 3) + (*dst << 1) + (*buffer ^ '0');
    return buffer;
}

int main()
{
    int n, m, tmp, sum;
    char* st, * oTop;
    scanf(" %d", &n);
    getchar();
    while (n--)
    {
        sum = 0;
        gets(input);
        st = getUInt(input, &m) + 1;
        if (st[0] < 'a')
        {
            oTop = output;
            for (int i = 0; i < m; i++)
                st = getUInt(st, &tmp), * oTop++ = n2e[tmp - 1];
            *oTop = '\0';
        }
        else
        {
            for (int i = 0; i < m; i++)
                sum += e2e[*st - 'a'] - e2n + 1, st += 2;
        }
        sum ? printf("%d\n", sum) : puts(output);
    }
    return 0;
}

d634: 魔法卡magic

2019-09-02

內容

繼梅蘭城的法師們在你的幫助下，成功節約符咒之後，
他們順利大量生產了各式魔法的符咒，但是…

符咒太多了所以把符咒室弄得亂七八糟的-▽-

所以請你寫一個程式再度幫助他們把符咒整理好吧。

輸入

每個測資點僅一組測資，不必 EOF 讀檔。
第一行有整數 n(1<n<=100000)表示接下來有 n 張符咒
從第二行開始的 n 行
每行有一個符咒的名稱，內容可能包含小寫字母、大寫字母、數字、空格字元。
並且每行不超過 10 個字元

7
penguin
jacker
jack doom
JACK
ws23
aszx87140
e196819

輸出

請依照”檔案系統”的方法，將這 n 個符咒排序後的結果輸出。
所謂檔案系統排序就是，
對於兩個英文單字的比較以 abc 和 xyz 來說，
先從第一個字母的”ASCII”值開始比，
(以這題出現的 ASCII 來說，空格<數字<大寫字母(A~~Z)<小寫字母(a~~z))
如 a<x，所以 abc 在 xyz 前面。
如果第一個字母相同，則比較下一個字母，如 abx 對上 aby，
比到第三位 x<y，所以 abx 在 aby 前面。

JACK
aszx87140
e196819
jack doom
jacker
penguin
ws23

解題思路

簡單的字串排序，除了存字串用的陣列，再開一個指標陣列去映射原陣列，這樣只要排序指標陣列並輸出就可以大幅減少記憶體操作的次數。

完整程式碼

AC (53ms, 2.7MB)

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

char list[100000][11], * sort[100000];

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

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        sort[i] = list[i];
    getchar();
    for (int i = 0; i < n; i++)
        gets(list[i]);
    qsort(sort, n, sizeof(char**), cmp);
    for (int i = 0; i < n; i++)
        puts(sort[i]);
    return 0;
}

e156: 良心題: 求和

2019-09-04

內容

如何不用乘法、除法、<<、>>、~、^，也不用 for、while、if、else、switch、case 及三元運算子，算出 1+2+3+…+n ?

輸入

輸入只有一個正整數 n。

1<=n<=1000

第一筆測資 in
3

第二筆測資 in
4

輸出

請輸出 1+2+3+…+n 的結果。

第一筆測資 out
6

第二筆測資 out
10

解題思路

兩種解法

利用短路求值的方式用邏輯閘代替 if
利用函式指標陣列和邏輯 NOT 取代 if

詳見下方程式碼。

完整程式碼

短路求值版

AC (2ms, 108KB)

#include <stdio.h>

int n, sum;

int dfs()
{
    return (sum += n) && --n && dfs();
}

int main()
{
    scanf(" %d", &n);
    dfs();
    printf("%d", sum);
    return 0;
}

函式指標陣列版

AC (2ms, 116KB)

#include <stdio.h>

int stop(int);

int dfs(int);

const int (*func[])(int) = { dfs ,stop };

int stop(int now)
{
    return 0;
}

int dfs(int now)
{
    return now + func[!now](now - 1);
}

int main()
{
    int n;
    scanf(" %d", &n);
    printf("%d", dfs(n));
    return 0;
}

e128: 新北100-1貪食蛇

2019-09-04

內容

輸入

輸入包含了 L+1 列(1<=L<=50)，前 L 列中每一列有一個正整數 Ni(1<=Ni<=2*10^9)，

代表 L 個貪蛇行進的秒數，最後一列以 0 代表輸入結束。

8
20
25
1
1000
10000000
0

輸出

對於輸入的每一個秒數，請輸出二個正整數，分別代表此時間點貪食蛇頭位置的橫座標與縱座標。

2 3
5 4
1 5
1 1
32 25
3163 1756

解題思路

將路線拆成兩部分

已經走完的正方形
正在走的 L 型

第一部分將總秒數開根號可以求得 (注意完全平方向的特舒情況)

第二部分在將總秒數減去上面正方形所需的秒數後判斷剩餘步驟是否大於前面正方形的邊長 + 1，如果是代表要轉彎，不是則不用。

最後定位到正確的位置輸出即可。

完整程式碼

AC (2ms, 140KB)

#include <stdio.h>
#include <math.h>

int main()
{
    int n, sr, pos;
    while (scanf(" %d", &n) == 1 && n)
    {
        sr = sqrt((double)n);
        if (sr * sr == n)
            sr--;
        n -= sr * sr;
        pos = sr + 1;
        if (pos & 1)
        {
            if (n < pos)
                printf("%d %d\n", pos, n);
            else
                printf("%d %d\n", (pos << 1) - n, pos);
        }
        else
        {
            if (n < pos)
                printf("%d %d\n", n, pos);
            else
                printf("%d %d\n", pos, (pos << 1) - n);
        }
    }
    return 0;
}

e102. C(n, k)

2019-09-04

內容

有 n 個點，求可以挑出幾個凸 k 邊形。

(這 n 個點共圓)

輸入

第一行有一個整數 t ( t <= 50 )，代表接下來有幾行。

接下來有兩個整數 n, k。(3 <= k <= n <= 20)。

代表從 n 個點取出 k 邊形。

2
6 4
3 3

輸出

輸出 n 個點可以挑出幾個 k 邊形。

15
1

解題思路

如題，C(n,k)。

完整程式碼

AC (2ms, 96KB)

#include <stdio.h>

int main()
{
    int kase, n, k;
    long long ans;
    scanf(" %d", &kase);
    while (kase--)
    {
        scanf(" %d %d", &n, &k);
        ans = 1;
        for (int i = n; i > k; i--)
            ans *= i;
        for (int i = n - k; i > 1; i--)
            ans /= i;
        printf("%lld\n", ans);
    }
    return 0;
}

e051: 文意字彙

2019-09-04

內容

聽說蝸牛老師在新課綱實施的第一年沒有課可以教，為了防止老師變成無殼蝸牛老師，所以學校打算讓他去教英文。

很快就到第一次段考了，在這次的段考，蝸牛老師負責出文意字彙。認真負責的蝸牛老師很快就把題目出完了，不過我們都知道文意字彙的題目是必須把欲考的單字中間挖空的，舉個例子，要考單字 snail，就得留住頭尾的字母后，把中間全部變成底線，於是就變成了 s___l。

蝸牛老師打算把題目出完之後再一個一個挖空，由於他原本是資訊老師，所以他打算寫一支程式來解決這個問題。

輸入

輸入只有一行，為一個英文單字，保證單字長度介於 [3,1000] ，且字串裡只有大小寫英文字母。

snail

輸出

為了簡化問題，我們不考慮留住多餘字元的問題，請輸出把輸入單字頭尾字母留住、中間全填成底線後的單字長相。

s___l

解題思路

簡單的字串處理。

完整程式碼

AC (2ms, 112KB)

#include <stdio.h>

char s[1010];

int main()
{
    gets(s);
    for (int i = 1; s[i + 1]; i++)
        s[i] = '_';
    puts(s);
    return 0;
}

d985: Gran Turismo 5

2019-09-03

內容

輸入

第一行有一個數字 N (0 < N ≤ 10)

代表接下來有 N 組測試資料

每組測試資料第一行有一個數字 M (0 < M ≤ 100)

接著有 M 行資料

每行兩個數字 A, B (0 ≤ A, B ≤ 60)

代表該圈所花費時間為 A 分 B 秒

3
4
1 54
2 02
1 58
1 50
3
1 23
1 42
1 37
5
3 00
2 56
3 04
2 50
3 01

輸出

Track X:

Best Lap: X minute(s) X second(s).

Average: X minute(s) X second(s).

Average 為整數，小數部份無條件捨去

詳請參考範例測資

Track 1:
Best Lap: 1 minute(s) 50 second(s).
Average: 1 minute(s) 56 second(s).

Track 2:
Best Lap: 1 minute(s) 23 second(s).
Average: 1 minute(s) 34 second(s).

Track 3:
Best Lap: 2 minute(s) 50 second(s).
Average: 2 minute(s) 58 second(s).

解題思路

將時間轉成秒來比較，取得最佳和平均秒數後再將秒格式化回去輸出即可。

完整程式碼

AC (2ms, 108KB)

#include<stdio.h>

int main()
{
    int track, lap, time, best, sum, min, sec;
    while (scanf(" %d", &track) == 1)
    {
        for (int t = 1; t <= track; t++)
        {
            best = 999999, sum = 0;
            scanf(" %d", &lap);
            for (int l = 0; l < lap; l++)
            {
                scanf(" %d %d", &min, &sec);
                time = min * 60 + sec;
                if (time < best)
                    best = time;
                sum += time;
            }
            sum /= lap;
            printf("Track %d:\n", t);
            printf("Best Lap: %d minute(s) %d second(s).\n", best / 60, best % 60);
            printf("Average: %d minute(s) %d second(s).\n\n", sum / 60, sum % 60);
        }
    }
    return 0;
}