天使問題
天使問題敘述的是一個天使要在座標格上逃離惡魔的魔掌， 天使和惡魔輪流進行一次動作。
在每個惡魔的回合惡魔可以放下一個障礙物， 在每個天使的回合天使能移動到上下左右其中一個位置， 當天使的上下左右都被包圍時，天使就輸了。 可以證明天使沒有辦法成功逃出。
現在你要玩這個遊戲，讓惡魔愈快抓住天使愈好，讓天使逃愈久愈好。
在這裡我們約定範圍是\([1,19]*[1,19]\)的格子，雙方都不可以出界，並且天使先動且初始位置為\((10,10)\)。
Input & Output
第一行是一個正整數\(T\)，代表要進行的回合數 第二行是一個正整數\(f\)，如果\(f=0\)代表你是惡魔，如果\(f=1\)代表你是天使。
在遊戲中，當輪到電腦的回合時讀入兩個正整數\(x,y\)，表示電腦設置障礙物或移動到的座標
輪到你的回合時輸出兩個正整數\(x,y\)，表示你設置障礙物或移動到的座標
當你沒辦法再移動時，輸出\(0\) \(0\)認輸即可進行下回合。同理，當讀到\(0\) \(0\)時表示電腦認輸，也是開始新的回合。
如果你讀到\(-1 -1\)，代表你違反規則了，這回合結束並且你在這回合0分。
如果在任一回合中你的輸出不合法可能會導致整題0分。
Constraints
第 \(1\) 組測資, \(T=20, f=0\)。
第 \(2\) 組測資, \(T=20, f=1\)。
Grading
當天使和惡魔各\(100\)分。
分別對於天使和惡魔，我們會決定兩個常數\(C_{20},C_{100}\)
當你是惡魔時， \(C_{20}=180, C_{100}=50\)；當你是天使時，\(C_{20}=3, C_{100}=12\)。
如果你的次數等於\(C_{100}\)或更優，會得到\(100\)分；如果你的次數等於\(C_{20}\)，會得到\(20\)分；如果你的次數比\(C_{20}\)差，會得到\(0\)分。
次數介在\(C_{20},C_{100}\)之間的給分是線性函數，也就是說如果你的次數\(x\)介在這之間，你會得到\(\frac{x-C_{20}}{C_{100}-C_{20}}\)分。
你的總分是所有回合得分的平均，分別在兩個測資點得到\(20\)分以上就能得到\(AC\)，但你還是可以繼續爭取更高的分數。
再次說明，當任一回合中輸出的不是兩個\(0\)～\(19\)的整數，會導致整題\(0\)分。
Sample Code
#include<iostream>
using namespace std;
int main()
{
int T, f;
cin >> T >> f;
for(int testcase = 0; testcase < T; testcase++)
{
if(f == 0)//你是惡魔
{
int blocked[20][20];//紀錄哪些格子被設置過障礙物
//一開始都沒被放過障礙物
for(int i = 1; i <= 19; i++)
{
for(int j = 1; j <= 19; j++)
{
blocked[i][j] = 0;
}
}
while(true)//直到遊戲結束
{
int x,y;
cin >> x >> y;//天使先動
if((x == 0 && y == 0) || (x == -1 && y == -1)) break;//違規或天使認輸後回合結束
int found = 0;//一開始還沒找到選點
for(int i = 1; i <= 19; i++)
{
if(found) break;//找到選點後離開
for(int j = 1; j <= 19; j++)
{
//找一個還沒設置過障礙物，也不是天使所在位置的點設置障礙物
if(!blocked[i][j] && (x != i || y != j))
{
cout << i << " " << j << endl;//將障礙物輸出給電腦
blocked[i][j] = 1;//紀錄放過障礙物
found = 1;
break;//找到選點後離開
}
}
}
}
}
if(f == 1)//你是天使
{
while(true)
{
cout << 10 << " " << 11 <<endl;//向上前進
int x,y;
cin >> x >> y;//電腦的動作
if(x == -1 && y == -1) break;//如果違規就結束
//如果電腦佔據了中心點或上方，直接投降結束回合，注意到你隨時可以投降而不一定要等到結束
if((x == 10 && y == 10) || (x == 10 && y == 11))
{
cout << 0 << " " << 0 <<endl;
break;
}
cout << 10 << " " << 10 << endl;//回到中心
cin >> x >> y;//再次輪到電腦
//如果電腦佔據了中心點或上方，直接投降結束回合
if((x == 10 && y == 10) || (x == 10 && y == 11))
{
cout << 0 << " " << 0 <<endl;
break;
}
}
}
}
return 0;
}
PS: 每次輸出的時候，必須清除緩衝區(std::cout << std::endl;或std::cout << std::flush;)，否則會產生錯誤。
PS2: 我們充分理解基於隨機的演算法(電腦策略也包含隨機)會導致傳多次同樣的程式碼可能會得到不同的分數，但還是請不要spam這個評測系統QAQ
一般來說，我們期望的自主限制是在兩分鐘內不提交多於一個submission, 相近的程式碼不提交超過5次。
评论