← 返回题目列表

AtCoder · xmascon21_a

A. 随机

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

配点 : 100 点

兔子是 它有一个矩形网格昨年呀 请注意,它可能是一昨年呀 请注意,它可能是一昨々年就像这样,正在打算制作纪念 Xmas Contest 2021 的看板。

当兔子想出了前卫的设计时,狐狸 0 和狐狸 1 来了,说“今年我们也想参与看板制作”,于是兔子和狐狸们一起有趣的决定制作看板。

問題文

这个问题是交互式的。评分程序最多使用执行时间 100 ms / 内存 8 MB 左右。

横 500 px,纵向 500 有一个 px 的画布,像素的位置由整数对 (x, y) (0 \leq x < 500,0 \leq y < 500) 表示。x 注意坐标增大的方向是从左到右,y 注意坐标增大的方向是从上到下。每个像素要么是白色,要么是黑色。一开始,画布上的所有像素都是白色的。

现在,狐狸 0 和狐狸 1 正抱着巨大的铅笔站在像素上。 (0, 0) 通过进行不超过以下操作次数的操作, 10\,000 可以创建符合给定目标设计的图像。

  • 操作: 画素 (x, y) 指定 (x, y) ,“狐狸,请移动到像素上”。然后,狐狸 0 和狐狸 1 出会以相等的概率随机选择其中一方移动到像素 (x, y) 上。即使指定操作时像素上已经有(其中一个或两个)狐狸也没有关系。

当狐狸移动时,会从移动前的像素到移动后的像素画出一条黑色线段。严格来说,使用的是布雷森汉姆算法。通过求出线段经过的像素,将所有这些像素变为黑色。(详细请参考分发的本地测试器的实现)

今年的招牌设计

達成条件

目标设计为横向 500 px,纵向 500 以 px 的黑白图像形式给出。通过操作生成的图像如果满足以下 2 两个条件,则被认为“符合设计”:

  • 在目标设计中黒为的像素中,在生成的图像中也为黒的像素比例 85% 以上。
  • 在目标设计中白为的像素中,在生成的图像中也为白的像素比例 70% 以上。

数据

为了解决这个问题所需的数据汇总在一个压缩文件中单击此处下载。压缩文件中包含以下文件:

  • atrandom/input.png:表示目标设计的图像。图像大小为横 500 px,纵向 500 px。
  • atrandom/input.txt:将目标设计根据下述输入输出规格制作成的文本文件。与实际评分时提交的程序最初所接收的输入相同。
  • atrandom/interactive_tester.py:用于在本地测试该问题中的交互操作的 Python 3 工具。
    • python3 interactive_tester.py <input_file> <seed> -- <cmd_line_solution> 用作。
      • <input_file> 是将目标设计文本化后的文件路径。要在与实际评分相同的情况下进行测试,可指定随附的 input.txt 。
      • <seed> 是用来决定移动狐狸的随机数种子。本工具使用的随机数生成方法不一定与实际评分时使用的完全一致。
      • <cmd_line_solution> 表示用于运行您提交的程序的命令字符串。
    • 例如,如果将用 C++ 编写的答案在与本工具相同的目录下编译, solver.out 创建名为的可执行文件,python3 interactive_tester.py input.txt 0 -- ./solver.out 就可以作为 等来执行。
    • 同样地,例如用 Python 编写的 solver.py 如果将答案放在与本工具相同的目录下,python3 interactive_tester.py input.txt 0 -- python solver.py 就可以作为 等来执行。
    • 另外,在这个工具中存在的 drawline 函数是实现了 Bresenham 算法的。可以在制作答案等时参考。
  • atrandom/visualize.html:用于查看本地测试工具输出的详细图像数据的可视化工具。
    • 当本地测试工具正确执行时,interactive_tester.dump 这个文件会在相同层级生成。将此文件提供给可视化工具,可以可视化您程序生成的图像,并将其保存为图像。

入出力

  1. 整数 W,H,T 以空格分隔的形式通过标准输入提供。
    • 这是目标设计以及画布的横向 W px,纵向 H px 组成,最多 T 次操作是允许的。
    • 换句话说,在这个问题的输入中 W = 500,H = 500,T = 10\,000 很满意。
  2. . 和 # 仅由 W 个字符的字符串 H 行将通过标准输入提供。
    • 其中 在行 y 行目 (0 \leq y < H) 的字符串 x 文字目 (0 \leq x < W) 表示目标设计中的像素 (x, y) 的颜色。白色由 .表示,黑色由 # 表示。
  3. 以下最多 T 次。
    1. 你的程序必须 2 整数 x, y 以空格分隔的形式输出到标准输出。
      • (x, y) = (-1, -1) 时,表示不再进行进一步操作,并结束重复操作。此后将不会再提供输入。
      • 否则,0 \leq x < W 和 0 \leq y < H 必须,并且指定像素 (x, y) 来进行操作。
    2. 操作的结果,如果狐狸 k (k = 0, 1) 移动了,那么整数 k 会作为标准输入提供。

请参考输入输出示例。

注意点

所有操作结束后,你的程序必须立即结束。如果没有结束,评测结果是不确定的。此外,如果输出不符合条件,也会导致结果不确定(不一定会 WA )。

当所有操作完成并且你的程序已结束后,如果生成的图像满足达成条件,则视为正确答案。

注意,在输出后必须 flush 输出。如果没有 flush,可能会导致 TLE。

每种语言的输入/输出方法都是过去 AtCoder 问题中提出的问题(链接: ABC 019 D:高桥君和树的直径) 可作为参考。

入出力例

W=5,\ H=5,\ T=10 显示了进行该操作时的输入输出示例。

作为实际测试用例提供的输入数据仅包含分发数据中存在的相同案例 1 请注意,以下内容是为了说明输入输出的具体示例。

入力 出力 説明
5 5 10
W, H, T 已给出。
..##.
.####
####.
###..
.#...
给出了目标设计。
2 4
(x, y) = (2, 4) 以此进行操作。
1
操作的结果是移动的是狐狸 1 的信息被提供。
3 3
(x, y) = (3, 3) 以此进行操作。
1
操作的结果是移动的是狐狸 1 的信息被提供。
3 0
(x, y) = (3, 0) 以此进行操作。
0
操作的结果是移动的是狐狸 0 的信息被提供。
-1 -1
表示不再进行操作(操作在 3 次时结束)。