今年的成績比去年進步，終於通過了資格賽，這次有找朋友一起參加，賽後一起討論題目怎麼解還蠻有趣的，明年繼續努力。
題意:
有人贏得 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;
}
題意:
有一個 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;
}
題意:
這題需要對密文進行解密，加密規則如下:
例如，假設 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 這種情況，相鄰的兩個密文會有相同的值，不過題目有提到明文最少會使用每個字母一次，所以不用擔心可以先跳過相同的值，回頭再來看。
整理後的邏輯是:
這題有兩個 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;
}
題意:
研究聯盟建立了一個新的資料庫系統，由一台計算機和 N 台工作機組成，工作機的 ID 為 0 到 N-1，計算機主機每次可以發送 N 個字元，並將第 i 位的字元發送給第 i 個工作機。
正常操作期間，工作機讀取字元後會回傳相同的字元給計算機主機，但有個不好的消息，有 B 台工作機壞掉了，壞掉的工作機不會回傳任何字元，因此每次發送字元，只會接收到回傳的 N - B 個字元，這些字元會按照工作機的 ID 排列。
假設 N = 5 並且第 0 和第 3 個工作機壞掉了。
請找出壞掉工作機的 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;
}
解法:
這題沒有想到什麼好的解法，只好把所有結果跑一次，只通過第一個 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 的方式，感覺蠻複雜的，時間不夠所以就先放棄。
今年我也是第一次參加GCJ 死在了Round2可怕的數值模擬跟SCC... (t-shirt bye)
有群組賽後討論蠻有趣的 如果還有想接著討論 Round3 and final求++ XD
大大太強了!!
數值模擬和SCC是哪一題呢?
數值模擬是第二題花瓶作弊90%win rate
SCC是第四題鍊金問題
我剛發現我就是去年看到你介紹2018GCJ的文章今年才參加的哈哈
這兩題好難。 
第一題用int跑Case3會爆掉，可以用字串跑
#include<iostream>
#include <string.h>
using namespace std;
int main()
{
int amount = 0;
char string[200];
char s1[200][200] = { 0 }, s2[200][200] = { 0 };
cin >> amount;
for (int i = 0; i < amount; i++)
{
cin >> string;
for(int j= 0;j<strlen(string);j++)
{
if (string[j] == '0')
{
s1[i][j] += '0';
s2[i][j] += '0';
}
else if (string[j] == '1')
{
s1[i][j] += '0';
s2[i][j] += '1';
}
else if (string[j] == '2')
{
s1[i][j] += '1';
s2[i][j] += '1';
}
else if (string[j] == '3')
{
s1[i][j] += '2';
s2[i][j] += '1';
}
else if (string[j] == '4')
{
s1[i][j] += '2';
s2[i][j] += '2';
}
else if (string[j] == '5')
{
s1[i][j] += '2';
s2[i][j] += '3';
}
else if (string[j] == '6')
{
s1[i][j] += '3';
s2[i][j] += '3';
}
else if (string[j] == '7')
{
s1[i][j] += '2';
s2[i][j] += '5';
}
else if (string[j] == '8')
{
s1[i][j] += '3';
s2[i][j] += '5';
}
else if (string[j] == '9')
{
s1[i][j] += '3';
s2[i][j] += '6';
}
}
}
for (int i = 0; i < amount; i++)
{
cout << "Case #" << i+1 << ": " << s1[i] << " " << s2[i] << endl;
}
return 0;
}
這題用字串是正解。 
iThome鐵人賽
看影片追技術