问题陈述
有 N(N+1)/2 球排列成 N- 分层金字塔如下图所示。 让 (0, 0) 为金字塔顶部球的坐标,令 (x,y) 是坐标 y (0\leq y\leq x)左起第一个球 x (0\leq x-1)从顶部算起的第 3 层。
每个球都标有来自 0 to N(N+1)/2-1,每个球上的数字都不同。 您可以通过一次操作在六个方向上交换两个相邻的球。 这里,球在坐标处 如果满足以下条件之一,则 (x_1,y_1) 和 (x_2,y_2) 在六个方向上相邻。
- x_1=x_2-1 和 y_1=y_2-1
- x_1=x_2-1 和 y_1=y_2
- x_1=x_2 和 y_1=y_2-1
- x_1=x_2 和 y_1=y_2+1
- x_1=x_2+1 和 y_1=y_2
- x_1=x_2+1 和 y_1=y_2+1
最多执行此操作 10000 次,请排列球,使每个球 (x,y) (0\leq x\leq N-2, 0\leq y\leq x) 除了最低层的球的数字小于两个球的数字外 (x+1,y), (x+1,y+1) 就在它的下面。 请通过尽可能少的操作来实现这一点。
评分
让 K 是操作次数并且 E 为完成操作后违反条件的球对的数量。 这里 E 是总对数 (x,y) 和 (x+1,y') (y'\in\{y,y+1\}) 这样的球 (x,y) 的数字比球大 (x+1,y')。 然后你将获得以下分数。
- If E=0, 100000-5K.
- If E>0, 50000-50E.
共有150个测试用例,提交的分数是每个测试用例的总分。 如果您的提交产生非法输出或超出某些测试用例的时间限制,则提交本身将被判断为 WA or TLE ,提交的分数将为零。 比赛期间获得的最高分将决定最终排名,比赛结束后不进行系统测试。 如果超过一名参赛者获得相同分数,则无论提交时间如何,他们都将排名在同一位置。
输入
金字塔层数固定为 N=30 对于所有输入,球的总数为 N(N+1)/2=465。 输入由标准输入提供,格式如下:
b_{0,0}
b_{1,0} b_{1,1}
b_{2,0} b_{2,1} b_{2,2}
\vdots
b_{29,0} \cdots b_{29,29}
b_{x,y} 是满足以下条件的整数 0\leq b_{x,y}\leq 464 表示球上最初在坐标处写的数字 (x,y)。 所有数字都是不同的。
输出
让 K 是操作次数并且 (x_i,y_i), (x'_i,y'_i) 是要交换的两个球的坐标 i-第次操作。 然后,按以下格式输出到标准输出。
K
x_0 y_0 x'_0 y'_0
\vdots
x_{K-1} y_{K-1} x'_{K-1} y'_{K-1}
操作次数 K 不得超过 10000 并且任何两个要交换的球必须在6个方向上相邻。 若不满足,提交作品将被判定为 WA .
输入生成
输入是通过随机洗牌生成的 465 带有数字的球 0 to 464.
工具(输入生成器和可视化工具)
- 网页版:这比提供动画的本地版本更强大。
- 本地版本: 你需要一个编译环境 Rust 语言.
- Windows 预编译二进制文件:如果你不熟悉Rust语言环境,请使用这个。
请注意,比赛期间禁止分享可视化结果或讨论解决方案/想法。