AT_ahc035_a [AHC035A] Breed Improvement
题目描述
有一个用 $N\times N$ 格子表示的农田。农田最左上角的格子的坐标为 $(0,0)$，从该格子向下移动 $i$ 格、向右移动 $j$ 格后的位置为 $(i,j)$。
给定 $2N(N-1)$ 粒谷物种子。存在 $M$ 个评价项目，每粒种子 $k$ 都有一个表示各评价项目优劣的非负整数向量 $\boldsymbol{x_k}=(x_{k,0},\ x_{k,1},\ \cdots,\ x_{k,M-1})$（下称“评价项目向量”）。种子 $k$ 的价值 $V_k$ 定义为 $V_k=\sum_{l=0}^{M-1}x_{k,l}$。
通过以下操作重复 $T$ 次，使手中种子的最大价值 $\max(V_0,\ V_1,\ \cdots,\ V_{2N(N-1)-1})$ 尽可能大。
- 在农田的 $N^2$ 个格子中，每个格子各种下一粒种子。同一粒种子不能种在多个格子，未被种下的 $2N(N-1)-N^2$ 粒种子全部丢弃。之后，对于上下左右相邻的格子中所种的种子对 $(k,\ k')$，会生成一粒新的种子，其评价项目向量的第 $l$ 个元素值会从原种子的 $x_{k,l}$ 和 $x_{k',l}$ 中等概率随机选取。这样共生成 $2N(N-1)$ 粒新种子，作为新的手中种子。
新种子的生成示例
例如，当 $M=3$ 时，将种子 $0$ 种在格子 $(0,0)$，种子 $1$ 种在格子 $(0,1)$。若种子 $0$ 的评价项目向量为 $\boldsymbol{x_0}=(1,2,3)$，种子 $1$ 的评价项目向量为 $\boldsymbol{x_1}=(4,5,6)$，则新种子的评价项目向量可能为以下 $8$ 种之一：
- $(1,2,3)$
- $(1,2,6)$
- $(1,5,3)$
- $(1,5,6)$
- $(4,2,3)$
- $(4,2,6)$
- $(4,5,3)$
- $(4,5,6)$
从这 $8$ 个评价项目向量中等概率随机选取 $1$ 个，作为新种子的评价项目向量。
输入格式
**※本题为交互式题目。请阅读以下内容，并与评测程序进行交互。**
首先，从标准输入读入农田大小 $N$、评价项目数 $M$、操作次数 $T$，以及所有种子的评价项目向量 $\boldsymbol{x_k}=(x_{k,0},\ x_{k,1},\ \cdots,\ x_{k,M-1})$，格式如下：
> $N$ $M$ $T$
> $x_{0,0}$ $\cdots$ $x_{0,M-1}$
> $\vdots$
> $x_{2N(N-1)-1,0}$ $\cdots$ $x_{2N(N-1)-1,M-1}$
其中，输入满足以下约束：
- $N=6$
- $M=15$
- $T=10$
- $0\le x_{k,l}\le 100$
- 所有输入均为整数
读取上述信息后，重复以下处理 $T$ 轮：
每一轮，首先将每个格子种植的种子编号按如下格式输出到标准输出：
> $A_{0,0}$ $\cdots$ $A_{0,N-1}$
> $\vdots$
> $A_{N-1,0}$ $\cdots$ $A_{N-1,N-1}$
其中，$A_{i,j}$ 表示种在格子 $(i,j)$ 的种子编号，需满足 $0\le A_{i,j} $x_{0,0}$ $\cdots$ $x_{0,M-1}$
> $\vdots$
> $x_{2N(N-1)-1,0}$ $\cdots$ $x_{2N(N-1)-1,M-1}$
其中，每个元素均为 $0\le x_{k,l}\le 100$ 的整数。
**每次输出后必须换行，并且刷新标准输出。** 否则可能会导致 TLE。
解答程序可以在输出中包含以 `#` 开头的注释行。使用网页版可视化工具时，这些注释会在相应时机显示，便于调试和分析。评测程序会忽略所有注释行，因此可以直接提交包含注释的程序。
输出格式
见上文“输入格式”部分的说明。
说明/提示
### 故事背景
AtCoder 公司正在致力于谷物品种改良。谷物有美味、产量、抗病性等多个评价项目，社长高桥希望培育出在所有评价项目上都很优秀的谷物。
在格状农田中种植谷物种子后，相邻格子的两粒种子会随机继承各自的评价项目值，生成新的种子。通过多次种植和收获，希望你能培育出尽可能优秀的谷物种子。
### 得分
对于初始给定的 $2N(N-1)$ 粒种子，评价项目向量第 $l$ 项的最大值为 $X_l=\max(x_{0,l},\ x_{1,l},\ \cdots,\ x_{2N(N-1)-1,l})$。经过 $T$ 次操作后，手中种子的最大价值为 $W=\max(V_0,\ V_1,\ \cdots,\ V_{2N(N-1)-1})$，则得分为 $\mathrm{round}(10^6\times W/\sum_{l=0}^{M-1}{X_l})$。
共 300 个测试用例，所有测试用例得分之和为提交的总得分。若有任一测试用例输出非法或超时，则整体判定为 WA 或 TLE。比赛期间以最高得分计入最终排名，赛后不再进行系统测试。得分相同者排名并列。
### 输入输出示例
以下为不满足实际约束的说明用输入示例。
回合 Output Input 事前信息 ```
3 5 10
42 45 29 50 53
19 35 91 0 11
35 83 30 9 31
28 18 20 28 88
0 52 21 66 51
24 9 35 10 89
57 27 13 73 24
22 2 5 78 59
66 67 27 18 12
81 38 24 21 32
89 21 32 16 19
6 27 9 67 68
```
0 ```
5 4 7
8 9 0
11 2 6
```
```
0 52 21 10 89
0 52 21 78 59
66 67 24 18 32
81 38 24 50 32
6 27 30 67 31
57 27 13 73 24
24 9 27 10 12
81 52 24 21 51
42 45 5 50 53
66 27 27 67 68
35 83 30 9 31
42 27 13 73 53
```
1 ```
6 8 11
3 9 1
7 2 5
```
```
42 45 5 10 12
42 45 13 73 53
66 38 24 50 32
66 52 27 67 68
81 52 24 18 32
66 67 13 18 32
81 38 27 10 12
42 27 5 50 68
0 52 13 78 53
81 52 24 50 32
66 67 27 67 32
0 52 13 78 59
```
$ \vdots $ 9 ```
2 6 10
8 1 9
11 4 3
```
```
42 27 5 50 68
42 27 5 50 32
0 67 27 50 68
42 27 5 50 68
42 27 24 50 32
42 67 5 50 68
42 67 24 50 68
42 27 27 50 68
0 27 5 50 32
0 67 24 50 68
42 67 5 50 68
42 27 5 50 32
```
在此例中，$W=V_6=42+67+24+50+68=251$，$\sum_{l=0}^{M-1}{X_l}=89+83+91+78+89=430$，因此得分为 $583721$。
[查看示例](https://img.atcoder.jp/ahc035/F5dI2O6U.html?lang=ja&seed=0&output=sample)
### 示例程序（Python）
以下为 Python 解答示例。该程序每次将第 $0$ 到 $35$ 号种子按左上到右下顺序依次种下。
```python
N, M, T = map(int, input().split())
SEED_COUNT = 2 * N * (N - 1)
X = []
for i in range(SEED_COUNT):
X.append(list(map(int, input().split())))
for t in range(T):
A = [[0] * N for i in range(N)]
for i in range(N):
for j in range(N):
A[i][j] = i * N + j
for i in range(N):
print(' '.join(map(str, A[i])), flush=True)
X = []
for i in range(SEED_COUNT):
X.append(list(map(int, input().split())))
```
### 示例程序（C++）
以下为 C++ 解答示例。该程序每次将第 $0$ 到 $35$ 号种子按左上到右下顺序依次种下。
```cpp
#include
#include
using namespace std;
int main() {
int N, M, T;
cin >> N >> M >> T;
int seed_count = 2 * N * (N - 1);
vector X(seed_count, vector(M, 0));
for (int i = 0; i < seed_count; i++) {
for (int j = 0; j < M; j++) {
cin >> X[i][j];
}
}
for (int t = 0; t < T; t++) {
vector A(N, vector(N, 0));
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
A[i][j] = i * N + j;
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cout