iT邦幫忙

5

[Google Code Jam] 2018 資格賽

感謝 海綿寶寶 的邀請,今年參加了 Google Code Jam 2018 的比賽,雖然很可惜,連資格賽都沒有過,不過題目真的蠻有趣的,明年再接再厲。

第一題 Saving The Universe Again

題意:

有一個外星機器人正在攻擊宇宙,機器人攻擊強度初始為1,機器人會有兩種操作如下:

  1. C 充電,會使攻擊光束強度加倍
  2. S 攻擊,射擊光束,造成當前光束強度的傷害

以 SCCSSC 舉例

  1. 射擊,造成1點傷害
  2. 充電,強度翻倍至2
  3. 充電,強度翻倍至4
  4. 射擊,造成4點傷害
  5. 射擊,造成4點傷害
  6. 充電,強度翻倍至8

科學家發明了一種可以承受 D值傷害的盾牌,
總統可以入侵機器人,每次交換相鄰的兩個指令,
我們要算出最少需要交換幾次命令,可以使機器人攻擊傷害不超過 D值。

解法:

這題可以用貪婪法來解,先以兩個指令來看,因為 先攻擊後充電 會比 先充電後攻擊 帶來的傷害還低,所以只要遇到 CS 就交換,就能保證總傷害最低。

接著觀察交換的動作可以 由左至右,也可以 由右至左,不過由右至左的交換能降低更多的傷害,因此我們程式的邏輯是。

由右至左遇到 CS 指令就交換,直到總傷害小於等於 D 值

結果

小 CASE 正確,大 CASE 錯誤。

程式碼

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

using namespace std;

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

    while (testcase--)
    {
        int D;
        string P;

        scanf("%d", &D);
        cin >> P;

        int maxIndex = 0; //最大索引
        int index = 0;    //當前索引
        int sum = 0;      //總傷害
        int power = 1;    //能量強度
        int change = 0;   //交換次數

        //先計算總傷害
        for (int i = 0; i < P.size(); i++)
        {
            //充能
            if (P[i] == 'C')
            {
                power = power * 2;
            }
            //發射
            if (P[i] == 'S')
            {
                sum = sum + power;
            }
        }
        maxIndex = index = P.size() - 1;

        while (true)
        {
            //全部交換完畢
            if (index == 0)
            {
                break;
            }
            //損傷小於D
            if (sum <= D)
            {
                break;
            }
            //交換位置
            if (P[index] == 'S' && P[index - 1] == 'C')
            {
                P[index] = 'C';
                P[index - 1] = 'S';

                sum = sum - power + power / 2;
                index = min(index + 1, maxIndex);

                change++;
                continue;
            }
            //由後往前退
            if (P[index] == 'C')
            {
                power = power / 2;
            }
            index--;
        }

        //印出結果
        if (sum > D)
        {
            printf("Case #%d: IMPOSSIBLE\n", c + 1);
        }
        else
        {
            printf("Case #%d: %d\n", c + 1, change);
        }

        c++;
    }

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

更新:

發現大 CASE 沒過的原因了,index + 1 的位置如果在 C 上,下一次迴圈 power 會被多減半一次。

index = min(index + 1, maxIndex);

修正後的程式碼

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

using namespace std;

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

    while (testcase--)
    {
        int D;
        string P;

        scanf("%d", &D);
        cin >> P;

        int maxIndex = 0; //最大索引
        int index = 0;    //當前索引
        int sum = 0;      //總傷害
        int power = 1;    //能量強度
        int change = 0;   //交換次數

        //先計算總傷害
        for (int i = 0; i < P.size(); i++)
        {
            //充能
            if (P[i] == 'C')
            {
                power = power * 2;
            }
            //發射
            if (P[i] == 'S')
            {
                sum = sum + power;
            }
        }
        maxIndex = index = P.size() - 1;

        while (true)
        {
            //全部交換完畢
            if (index == 0)
            {
                break;
            }
            //損傷小於D
            if (sum <= D)
            {
                break;
            }
            //交換位置
            if (P[index] == 'S' && P[index - 1] == 'C')
            {
                P[index] = 'C';
                P[index - 1] = 'S';

                sum = sum - power + power / 2;

                //如果 index + 1 的位置是 S 可以再交換一次
                if (index + 1 <= maxIndex && P[index + 1] == 'S')
                {
                    index++;
                }

                change++;
                continue;
            }
            //由後往前退
            if (P[index] == 'C')
            {
                power = power / 2;
            }
            index--;
        }

        //印出結果
        if (sum > D)
        {
            printf("Case #%d: IMPOSSIBLE\n", c + 1);
        }
        else
        {
            printf("Case #%d: %d\n", c + 1, change);
        }

        c++;
    }

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

結果

https://ithelp.ithome.com.tw/upload/images/20180716/20106865Rqw4bqKI48.jpg


第二題 Trouble Sort

題意:

這是一個氣泡排序的變形三重氣泡排序,每次會檢查三個數字,如果左邊數字大於右邊,那麼就將左右數字交換,中間的不動。

不過有個問題,例如 897,8和7交換後是 798,但9卡在中間,沒有正確排序,
所以我們要找出排序後第一個未正確排序的數字出現在哪裡。

解法:

這題我很無腦的就用了氣泡排序去解,不過氣泡排序的時間複雜度是 O(n²),所以大 CASE 超時沒有通過。

結果

小 CASE 正確,大 CASE 超時。

程式碼

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

using namespace std;

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

    while (testcase--)
    {
        vector<int> nums;
        int N, T;
        scanf("%d", &N);

        //讀取陣列
        nums.resize(N);
        for (int i = 0; i < N; i++)
        {
            scanf("%d", &T);
            nums[i] = T;
        }

        //排序
        int temp;
        bool isChange;
        while (true)
        {
            isChange = false;

            for (int i = 0; i < N - 2; i++)
            {
                if (nums[i] > nums[i + 2])
                {
                    temp = nums[i];
                    nums[i] = nums[i + 2];
                    nums[i + 2] = temp;

                    isChange = true;
                }
            }

            //排序結束
            if (!isChange)
            {
                break;
            }
        }

        //檢查排序是否成功
        int index;
        bool isOK = true;
        for (int i = 0; i < N - 1; i++)
        {
            if (nums[i] > nums[i + 1])
            {
                isOK = false;
                index = i;
                break;
            }
        }

        //印出結果
        if (isOK)
        {
            printf("Case #%d: OK\n", c + 1);
        }
        else
        {
            printf("Case #%d: %d\n", c + 1, index);
        }

        c++;
    }

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

更新:

要解大 Case 需要將時間複雜度從 O(n²) 降低成 O(nlogn) 才不會超時,觀察三重氣泡排序交換的動作,發現其實就是奇數項和偶數項交替的做氣泡排序,發現這點我就知道可以怎麼解了,首先我將奇數項和偶數項拆開,接著分別用 O(nlogn) 的演算法排序,排序後再穿插檢查其合理性,這樣就能降低時間複雜度了,排序演算法我就偷懶一下直接拿 STL 來用,哈哈哈。

修正後的程式碼

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

using namespace std;

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

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

        vector<int> nums1; //奇數陣列
        vector<int> nums2; //偶數陣列

        //讀取陣列
        nums1.reserve(N / 2);
        nums2.reserve(N / 2);
        for (int i = 0; i < N; i++)
        {
            scanf("%d", &T);
            if (i % 2 == 0)
                nums1.push_back(T);
            else
                nums2.push_back(T);
        }

        //排序
        sort(nums1.begin(), nums1.end());
        sort(nums2.begin(), nums2.end());

        //檢查排序是否成功
        int curr, prev = -1;
        int index = -1;
        for (int i = 0; i < N; i++)
        {
            curr = i % 2 == 0 ? nums1[i / 2] : nums2[i / 2];
            if (prev > curr)
            {
                index = i - 1;
                break;
            }
            prev = curr;
        }

        //印出結果
        if (index == -1)
        {
            printf("Case #%d: OK\n", c + 1);
        }
        else
        {
            printf("Case #%d: %d\n", c + 1, index);
        }

        c++;
    }

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

結果

https://ithelp.ithome.com.tw/upload/images/20180716/201068652t4krCBSGI.jpg


第三題 Go, Gopher!

題意:

我們準備在一個 1000 X 1000 大小的果園內種植一些果樹,再種植之前需要先整理果園,不過對於人類來說這是一項艱苦的工作,所以我們想藉助 Go gopher 來完成,不過 Go gopher 還沒有完善,所以每次只能以給定的座標範圍為中心,在3X3的範圍內隨機整理一塊土地,我們需要想出一個策略,在 Go gopher 挖掘 1000 次之前,完成所有土地的整理。

這題的輸入輸出很特別,是交互式的,我們需要根據 Go gopher 的回應,判斷要輸出的操作,不同於以往的題目。

解法:

這題一開始誤會題目的意思,加上 Debug 要使用 Python 寫的測試工具,所以完全不知道問題在哪,花了好多時間找錯誤的原因,直到比賽剩 1個半小時才意會過來。

這題我的解法好笨,我會根據 Go gopher 給的最大座標和最小座標,畫出一個矩形範圍,如果該矩形面積沒超過題目給的大小,就輸出矩形範圍內還沒有整理的位置,如果超過了,那我會將範圍內縮1格,防止 Go gopher 擴大我畫的矩形範圍,直到所有土地都整理完畢。

小弟在這邊想問各位大大,這題測試時有沒有下中斷點的辦法,小弟我 Debug 的好痛苦。
/images/emoticon/emoticon70.gif

結果

小 CASE 正確,大 CASE 錯誤。

程式碼

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

using namespace std;

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

    while (testcase--)
    {
        vector<vector<int>> map(1000, vector<int>(1000, 0));

        int a;
        scanf("%d", &a);

        int x = 10;
        int y = 10;

        int min_x = x;
        int min_y = y;
        int max_x = x;
        int max_y = y;

        printf("%d %d\n", x, y);
        fflush(stdout);

        while (true)
        {
            scanf("%d %d", &x, &y);

            if (x == 0 && y == 0)
            {
                break;
            }
            if (x == -1 && y == -1)
            {
                return 0;
            }
            if (x >= 2 && x <= 999 && y >= 2 && y <= 999)
            {
                min_x = min(x, min_x);
                min_y = min(y, min_y);
                max_x = max(x, max_x);
                max_y = max(y, max_y);

                map[x][y] = 1;
            }

            x = 10;
            y = 10;

            bool isFind = false;
            for (int i = min_x; i <= max_x; i++)
            {
                for (int j = min_y; j <= max_y; j++)
                {
                    if (map[i][j] == 0)
                    {
                        x = i;
                        y = j;

                        if ((max_x - min_x + 1) * (max_y - min_y + 1) >= a)
                        {
                            if (i == max_x)
                            {
                                x = (i == max_x && i == min_x) ? i : i - 1;
                            }
                            if (j == max_y)
                            {
                                y = (j == max_y && j == min_y) ? j : j - 1;
                            }
                            if (i == min_x)
                            {
                                x = (i == max_x && i == min_x) ? i : i + 1;
                            }
                            if (j == min_y)
                            {
                                y = (j == max_y && j == min_y) ? j : j + 1;
                            }
                        }
                        isFind = true;
                        break;
                    }
                }
                if (isFind)
                {
                    break;
                }
            }

            printf("%d %d\n", x, y);
            fflush(stdout);

            /*for (int i = min_x; i <= max_x; i++)
            {
                for (int j = min_y; j <= max_y; j++)
                {
                    printf("%d ", map[i][j]);
                }
                printf("\n");
            }*/
        }

        c++;
    }

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

更新:

看了官方的分析,發現我的作法會導致 Go gopher 給出過多重複的座標,因此無法在 1000 次內整理完果園。

優化的方式可以將果園分成 n 個 3X3 不相交的區塊,每次只給 Go gopher 該區塊的中心座標,該區塊完成後再繼續下一個區塊,這樣就能降低給出重複座標的機會。

上傳過程有兩次失誤,這題比較難 Debug 上傳後才發現有錯,重寫的程式碼也比較好閱讀,之前硬擠出來的程式現在自己也看不太懂,哈哈哈。

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

using namespace std;

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

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

        int record[3][3] = {0}; //記錄3X3區塊完成的部分
        int count = 9;          //剩餘的數量
        int num = 1;            //區塊編號

        int x, y;               //GoGopher回傳的座標
        int centet_x, centet_y; //3X3區塊中心座標

        //隨便選一個座標開始
        centet_x = centet_y = 6;

        while (true)
        {
            //該3X3區塊已整理完
            if (count == 0)
            {
                centet_y += 3;
                count = 9;
                num++;
                continue;
            }

            printf("%d %d\n", centet_x, centet_y);
            fflush(stdout);

            scanf("%d %d", &x, &y);

            //程式失敗
            if (x == -1 && y == -1)
            {
                return 0;
            }
            //完成果園整理
            if (x == 0 && y == 0)
            {
                break;
            }
            //x,y超出範圍
            if (x < 2 || x > 999 || y < 2 || y > 999)
            {
                continue;
            }
            //紀錄完成的部分,以區塊編號當標記
            if (record[x - centet_x + 1][y - centet_y + 1] != num)
            {
                record[x - centet_x + 1][y - centet_y + 1] = num;
                count--;
            }
        }

        c++;
    }

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

結果

https://ithelp.ithome.com.tw/upload/images/20180716/20106865oUBoy366Ns.jpg


第四題 Cubic UFO

結果

這題是數學題,我沒有做 XD。
以後真的要多練習數學題...


心得

比賽禮拜六開始,不過我早上都在寫 這篇,寫完已經晚上了,然後吃飽飯後太累不小心睡著,半夜 1點才驚醒,趕快開始寫題目,一直寫到早上,通霄寫程式感覺真的不錯,果然半夜是工程師精神最好的時候。

本來還想大 CASE 只要對一題就可以進入下一關,沒想到全部都失敗,太悲慘了。

https://ithelp.ithome.com.tw/upload/images/20180409/20106865vvU7jNi7x5.jpg


2 則留言

0
神Q超人
iT邦新手 1 級 ‧ 2018-04-09 01:40:25

好有毅力ㄛ,我就熬不了夜,可能越來越不適合當工程師了/images/emoticon/emoticon46.gif
明天找時間也來挑戰看看這幾題!!

fysh711426 iT邦研究生 2 級‧ 2018-04-10 00:01:34 檢舉

熬夜隔天就感冒了 /images/emoticon/emoticon28.gif

等你做完後的心得分享!!

0
海綿寶寶
iT邦大神 1 級 ‧ 2018-04-09 17:43:39

虧我還提前惡補了一些 DP 的部落格
這次我連一題都沒對
真是/images/emoticon/emoticon52.gif/images/emoticon/emoticon52.gif/images/emoticon/emoticon52.gif

fysh711426 iT邦研究生 2 級‧ 2018-04-10 00:07:23 檢舉

哈哈哈,雖然結果不盡理想,
不過題目蠻有趣的,很享受解題的過程,
很可惜大CASE不能驗證,不然可以慢慢試為什麼錯誤,
明年在和大大一起參加
/images/emoticon/emoticon37.gif

是呀
以前是採取「參加者自行下載測試資料(大小case)」
雖然每次下載的測試資料都不一樣
但是至少還有資料可以看/debug

這次的做法
就是對程式設計者更高的要求
在設計程式時就要bug-free
而不是try error再來修

事實證明
我就是那種try error型的人
/images/emoticon/emoticon05.gif

fysh711426 iT邦研究生 2 級‧ 2018-04-12 21:36:09 檢舉

我也是,我這方面經驗比較少,需要從錯誤中修正程式,
bug-free 真的很厲害。

以後要多練習數學題,寫網頁用到數學的地方少,
都把數學還給老師了。
/images/emoticon/emoticon25.gif

我要留言

立即登入留言