TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

100.0% (3/3)

Submission's AC Ratio

100.0% (3/3)

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

呼叫函數和引數回傳值說明
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+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

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 1
2 1000 65536 262144 1
3 1000 65536 262144 1
4 1000 65536 262144 1
5 1000 65536 262144 1
6 1000 65536 262144 1
7 1000 65536 262144 1
8 1000 65536 262144 1
9 1000 65536 262144 1
10 1000 65536 262144 1
11 1000 65536 262144 1
12 1000 65536 262144 1
13 1000 65536 262144 1
14 1000 65536 262144 1
15 1000 65536 262144 2
16 1000 65536 262144 2
17 1000 65536 262144 2
18 1000 65536 262144 2
19 1000 65536 262144 2
20 1000 65536 262144 3
21 1000 65536 262144 3
22 1000 65536 262144 3
23 1000 65536 262144 3
24 1000 65536 262144 3
25 1000 65536 262144 3
26 1000 65536 262144 3
27 1000 65536 262144 3
28 1000 65536 262144 3
29 1000 65536 262144 3
30 1000 65536 262144 4
31 1000 65536 262144 4
32 1000 65536 262144 4
33 1000 65536 262144 4
34 1000 65536 262144 4
35 1000 65536 262144 4
36 1000 65536 262144 4
37 1000 65536 262144 4
38 1000 65536 262144 4
39 1000 65536 262144 4