← 返回题目列表

AtCoder · pakencamp_2020_day2_h

H. 出发当天

中文机器翻译题面 查看原题

配点 : 1800 点

問題文

您和kaage(以下简称“您”), 在N*N 网格上,两个人骑着自行车进行定向运动。从网格顶部开始(0 索引) i 行,从左侧开始(0 索引) 表示为 j 该列中的单元格是 它由 (i,j) 。根据下面所示的定向运动规则,您的目标是在定向运动结束时获得尽可能高的分数。

  • 你们是时候了 从 0 到质量 (sx,sy) 出发。
  • 定向运动的场地是 这是由0\leq i,j<N 的任意整数 对于 i,j 可以表示为 (i,j) 表示的整个正方形。定向运动期间不能外出。
  • 场方格是“陆地”和“海洋” 2 分为类型。当你们在“陆地”广场上时,你们各自,1 你可以垂直、水平或垂直移动到相邻的“陆地”方块,也可以留在原地。你不能进入“海”广场。
  • 首先给出您获得“分数”的方式。 目标是完成 M “任务”。使命包括: 3 有不同的类型,如果你完成每一种,你都会收到一个任务。 1 筒木 S_1, S_2, S_3 您可以获得积分。

    • 使命 1: 某个方格 两个人同时访问 (x, y) 。 两者之一将访问
    • 使命 2: 某个方格 两个人同时访问 (x, y) 。
    • 使命 3:一组特定的正方形 两人中的一人将访问 (x_1, y_1),(x_2,y_2),\cdots,(x_k,y_k) 中包含的所有方块。

入力

输入是按以下格式从标准输入给出的。

\(N\) \(T\) \(M\) \(sx\) \(sy\)
\(S_1\) \(S_2\) \(S_3\)
\(v_{0,0}\) \(v_{0,1}\) \(\cdots\) \(v_{0,N-1}\)
\(\vdots\)
\(v_{N-1,0}\) \(v_{N,1}\) \(\cdots\) \(v_{N-1,N-1}\)
Mission_1\\
Mission_2\\
\vdots\\
Mission_M

\(v_{i,j}\) 是 . 或 要么- 。v_{i,j} 是 在 . 当广场 (i,j) 是“土地”,- 的意思是“海”。

另外,Mission_i 代表一个任务,格式如下:

\(1\) \(x_i\) \(y_i\)

使命 1 参观的广场是 (x_i,y_i) 。

\(2\) \(x_i\) \(y_i\)

使命 2 参观的广场是 (x_i,y_i) 。

\(3\) \(k_i\)
\(x_{i,1}\) \(y_{i,1}\)
\(x_{i,2}\) \(y_{i,2}\)
\vdots
\(x_{i,k_i}\) \(y_{i,k_i}\)

使命 3 参观的广场是 (x_{i,1}, y_{i,1}),(x_{i,2},y_{i,2}),\cdots,(x_{i,k_i},y_{i,k_i}) 。

出力

你们所有人 定向运动开始 1\leq i\leq T 定向运动开始 i 分钟后两个人所在的每个方格的位置, i 必须以空格分隔输出。但是,如果你做出了违背题目意图的举动,你这道题的分数将会降低。 0 点, 它变成WA 。举个例子,i 几分钟后您将进入的广场是 (x_{i,A},y_{i,A}), kaage 你所在的方格是 (x_{i,B},y_{i,B}) 时,i 行的输出如下。 除

\(x_{i,A}\) \(y_{i,A}\) \(x_{i,B}\) \(y_{i,B}\)

制約

  • 输入是 v_{i,j} 外均为整数。
  • N=201
  • sx=sy=100
  • T=10000
  • M=1000
  • S_1=5,S_2=4,S_3=7
  • \(v_{i,j}\) 是 . 或 要么- 。
  • 1\leq k_i \leq 5
  • 0\leq x_i,x_{i,j},y_i,y_{i,j}\leq 200
  • (x_i,y_i),(x_{i,j},y_{i,j}),(sx,sy) 是一个“土地”方块。 你可以从
  • (sx,sy) 到达所有非海洋广场,而无需穿过海洋广场。
  • “陆地”方格占据了整个场地的一半以上。 有

如何生成测试用例

总共 20 ,它们是使用下面所示的算法生成的。 考虑

  1. N*N 的网格。 从[0,N) 中均匀随机 以 x_i,y_i ,[0,70] 中均匀随机 以 h_i , (x,y) 为中心的高度 建造一座 h_i 山并将其添加到网格中。具体来说, 添加了(x,y) 有 直到 max(0, h_i-|x_i-x|-|y_i-y|) 。
  2. 1. 对以下操作求和 50 次。 将
  3. 2. 对于由以下材料制成的网格 X 当X<30 如果是,请使用“海洋”,否则使用“陆地”。
  4. 3. 如果创建的网格不满足约束,则返回步骤1。如果满足约束,则该网格成为输出网格。 生成
  5. M 任务。任务编号是 从 [1,3] 中均匀随机选择,任务 3 的坐标数为 从 [1,5] 中均匀随机选择。坐标是从整个“土地”方格中均匀随机选取的。
另外,开发文件已分发,因此也请参阅。

採点

您在此问题上的得分是20 测试用例的分数总和为 该值除以 80 并向下舍入到小数点。


入力例1

4 5 2 2 2
7 3 6
....
....
...-
..--
3 2
1 2
2 1
2 1 1

出力例1

1 2 2 2
1 1 2 1
2 1 2 1
2 2 2 2
2 2 2 2

请注意,这是一个说明性输入示例,不满足任何约束。 在此示例中,您的分数是 9 变为。

作者: 凯上