感謝 海綿寶寶 的邀請，今年參加了 Google Code Jam 2018 的比賽，雖然很可惜，連資格賽都沒有過，不過題目真的蠻有趣的，明年再接再厲。
題意:
有一個外星機器人正在攻擊宇宙，機器人攻擊強度初始為1，機器人會有兩種操作如下:
C 充電，會使攻擊光束強度加倍S 攻擊，射擊光束，造成當前光束強度的傷害以 SCCSSC 舉例
科學家發明了一種可以承受 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;
}
結果
題意:
這是一個氣泡排序的變形三重氣泡排序，每次會檢查三個數字，如果左邊數字大於右邊，那麼就將左右數字交換，中間的不動。
不過有個問題，例如 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;
}
結果
題意:
我們準備在一個 1000 X 1000 大小的果園內種植一些果樹，再種植之前需要先整理果園，不過對於人類來說這是一項艱苦的工作，所以我們想藉助 Go gopher 來完成，不過 Go gopher 還沒有完善，所以每次只能以給定的座標範圍為中心，在3X3的範圍內隨機整理一塊土地，我們需要想出一個策略，在 Go gopher 挖掘 1000 次之前，完成所有土地的整理。
這題的輸入輸出很特別，是交互式的，我們需要根據 Go gopher 的回應，判斷要輸出的操作，不同於以往的題目。
解法:
這題一開始誤會題目的意思，加上 Debug 要使用 Python 寫的測試工具，所以完全不知道問題在哪，花了好多時間找錯誤的原因，直到比賽剩 1個半小時才意會過來。
這題我的解法好笨，我會根據 Go gopher 給的最大座標和最小座標，畫出一個矩形範圍，如果該矩形面積沒超過題目給的大小，就輸出矩形範圍內還沒有整理的位置，如果超過了，那我會將範圍內縮1格，防止 Go gopher 擴大我畫的矩形範圍，直到所有土地都整理完畢。
小弟在這邊想問各位大大，這題測試時有沒有下中斷點的辦法，小弟我 Debug 的好痛苦。
結果
小 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;
}
結果
結果
這題是數學題，我沒有做 XD。
以後真的要多練習數學題...
比賽禮拜六開始，不過我早上都在寫 這篇，寫完已經晚上了，然後吃飽飯後太累不小心睡著，半夜 1點才驚醒，趕快開始寫題目，一直寫到早上，通霄寫程式感覺真的不錯，果然半夜是工程師精神最好的時候。
本來還想大 CASE 只要對一題就可以進入下一關，沒想到全部都失敗，太悲慘了。
好有毅力ㄛ，我就熬不了夜，可能越來越不適合當工程師了
明天找時間也來挑戰看看這幾題!!
熬夜隔天就感冒了 
等你做完後的心得分享!!
虧我還提前惡補了一些 DP 的部落格
這次我連一題都沒對
真是
哈哈哈，雖然結果不盡理想，
不過題目蠻有趣的，很享受解題的過程，
很可惜大CASE不能驗證，不然可以慢慢試為什麼錯誤，
明年在和大大一起參加
是呀
以前是採取「參加者自行下載測試資料(大小case)」
雖然每次下載的測試資料都不一樣
但是至少還有資料可以看/debug
這次的做法
就是對程式設計者更高的要求
在設計程式時就要bug-free
而不是try error再來修
事實證明
我就是那種try error型的人
我也是，我這方面經驗比較少，需要從錯誤中修正程式，
bug-free 真的很厲害。
以後要多練習數學題，寫網頁用到數學的地方少，
都把數學還給老師了。
iThome鐵人賽
看影片追技術