今年的成績比去年進步，終於通過了資格賽，這次有找朋友一起參加，賽後一起討論題目怎麼解還蠻有趣的，明年繼續努力。

第一題 Foregone Solution

連結

題意:

有人贏得 Code Jam 彩券，需要印出數字 N 的支票，但打印機上鍵盤的 4 卻壞掉了，N 的值是一個正整數，且至少包含一個數字 4。

不過幸運的是，我們可以將 N 分解成兩個正整數 A、B，使 A + B = N，且 A、B 都不包含 4，請找到滿足條件的任一 A 和 B。

輸入輸出:

Input  | Output 
-------|--------
3      | 
4      | Case #1: 2 2
940    | Case #2: 852 88
4444   | Case #3: 667 3777

解法:

這題還蠻簡單的，將 N 的每個位數依序讀入，
如果碰到 4，則將 1 加到 A 上，3 加到 B 上，
如果不是 4，則將該數加到 A 上，
因為 N 至少包含一個 4，所以迴圈跑完後一定可以得到 A、B 兩數。

這題有三個 Case，通過前兩個。

程式碼:

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

int main() 
{
    int c = 0;
    int testcase;
    scanf("%d", &testcase);

    while (testcase--)
    {
        int N;
        scanf("%d", &N);

        int digit = 1;
        int num = 0;

        int a = 0;
        int b = 0;

        while(N > 0) 
        {
            num = N % 10;
            if (num == 4)
            {
                a += 3 * digit;
                b += 1 * digit;
            }
            else
            {
                a += num * digit;
            }
            N /= 10;
            digit *= 10;
        }

        printf("Case #%d: %d %d\n", c + 1, a, b);
        
        c++;
    }

    //system("pause");
    return 0;
}

第二題 You Can Go Your Own Way

連結

題意:

有一個 N x N 大小的迷宮，你必需從西北的網格開始移動到東南的網格，你只有兩種移動方式，向東移動一單元格，或向南移動一個單元格。

你有一個競爭對手 Labyrinth Lydia，你不能重複對手的路徑，例如對手的路徑包含 A 到相鄰單元格 B 的移動，你的路徑就不能包含 A 到 B 的移動。

請找出一條符合上述條件的任一路徑。

輸入輸出:

Input    | Output 
---------|--------
2        | 
2        |
SE       | Case #1: ES
5        |
EESSSESE | Case #2: SEEESSES

解法:

因為迷宮是一個正方形，我們只需和對手做相反的移動，就能得到一個對稱的路徑，對手往東我們就往南，對手往南我們就往東。

這題有三個 Case，三個都通過。

程式碼:

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

using namespace std;

int main() 
{
    int c = 0;
    int testcase;
    scanf("%d", &testcase);

    while (testcase--)
    {
        int N;
        scanf("%d", &N);

        vector<char> str;

        int size = N * 2 - 2;
        str.resize(size);

        scanf("%*c");
        for(int i=0; i<size; i++)
        {
            scanf("%c", &str[i]);
        }

        printf("Case #%d: ", c + 1);
        for(int i=0; i<size; i++)
        {
            if (str[i] == 'E')
                printf("S");
            else
                printf("E");
        }
        printf("\n");

        c++;
    }

    //system("pause");
    return 0;
}

第三題 Cryptopangrams

連結

題意:

這題需要對密文進行解密，加密規則如下:

1. 我們選擇了 26 個不同的質數，其中沒有一個是比 N 更大的整數。
2. 我們按遞增順序對這些質數進行排序，然後將最小的質數分配給字母 A，將第二小的分配給 B，依此類推。
3. 我們會將明文的第一個字母和第二個字母的質數乘積當作密文的第一個值，然後將明文的第二個字母和第三個字母的質數乘積當作密文的第二個值，依此類推。以倒數第二和最後一個字母的質數乘積結束，這個新的值列表為我們的密文，數量比明文消息的字母數小一。
4. 明文中至少使用一次英文字母的每個字母。

例如，假設 N = 103 並且我們選擇使用前 26 個質數，A=3，B=5，C=7，D=11，依此類推，Z=103，接著假設我們需要加密的明文為 CJQUIZKNOWBEVRITHMS，密文的第一個值就是 7 (C) 乘 31 (J) = 217，下一個值是 1891，依此類推，以 3053 結尾。

請將密文解密回明文。

輸入輸出:

Input    | Output 
---------|--------
2 
103 31   | 217 1891 4819 2291 2987 3811 1739 2491 4717 445 901 187 649 1003 697 3239 7663 291 123 779 1007 3551 1943 2117 1679 989 3053 
10000 25 | 3292937 175597 18779 50429 375469 1651121 2102 3722 2376497 611683 489059 2328901 3150061 829981 421301 76409 38477 291931 730241 959821 1664197 3057407 4267589 4729181 5335543

解法:

假設明文代表的質數為 abc，密文的第一個值等於 a x b，第二個等於 b x c，可以看出 b 就等於兩個密文值的最大公因數。

接下來可能會遇到 aba 這種情況，相鄰的兩個密文會有相同的值，不過題目有提到明文最少會使用每個字母一次，所以不用擔心可以先跳過相同的值，回頭再來看。

整理後的邏輯是:

1. 先找到兩個不相同的密文值
2. 對兩密文值進行輾轉相除法找到最大公因數
3. 以最大公因數向前、向後找出所有的質數
4. 將質數排序後得到所有字母
5. 最後依字母還原明文

這題有兩個 Case，只通過第一個。

第二個 Case 需要進行大數運算，找時間再研究如何對大數進行輾轉相除。

程式碼:

#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <map>

using namespace std;

long long euclidean(long long a, long long b)
{
    long long temp;
    while (b != 0)
    {
        temp = b;
        b = a % b;
        a = temp;
    }
    return temp;
}

int main() 
{
    int c = 0;
    int testcase;
    scanf("%d", &testcase);

    while (testcase--)
    {
        long long N;
        int L;

        scanf("%lld", &N);
        scanf("%d", &L);

        long long nums[100];

        for(int i=0; i<L; i++)
        {
            scanf("%lld", &nums[i]);
        }

        vector<long long>answer;
        answer.resize(L + 1);

        //找到第一個沒有重複的點
        int index = 0;
        for(int i=0; i<L-1; i++)
        {
            if (nums[i] != nums[i+1])
            {
                index = i;
                break;
            }
        }

        //算出第一個質數
        long long prime = euclidean(nums[index], nums[index + 1]);
        answer[index + 1] = prime;

        //往後找出所有答案
        for (int i=index+1; i<L; i++)
        {
            answer[i + 1] = nums[i] / answer[i];
        }
        //往前找出所有答案
        for (int i=index; i>=0; i--)
        {
            answer[i] = nums[i] / answer[i + 1];
        }

        //產生對應表
        map<long long, char> answerMap;
        for(int i=0; i<answer.size(); i++)
        {
            answerMap.insert(make_pair(answer[i], '\0'));
        }
        //排序質數
        char letter = 'A';
        for (map<long long, char>::iterator it=answerMap.begin(); it!=answerMap.end(); ++it)
        {
            it->second = letter;
            letter++;
        }

        //印出解答
        printf("Case #%d: ", c + 1);
        for(int i=0; i<answer.size(); i++)
        {
            printf("%c", answerMap[answer[i]]);
        }
        printf("\n");

        c++;
    }

    //system("pause");
    return 0;
}

第四題 Dat Bae

連結

題意:

研究聯盟建立了一個新的資料庫系統，由一台計算機和 N 台工作機組成，工作機的 ID 為 0 到 N-1，計算機主機每次可以發送 N 個字元，並將第 i 位的字元發送給第 i 個工作機。

正常操作期間，工作機讀取字元後會回傳相同的字元給計算機主機，但有個不好的消息，有 B 台工作機壞掉了，壞掉的工作機不會回傳任何字元，因此每次發送字元，只會接收到回傳的 N - B 個字元，這些字元會按照工作機的 ID 排列。

假設 N = 5 並且第 0 和第 3 個工作機壞掉了。

• TEST_STORE 01101 回報 111
• TEST_STORE 00110 回報 010
• TEST_STORE 01010 回報 100
• TEST_STORE 11010 回報 100

請找出壞掉工作機的 ID。

解法:

這題是經典的老鼠毒藥問題，我們可以將每一台工作機的編號看成一個二進制數，接下來按位發送位元，10 次後統計回傳結果，缺少的數就是壞掉的工作機編號。

這題有兩個 Case，只通過第一個。

第二個 Case 需要在 5 次內比對 1024 台工作機，目前還沒想到好方法。

程式碼:

#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <set>

using namespace std;

int main() 
{
    int c = 0;
    int testcase;
    scanf("%d", &testcase);

    while (testcase--)
    {
        int N, B, F;
        scanf("%d %d %d", &N, &B, &F);

        vector<int>answer;
        answer.resize(N);

        for(int i=0; i<N; i++)
        {
            answer[i] = 1;
        }

        vector<int>nums(N-B, 0);

        set<int> check;
        set<int>::iterator it;

        char temp;
        int digit = 0;
        while (1==1)
        {
            //輸出
            for (int i=0; i<N; i++)
            {
                printf("%c", (i >> digit & 1) + '0');
            }
            printf("\n");
            fflush(stdout);
            scanf("%*c");

            //讀取
            int isFinish = false;
            for (int i=0; i<N-B; i++)
            {
                scanf("%c", &temp);
                if (temp == '-')   //回傳-1
                {
                    isFinish = true;
                    break;
                }
                nums[i] = nums[i] + ((temp - '0') << digit);
            }
            if (isFinish)
                break;

            check.clear();
            for (int i=0; i<N-B; i++)
            {
                check.insert(nums[i]);
            }

            //排除與回傳結果不符的項目
            int bcnt = 0;
            int mask;
            for (int i=0; i<N; i++)
            {
                //1024最多有11位
                mask = 2047 >> (11-digit-1);
                it = check.find(i & mask);
                if (it != check.end())
                {
                    answer[i] = 1;
                }
                else
                {
                    answer[i] = 0;
                    bcnt++;
                }
            }

            if (bcnt == B)
            {
                bool isFirst = true;
                for (int i=0; i<N; i++)
                {
                    if (answer[i] == 0)
                    {
                        if (isFirst)
                        {
                            printf("%d", i);
                            isFirst = false;
                        }  
                        else
                        {
                            printf(" %d", i);
                        }
                    }
                }
                printf("\n");
                fflush(stdout);
                scanf("%*d");
                break;   //成功或失敗都退出
            }

            digit++;
        }
        
        c++;
    }

    //system("pause");
    return 0;
}

Round1A 第一題 Pylons

連結

解法:

這題沒有想到什麼好的解法，只好把所有結果跑一次，只通過第一個 Case。

程式碼:

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

using namespace std;

int func(vector<vector<int>> &map, int r, int c, int x, int y, int lv, vector<int> &ans_r, vector<int> &ans_c)
{
    if (r*c == lv)
    {
        return 1;
    }
    for(int i=0; i<r; i++)
    {
        for(int j=0;j<c;j++)
        {
            if (map[i][j] == 0 &&
                i != x && j != y &&
                i-j != x-y && i+j != x+y)
            {
                map[i][j] = lv+1;
                if (func(map, r, c, i, j, lv+1, ans_r, ans_c) == 1)
                {
                    ans_r.insert(ans_r.begin(), i);
                    ans_c.insert(ans_c.begin(), j);
                    return 1;
                }
                map[i][j] = 0;
            }
        }
    }
    return 0;
}

int main() 
{
    int c = 0;
    int testcase;
    scanf("%d", &testcase);

    while (testcase--)
    {
        int R, C;
        scanf("%d %d", &R, &C);
        
        vector<vector<int>>map(R, vector<int>(C, 0));
        vector<int> ans_r;
        vector<int> ans_c;
        ans_r.reserve(R*C);
        ans_c.reserve(R*C);

        if (func(map, R, C, -1, -1, 0, ans_r, ans_c) == 1)
        {
            printf("Case #%d: POSSIBLE\n", c+1);
            for(int i=0; i<R*C; i++)
            {
                printf("%d %d\n", ans_r[i]+1, ans_c[i]+1);
            }
        }
        else
        {
            printf("Case #%d: IMPOSSIBLE\n", c+1);
        }
        
        c++;
    }

    //system("pause");
    return 0;
}

結語

今年運氣比較好輾轉相除法和老鼠毒藥，賽前有看到相關文章，看到題目後馬上就連想到解法，反而是最簡單的第一題，想了很久沒有抓到重點，第二題和第一題有點類似，都是題目敘述感覺有陷阱，但抓到重點後很快就能寫出來，第二題寫得還蠻順的。

第三題因為使用 C++ 碰到大數運算比較吃虧，應該找時間把基本大數運算的函數先寫好，比賽時直接呼叫就好，比賽當下有稍微研究大數取 mod 的方式，感覺蠻複雜的，時間不夠所以就先放棄。

比賽結果