天使問題

View as PDF

Submit solution

Points: 200
Time limit: 2.0s
Memory limit: 64M

Author:
Problem type

天使問題敘述的是一個天使要在座標格上逃離惡魔的魔掌, 天使和惡魔輪流進行一次動作。

在每個惡魔的回合惡魔可以放下一個障礙物, 在每個天使的回合天使能移動到上下左右其中一個位置, 當天使的上下左右都被包圍時,天使就輸了。 可以證明天使沒有辦法成功逃出。

現在你要玩這個遊戲,讓惡魔愈快抓住天使愈好,讓天使逃愈久愈好。

在這裡我們約定範圍是\([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次。


Comments

There are no comments at the moment.