2197 . E. 密室逃脫
TopCoder
Tags
Description
密室逃脫一般泛指一種特定的遊戲類型。在該類遊戲中，玩家通常被限定在一個近乎完全封閉或者對自身存在威脅的環境內，以第一視角探索週遭環境，不斷地尋找並利用身邊的物品做為工具，完成指定任務，並以最終逃離該區域為目的。這些指定的任務，常常是以解開特定謎題的方式呈現。
在實景遊戲的範疇裡，密室逃脫一般指一種單人或多人在特定場所裡進行的娛樂活動。參與這項活動的玩家，一般會被置身於在一個特定的場所，通過裝修與設計，營造逼真的場景，而後賦予玩家不同的身份、任務、及故事劇情，要求玩家在規定的時間內，通過尋找線索、團隊合作、層層解謎，最終完成任務脫離密室，整個過程一般進行 $60$ 至 $120$ 分鐘。因為該類遊戲是基於電子遊戲裡的密室逃脫的基礎發展而成，故又被稱為真人密室逃脫。（節錄自《維基百科》）
近年來，越來越多實境密室逃脫工作室成立，遊戲設計的難度也越來越高。而任務的設計必須不斷地推陳出新，否則在這個資訊科技發達的時代，任務關卡的破解方式很快就能在網路上找到。踢歐埃工作室是一間以太空探險為主題的實境密室逃脫工作室；他們打算設計一道會隨著參與人數的多寡而改變答案的遊戲關卡，其任務規則設計如下：
- 依照參與人數 $n$ 給予一個 $n \times n$ 的棋盤方格，其中每個格子都被填入一個非負整數。
- 用座標 $(i, j)$ 來表示第 $i$ 列第 $j$ 行的格子，在關卡劇情中為一塊空域，飛空艇可以穿梭其中。
- 令格子 $(i, j)$ 被填入的非負整數為 $a_{i,j}$，代表 $(i, j)$ 空域有質量為 $a_{i,j}$ 的小行星，影響飛航安全。
- 玩家們有一座高能雷射武器，每次發射可以把一列或一行的所有小行星的質量都減去 $1$；一顆小行星唯有在質量降為 $0$ 時才算被清除，而此時即便再被發射也不會減少質量（亦即質量不會變成負數）。
- 由於這座高能雷射武器的耗能巨大，玩家們必須在發射總次數最低的情況下把棋盤上的所有小行星清除乾淨才算通關。
請你幫忙踢歐埃工作室設計一個程式，針對一給定的棋盤，給出一個發射總次數最低的策略。
Input Format
$n$
$a_{1,1}\ a_{1,2}\ \dots\ a_{1,n}$
$a_{2,1}\ a_{2,2}\ \dots\ a_{2,n}$
$\vdots$
$a_{n,1}\ a_{n,2}\ \dots\ a_{n,n}$
- $n$ 代表玩家數，亦即棋盤的列數與行數。
- $a_{i,j}$ 代表 $(i,j)$ 空域的小行星質量。
Output Format
$m$
$r_1\ r_2\ \dots\ r_n$
$c_1\ c_2\ \dots\ c_n$
- $m$ 為一整數代表清除所有小行星的最低發射次數
$\{r_i\}^ n_{i=1}$ 與 $\{c_i\}^ n_{i=1}$ 為任意一個發射總次數最低的策略，其中
- $r_i$ 為一非負整數，代表朝著第 $i$ 列發射的次數。
- $c_i$ 為一非負整數，代表朝著第 $i$ 行發射的次數。
- 輸出的 $r_i, c_i$ 必須為 $0$ 到 $2\times 10^ 6$ 之間的非負整數
- 若輸出的 $m$ 為正確的最小次數但發射方案錯誤仍可得到部分分數，得分算法請參照下方評分說明一節。
Sample Input 1
3 1 0 1 0 1 0 0 1 0
Sample Output 1
2 1 0 0 0 1 0
Sample Input 2
4 8 5 37 3 4 4 46 4 77 12 23 82 100 59 81 98
Sample Output 2
233 3 12 79 95 5 2 34 3
Sample Input 3
10 65 93 72 20 76 24 52 27 74 88 28 80 11 1 29 30 7 14 39 55 88 71 62 51 41 65 62 66 53 4 60 49 11 71 21 78 24 31 10 87 61 38 2 6 64 43 25 14 95 64 54 80 97 64 56 70 73 27 84 52 74 8 78 98 6 56 71 91 17 86 80 80 85 80 21 57 88 68 66 28 36 31 15 88 87 100 99 73 42 4 94 7 39 56 75 1 79 76 81 11
Sample Output 3
885 46 33 40 45 60 67 68 55 67 46 48 47 30 30 30 33 33 30 35 42
Hints
測資限制
- $1\leq n\leq 500$。
- $0\leq a_{i,j}\leq 2\times 10^ 6$。（$i,j\in\{1,2,\dots,n\}$）
- 輸入的數均為整數。
評分說明
本題共有四組子任務，條件限制如下所示。
- (20%) $n\leq 20$，且 $a_{i,j}\in\{0,1\}$。
- (40%) $n\leq 70$，且 $a_{i,j}\in\{0,1\}$。
- (35%) $n\leq 70$。
- (5%) 無額外限制。
每一子任務可有一或多筆測試資料。在一子任務中，若所有測試資料的輸出均滿足以下條件，即可獲得滿分：
- 最小總發射次數 $m$ 正確。
- 發射策略 $\{r_i\}^ n_{i=1}$ 與 $\{c_i\}^ n_{i=1}$ 滿足題目要求。
若子任務中有任一筆測試資料的輸出滿足以下任一條件，將收到 Wrong Answer 且無法在此子任務中獲得任何分數：
- 只輸出一行 $m$ 但沒有輸出 $r_i, c_i$。
- 其它輸出格式錯誤，例如 $r_i, c_i$ 不是介於 $0$ 到 $2 \times 10^ 6$ 之間的情形。
- 最小總發射次數 $m$ 錯誤。
若子任務中所有測試資料的輸出，格式與最小總發射次數 $m$ 皆正確，但發射策略不符合題目要求 （$\{r_i\}^ n_{i=1}$ 與 $\{c_i\}^ n_{i=1}$ 總和與 $m$ 不相等也可以），可在此子任務中獲得 40% 的分數。也就是說如果只會計算總和但不會計算解的方案時在 $m$ 後面輸出兩行 $n$ 個 $0$：
$m$
$0\ 0\ \dots\ 0$
$0\ 0\ \dots\ 0$
可以得到該子任務 40% 的分數。
Problem Source
2021 TOI 入營考 pE
testdata set by Omelet
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~4 | $n\leq 20$，且$a_i\in\{0,1\}$ | 8 |
| 2 | 0~9 | $n\leq 20$，且$a_i\in\{0,1\}$（需輸出$r_i,c_i$） | 12 |
| 3 | 0~4, 10~14 | $n\leq 70$，且$a_i\in\{0,1\}$ | 16 |
| 4 | 0~19 | $n\leq 70$，且$a_i\in\{0,1\}$（需輸出$r_i,c_i$） | 24 |
| 5 | 0~4, 10~14, 20~29 | $n\leq 70$ | 14 |
| 6 | 0~39 | $n\leq 70$（需輸出$r_i,c_i$） | 21 |
| 7 | 0~4, 10~14, 20~29, 40~54 | 無額外限制 | 2 |
| 8 | 0~69 | 無額外限制（需輸出$r_i,c_i$） | 3 |