5

## [Google Code Jam] 2018 資格賽

### 第一題 Saving The Universe Again

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

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

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

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

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

### 第二題 Trouble Sort

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

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

### 第三題 Go, Gopher!

`小弟在這邊想問各位大大，這題測試時有沒有下中斷點的辦法，小弟我 Debug 的好痛苦。`

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

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

### 2 則留言

0

iT邦新手 1 級 ‧ 2018-04-09 01:40:25

0

iT邦大神 1 級 ‧ 2018-04-09 17:43:39

bug-free 真的很厲害。