有一種(或許在墨西哥)很流行的個人遊戲叫做點連接遊戲
這個遊戲是一種獨人遊戲。就是一個盤上有g顆綠色棋子、r顆紅色棋子。
保證:
你有兩種顏色的線可以用,綠線只能連接兩個綠點、紅線只能連接兩個紅點。
遊戲目標是希望你寫個程式用(g-1)條綠線讓所有綠點連通、用(r-1)條紅線讓所有紅點連通。
但任兩條線不能交叉。
例如,下圖就是一個完成的畫面:
本題為互動題,請引入#include "lib1631.h"並撰寫一個程式來完成他。
以下為可使用的函式:(注意:在這個互動題中 0代表綠色 1代表紅色)
void Init(int &gCnt, int &rCnt); 在作任何操作前請先呼叫此函式,gCnt為綠棋子個數、rCnt為紅棋子個數。
void Get(int color, int &x, int &y); color=0代表綠色、color=1代表紅色。
例如,第i次呼叫Get(0, x, y)會得到綠色棋子第i顆的x座標及y座標。超過該顏色棋子顆數的呼叫會得到一個WA
void Report(int color, int n1, int n2); 回報答案,表示你要把color顏色 編號n1和n2的兩個點連起來。
例如,Report(1, 1, 2)就是把紅色1跟紅色2連起來。
void Finish(void);表示結束回報線段,並開始檢測程式是否正確。之後會自動幫你結束程式。
一些保證:
3 <= g,r <= 50,000
0 < s <= 200,000,000
本題無須讀入,任何讀入動作會得到一個WA。
本題無須輸出,請Report()答案後Finish()。
1.一個保證不會AC的程式:
#include <cstdio>
#include "lib1631.h"
int pos[2][50001][2];
int cnt[2];
int main(){
Init(cnt[0], cnt[1]);
for(int i=0; i<=1; i++)
for(int j=1; j<=cnt[i]; j++)
Get(i, pos[i][j][0], pos[i][j][1]);
for(int i=0; i<=1; i++)
for(int j=1; j<cnt[i]; j++)
Report(i, j, j+1);
Finish();
}
還有,這題的judge程式速度非常慢,但是時間絕對夠正解在沒有特別設計過的測資上。
原TIOJ1631 / IOI '06 Joining Points
Problem Setter:ATP
No. | Testdata Range | Score |
---|---|---|
1 | 0 | 16 |
2 | 1 | 16 |
3 | 2 | 16 |
4 | 3 | 16 |
5 | 4 | 16 |
6 | 5 | 20 |