1859 . Ch1-7.練習
TopCoder
Tags
Description
※本題為互動題，請在程式碼中引入標頭檔：
#include "lib1859.h"
經過了幾天的摔角訓練，你實力大增，而且還學會了新技能「小志❤の電波」。
「為什麼中間有個❤」你深感不解。
「哼哼!小子你進步很快嘛。」比利說到
「不過你如果要能在ZZ(Zombie Zone)下生存，你一定要能快速的解決大批殭屍，我們來練習一下吧。」
於是你又得跟比利比賽了，這次的比賽是比誰擊殺的殭屍比較多。
比賽是這樣的，在N行N列的方格上，由左到右分別為第1,2,...,N行，由上到下分別為第1,2,...,N列，而每一格都有一個數字Aij代表第i列第j行這一個格子上的殭屍的數目。
而這些殭屍只要被同一種電波打到2次就會死亡，比如如果一個殭屍被兩次「小志❤の電波」打到，不管之間間隔多久都會死亡。
但是如果被「小志❤の電波」打到，再被「比利電波」打到，並不會死亡。
第一回合由你先使用「小志❤の電波」，你可以決定一個x1值，然後你便會向第x1行發射電波，所有在第x1行上面的殭屍都會被電波打到一下，第x1列也發射電波，所有在第x1列上面的殭屍也都會被電波打到一下，而你可以知道第x1行第x1列上的殭屍就會被你打到兩下。
第二回合由比利先使用「比利電波」，他可以決定一個x2值，注意到不能挑選已經被某個人挑過的數字，然後他便會向第x2行還有第x2列發射電波，所有在某個電波的發射路徑上的殭屍都會被那個電波打到一次。
然後第三回合由你決定一個x3值使用「小志❤の電波」，注意到不能挑選已經被某個人挑過的數字。
然後第四回合由比利決定一個x4值...這樣一直輪流下去
因為不能挑已經有人選過的數字，即x1≠x2≠...≠xn 可以知道在第N輪後，遊戲就結束了。
「不知道如果輸了會怎樣，啊~好銷魂啊❤...」你這樣想
「不行!要振作點!這次一定要贏!!」
為了證明自己的進步!你希望你可以贏越多越好!
Input Format
請不要執行任何輸入輸出，否則很有可能會讓你的執行結果為Wrong Answer。
請先引入"lib1859.h"
然後會有以下函示
void Billy_Starts_The_Game()
比利開始遊戲，請先呼叫這個函式才能呼叫以下函式
int Billy_Tells_You_N()
回傳N值
int Billy_Tells_You_Aij(int i,int j)
回傳Aij值，即第i行第j列上有多少殭屍。
int You_Choose(int x)
你選了x，會回傳比利下一回合選了哪個數字。
如果遊戲結束了會自動結束程式。
Output Format
假設你擊殺了X之殭屍，比利擊殺了Y隻殭屍，只要X−Y≥K即可，其中K為在比利使用最佳的策略下，你擊殺的殭屍數最多可以贏他多少隻。
Sample Input 1
| 呼叫函數和引數 | 回傳值 | 說明 |
| Billy_Starts_The_Game() | - | 在任何操作之前都必須呼叫此函式 |
| Billy_Tells_You_N() | 3 | 代表此測資中N=3 |
| Billy_Tells_You_Aij(1,1) | 4 | 代表A[1][1]=4 |
| Billy_Tells_You_Aij(1,2) | 2 | 代表A[1][2]=2 |
| Billy_Tells_You_Aij(1,3) | 1 | 代表A[1][3]=1 |
| Billy_Tells_You_Aij(2,1) | 3 | 代表A[2][1]=3 |
| Billy_Tells_You_Aij(2,2) | 1 | 代表A[2][2]=1 |
| Billy_Tells_You_Aij(2,3) | 2 | 代表A[2][3]=2 |
| Billy_Tells_You_Aij(3,1) | 5 | 代表A[3][1]=5 |
| Billy_Tells_You_Aij(3,2) | 3 | 代表A[3][2]=3 |
| Billy_Tells_You_Aij(3,3) | 1 | 代表A[3][3]=1 |
| You_Choose(2) | 1 | 代表你選完2後比利選了1 |
| You_Choose(3) | - | 代表你選完3後遊戲結束 |
Sample Output 1
你的成績(紅)=1+2+3+1=7
比利的成績(藍)=4
你贏了他7−4=3隻
注意到這可能不是最佳解。
Hints
對於所有測資 : A_ij ≤1000
測資組A : N≤8
測資組B : N≤20
測資組C : N≤100
測資組D : N≤1000
Problem Source
Step5
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0~14 | 10 |
| 2 | 15~19 | 20 |
| 3 | 20~29 | 50 |
| 4 | 30~39 | 20 |