故事
AtCoder 正在致力于改良谷物品种。粮食具有口感、产量、抗病性等多重评价标准。高桥首席执行官的目标是创造出在所有评估标准上都表现出色的谷物。
通过在网格状田地中种植谷物种子,一年后可以收获新种子,这些种子随机继承两个相邻种子的每个评估标准的值。通过多次重复种植和收获过程,请创造出最好的谷物种子。
问题陈述
有一个由 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}),代表每个标准的优度。 价值 V_k 种子 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 is \boldsymbol{x_0}=(1, 2, 3) 和种子的评价向量 1 is \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)
评分
对于最初给出的 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 or TLE ,提交的分数将为零。 比赛期间获得的最高分将决定最终排名,比赛结束后不进行系统测试。 如果超过一名参赛者获得相同分数,则无论提交时间如何,他们都将排名在同一位置。
输入和输出
注意:此问题是交互式的。阅读下面的解释,并与判断程序进行相应的沟通。
首先,您将获得网格大小 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} < 2N(N-1)。一样的 A_{i,j} 在同一回合中不得输出多次。
输出后,新生成的评价向量 2N(N-1) 种子将从标准输入以以下格式给出。
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.
您的程序可能会输出以以下开头的注释行 #。可视化工具的网络版本显示注释行以及相应的时间,这对于调试和分析可能很有用。由于判断程序会忽略所有注释行,因此您可以提交按原样输出注释行的程序。
示例
请注意,以下是用于解释目的的示例输入,不满足输入约束。
| 转 | 输出 | 输入 |
|---|---|---|
| 先前信息 | 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.
示例解决方案 (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++)
#include <iostream>
#include <vector>
using namespace std;
int main() {
int N, M, T;
cin >> N >> M >> T;
int seed_count = 2 * N * (N - 1);
vector<vector<int>> X(seed_count, vector<int>(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<vector<int>> A(N, vector<int>(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 << A[i][j];
if (j < N - 1) {
cout << " ";
} else {
cout << endl;
}
}
}
cout.flush();
for (int i = 0; i < seed_count; i++) {
for (int j = 0; j < M; j++) {
cin >> X[i][j];
}
}
}
return 0;
}
输入生成
定义一个函数 \mathrm{randnormal}() 从生成值 标准正态分布.
对于每个 k=0, 1, \cdots, 2N(N-1),生成 \boldsymbol{x_k}=(x_{k,0}, x_{k,1}, \cdots, x_{k,M-1}) 如下。
生成一个 M维向量 (x_{k,0}',\cdots,x_{k,M-1}') by x_{k,l}'=|\mathrm{randnormal}()|。让 p_k=\frac{100}{\sqrt{\sum_{l=0}^{M-1}x_{k,l}'^2}} 并定义 x_{k,l}=\mathrm{round}(p_k x_{k,l}').
工具(输入生成器、本地测试器和可视化器)
- 网页版:这个比本地版本更强大,可以显示动画。
- 本地版本: 你需要一个编译环境 Rust 语言.
- Windows 预编译二进制文件:如果你不熟悉Rust语言环境,请使用这个。
请注意,比赛期间禁止分享可视化结果或讨论解决方案/想法。
工具使用的输入文件规范
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}
u_{0,0,0} \cdots u_{0,0,N-2}
\vdots
u_{0,N-1,0} \cdots u_{0,N-1,N-2}
v_{0,0,0} \cdots v_{0,0,N-1}
\vdots
v_{0,N-2,0} \cdots v_{0,N-2,N-1}
\vdots
u_{T-1,0,0} \cdots u_{T-1,0,N-2}
\vdots
u_{T-1,N-1,0} \cdots u_{T-1,N-1,N-2}
v_{T-1,0,0} \cdots v_{T-1,0,N-1}
\vdots
v_{T-1,N-2,0} \cdots v_{T-1,N-2,N-1}
在这里, u_{t,i,j} 和 v_{t,i,j} 是 M- 组成的字符串 0 和 1,它们的含义如下:
- 如果 l- 第一个字符 u_{t,i,j} is
0, l- 从种子生成的新种子的评估向量的第一个元素 A_{i,j} 和 A_{i,j+1} 种植于 (i,j) 和 (i, j+1) 为 t-第操作将是 x_{A_{i,j},l};如果是的话1,这将是 x_{A_{i,j+1},l}. - 如果 l- 第一个字符 v_{t,i,j} is
0, l- 从种子生成的新种子的评估向量的第一个元素 A_{i,j} 和 A_{i+1,j} 种植于 (i,j) 和 (i+1, j) 为 t-第操作将是 x_{A_{i,j},l};如果是的话1,这将是 x_{A_{i+1,j},l}.