← 返回题目列表

AtCoder · rcl_contest_2021_long_a

A. 农场王X

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

问题陈述

X先生有一个大农场,其中包括 N \times N 方块。
我们称该广场为 r从顶部开始的第 1 行 c左起第 列作为区域 (r, c) (0≤r, c<N).

M 未来农场里的蔬菜会生长并死亡 T 天。
的 树的 i-第蔬菜由五个整数表示 R_{i},C_{i},S_{i},E_{i}, 和 V_{i}.
他们的意思是具有以下价值的蔬菜 V_{i} 将出现在该区域 (R_{i},C_{i}) 上 S_{i}- 第天,并在结束时消失 E_{i}第一天。

X 用收割机收割这些蔬菜。
起初,他没有任何收割机,并且有 1 货币单位。

在每个 T 天,X 做出以下操作之一。

  • 购买
    • X 获得一台新的收割机,并将其放在没有另一台收割机的区域中。
    • 当 X 有 j 收割机、采购成本 (j+1)^3 货币单位。
      • 例如首次进货费用 1 货币单位。第二次购买费用 8 货币单位,等等。
    • X 如果没有足够的钱就无法购买机器。
  • 移动
    • X 选择一台收割机并将其移动到没有收割机的区域之一。
  • 通过
    • X 不执行任何操作。

之后 t-th (0≤t<T) 行动时,以下事情按顺序发生。

  • 对于所有我在哪里 S_{i} = t, 蔬菜 i 出现在该区域 (R_{i},C_{i}).
  • 在有收获机的地区收获蔬菜。
    • 对于每种蔬菜,让 v 为其值,并且 k 是具有包含蔬菜位置的收割机区域的 4 个连通分量的大小。
      • 4 连通分量是通过垂直或水平相邻区域相互连接的区域组。
    • X 收入 v \times k 货币单位。
    • 这种蔬菜消失了。 如果尚未收获,
  • 对于所有我在哪里 E_{i} = t, 蔬菜 i 就会从农场消失。

你的目标是在他赚到尽可能多的钱之后 T-1- 第一天,确定 X 将采取的行动。

评分

测试用例的分数是 X 在 T-1第一天。
提交的分数是每个测试用例的总分。

  • 临时测试由 50 个测试用例组成。如果您得到的结果不是 AC 对于一个或多个测试用例,提交的分数将为零。
  • 系统测试由 1000 个测试用例组成。如果您得到的结果不是 AC 对于某些测试用例,只有这些测试用例的分数为零。
    由于执行时间会有一些差异,非常接近时间限制的提交可能会导致 TLE 在系统测试中。 请测量程序中的执行时间以终止进程,或者在执行时间上留有足够的余量。 我们将发布 种子.txt (md5=75031719692fe939fb105e7af16e31c8) 比赛结束后。


输入

输入是按以下格式从标准输入给出的。
第一行由三个整数组成 N,M,T 用空格分隔。接下来的每一个 M 行由五个以空格分隔的整数组成。

N M T
R_{0} C_{0} S_{0} E_{0} V_{0}
\(\vdots\)
R_{i} C_{i} S_{i} E_{i} V_{i}
\(\vdots\)
R_{M-1} C_{M-1} S_{M-1} E_{M-1} V_{M-1}
  • N 是一个整数,代表农场的大小并满足 N=16.
  • M 是一个整数,表示蔬菜的数量并满足 M=5000.
  • T 是一个整数,表示天数并满足 T=1000.
  • R_{i} 和 C_{i} 是表示其中区域的整数 i第蔬菜出现,满足 0≤R_{i}<N, 0≤C_{i}<N.
  • S_{i} 是一个整数,表示日期 i第蔬菜出现,并满足 S_{i}≤S_{i+1},0≤S_{i}<T.
  • E_{i} 是一个整数,表示日期 i-th 蔬菜消失,并且满足 S_{i}≤E_{i}<T.
  • V_{i} 是一个整数,表示 i-第蔬菜。有关详细信息,请参阅下面的“测试用例生成”部分。
  • If (R_i, C_i)=(R_j, C_j) (i<j) ,那么 E_i<S_j。也就是说,出现在同一区域的蔬菜的生命周期不重叠。

输出

输出 T行。
i- 第行代表 X i- 第一个动作。

  • 用于制作 购买,输出两个以空格分隔的整数。
    • 将购买的收割机放置在该区域 (r_{1},c_{1}),输出 r_{1} c_{1}.
  • 做一个 移动,输出两个以空格分隔的整数。
    • 将收割机移出该区域 (r_{1},c_{1}) 到该地区 (r_{2},c_{2}),输出 r_{1} c_{1} r_{2} c_{2}.
    • (r_{1},c_{1}) 可能与 (r_{2},c_{2}).
  • 为了做 通过,输出 -1.

测试用例生成

每种蔬菜的生成方式如下。
所有随机选择都是统一随机的。
有关确切的详细信息,请参阅测试用例生成器的源代码。

  • l_{i} 从之间的整数中选择 0 和 20,包括在内。
  • S_{i} 从之间的整数中选择 0 和 T-1-l_{i},包括在内。
  • E_{i} is S_{i} + l_{i}.
  • v_{i} 是从大于或等于的浮点数中选择的 0.0 且小于或等于 1.0+S_{i}/100.0.
  • V_{i} is \text{floor}(2^{v_{i}}).
    • \text{floor}(x) 表示不大于的最大整数 x.
  • R_{i} 和 C_{i} 独立地从之间的整数中选择 0 和 N-1,包括在内。
  • 如果任何已生成的蔬菜具有相同的 (R_{i},C_{i}) 由于新生成的蔬菜及其生命周期与新生成的蔬菜重叠,因此对该蔬菜再次执行生成。
  • 已生成 M 蔬菜按元组字典顺序排序 (S_{i},R_{i},C_{i}).


    示例输入

    9 4 10
    3 3 1 5 35
    4 4 4 6 22
    8 8 7 9 20
    2 3 8 9 10
    

    注意:此输入用于解释目的,不符合约束。

    示例输出

    3 3
    -1
    2 3
    3 4
    2 3 4 4
    3 3 7 8
    4 4 7 7
    3 4 8 7
    8 8
    -1
    
    输出 说明 收割机放置 货币兑换
    3 3
    
    X 购买了一台收割机 1 货币单位,并将其放置到该区域 (3,3).
    ---------
    ---------
    ---------
    ---o-----
    ---------
    ---------
    ---------
    ---------
    ---------
    
    1 -> 0
    
    -1
    
    X 不执行任何操作。
    该区域出现蔬菜 (3,3) 并收获。
    X 收入 35 \times 1 = 35 货币单位。
    ---------
    ---------
    ---------
    ---o-----
    ---------
    ---------
    ---------
    ---------
    ---------
    
    0 -> 35
    
    2 3
    
    X 购买了一台收割机 8 单位金钱,并将其放置到该区域 (2,3).
    ---------
    ---------
    ---o-----
    ---o-----
    ---------
    ---------
    ---------
    ---------
    ---------
    
    35 -> 27
    
    3 4
    
    X 购买了一台收割机 27 单位金钱,并将其放置到该区域 (3,4).
    ---------
    ---------
    ---o-----
    ---oo----
    ---------
    ---------
    ---------
    ---------
    ---------
    
    27 -> 0
    
    2 3 4 4
    
    X 移动位于 (2,3) 到该地区 (4,4).
    之后,该区域出现蔬菜 (4,4) 并收获。
    X 收入 22 \times 3 = 66 货币单位。
    ---------
    ---------
    ---------
    ---oo----
    ----o----
    ---------
    ---------
    ---------
    ---------
    
    0 -> 66
    
    3 3 7 8
    
    X 移动位于 (3,3) 到该地区 (7,8).
    ---------
    ---------
    ---------
    ----o----
    ----o----
    ---------
    ---------
    --------o
    ---------
    
    66 -> 66
    
    4 4 7 7
    
    X 移动位于 (4,4) 到该地区 (7,7).
    ---------
    ---------
    ---------
    ----o----
    ---------
    ---------
    ---------
    -------oo
    ---------
    
    66 -> 66
    
    3 4 8 7
    
    X 移动位于 (3,4) 到该地区 (8,7).
    ---------
    ---------
    ---------
    ---------
    ---------
    ---------
    ---------
    -------oo
    -------o-
    
    66 -> 66
    
    8 8
    
    X 购买了一台收割机 64 单位金钱,并将其放置到该区域 (8,8).
    之后,该地区的一种蔬菜 (8,8) 已收获。
    X 收入 20 \times 4 = 80 货币单位。
    ---------
    ---------
    ---------
    ---------
    ---------
    ---------
    ---------
    -------oo
    -------oo
    
    66 -> 82
    
    -1
    
    X 不执行任何操作。 该地区的一种蔬菜 (2,3) 消失。
    ---------
    ---------
    ---------
    ---------
    ---------
    ---------
    ---------
    -------oo
    -------oo
    
    82 -> 82
    

    从此输出获得的分数是 82.

    工具

    我们为参赛者提供工具。它包含测试用例生成器、输出验证器、示例输入数据、解决方案可视化器和示例解决方案(C++、Python)。

    参赛工具(zip)


    展示台

    • 该可视化工具在最新的桌面版本上进行了测试 谷歌浏览器 和 Mozilla 火狐浏览器。我们不保证它适用于所有浏览器。
    • 此可视化工具上计算的分数并非比赛的实际分数。在 AtCoder 竞赛页面提交您的解决方案即可参加竞赛。
    • 使用此可视化工具的风险由您自行承担。

    该可视化工具也包含在参赛者工具中。

    输入文件
    输出文件
    fps
    另存为图像
    钱
    行动
    机器
    价格
    日志