← 返回题目列表

AtCoder · pakencamp_2018_day2_h

H. 分发礼物(圣诞老人轨道)

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

問題文

圣诞老人在一个名为 PAKEN CITY 的小镇分发礼物。

PAKEN 城市是 该城市由 (2N+1) \times (2N+1) 网格表示,位于北部。 i+1 广场,从西边看 j+1 正方形 由 (i, j) 代表。
此时,i 是“行号”, 我们将j 称为“列号”。

PAKEN CITY 中的每个方块要么是“道路”,要么是“空地”,要么是“房屋”。
行数或列数为偶数的方格为道路,均为奇数的方格为空地或房屋。
由输入给出 S_{R, C} 是质量 给出了 (2R+1, 2C+1) 。. 为“空地”; 当1〜9 是房子时,这个数字代表住在房子里的人数。

圣诞老人 reiji1112 你从某个道路交叉口(行数和列数为偶数的正方形)开始,尝试穿过同一个正方形两次。 K 沿着经过不超过3个路口并返回原始位置的路线分发礼物。 另外,在家(4 方向)你可以从相邻的方格向这所房子分发礼物。可以向一所房子分发的礼物数量取决于该房子的居住人数。也在同一个房子里 您分发礼物的次数不能超过 2 次。

请为圣诞老人创建一条路线,以分发尽可能多的礼物。

圣诞老人的路径示例如下所示,输入如下:

3 6
123
4.5
678


在这种情况下, 创建一个2 + 4 + 5 + 6 + 7 + 8 = 32 您可以向人们分发礼物。

入力

N K
S_{0,0}S_{0,1}S_{0,2}...S_{0,N-1}
S_{1,0}S_{1,1}S_{1,2}...S_{1,N-1}
S_{2,0}S_{2,1}S_{2,2}...S_{2,N-1}
 :  :    :
S_{N-1,0}S_{N-1,1}S_{N-1,2}...S_{N-1,N-1}

出力

起始交叉点的坐标是 (2R, 2C) 并从初始位置开始,向东、西、南、北方向移动。 2 前进时,每个 R, L, D, U”已连接 K 字符串小于或等于 X 对于每种情况: 请输出

R C X 

。X 是这种情况下的字符数。 K 必须小于或等于字符。例如,问题文本中图表示例的输出是 1 1 DDRUUL 。但是,当某些情况的结果不可用时,对于该情况:

-1 -1 -1

。

总而言之 需要 6 既然有案子,那么案子 从 1 开始 6 请以行的形式输出。
但是,此问题采用仅输出格式,并且还给出了输入数据,因此如果您想在您的环境中找到答案,我们建议以 Text(cat) 语言提交(作为输出的字符串)。

1 1 DDRUUL
-1 -1 -1
-1 -1 -1
-1 -1 -1
-1 -1 -1
-1 -1 -1

这样,6 行。然而,即使有这样的输出 0 点。请参阅“分数”部分了解更多信息。

请注意,如果路线没有返回起点,如果$X$超过$K$字符,或者如果您输出的路线超出了PAKEN CITY,则会出现诸如WA之类的错误。


关于案件

情况如下。

案件编号 得点 N K V_1 V_2 V_3 V_4 V_5
#1 10 9 24 220 260 271 - -
#2 18 100 280 2766 2937 3051 3110 3230
#3 18 500 1400 13299 14104 14641 14940 15820
#4 18 500 1400 3346 3975 4394 4600 5060
#5 18 500 1400 11368 15543 16198 16600 17490
#6 18 100 1000 8950 9783 10338 10660 11310

输入数据如下 ZIP 文件 可以通过下载 获得。

得点

在前面的“案例”部分中, 值V_1, V_2, V_3, V_4, V_5 已确定,但这与分数有关。

  • 首先, 交换第V_1 是 您也可以写 25 百分比点线。如果小于0.8倍 0 点,0.8 倍〜1 次,点数线性增加。
  • 接下来,V_2 是 您也可以写 70 百分比点线。 分数在V_1 减去 V_2 期间线性增加。 直到
  • 接下来,V_3 是 您也可以写 100 百分比点线。 分数在V_2 减去 V_3 期间线性增加。 直到
  • V_3 减去 V_4 为止的所有内容 100 百分点。 如果超过
  • 分数 V_4 ,则得分 分数线性增加直到 V_5 。 当V_5 时,最高分数为 120 个百分位点。

换句话说,分数的变化如下图所示。