← 返回题目列表

AtCoder · kupc2016_d

D. 长黑板

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

分数: 150 点

问题陈述

有一块长黑板,上面写着 京都大学教室里的 2 行和 N 专栏。 这块黑板太长了,以至于无法分辨哪些单元格已被使用,哪些单元格未使用。

最近,教室安装了黑板检索装置。 要使用此设备,您可以键入一个搜索查询,该查询形成一个具有 2 行和任意长度列的矩形,其中每个单元格都已使用或未使用。 当您输入查询时,设备会回答黑板上是否存在与查询对应的矩形。 这里,对于对应于搜索查询的矩形,如果两个整数 i, j ( i < j ) 存在 矩形等于列之间的部分黑板 i 和 j , 该矩形称为黑板的子黑板。

您目前正在准备在本教室进行演示。 为了使演示顺利进行,您决定编写一个程序,使用检索设备来检测整个黑板的状态。 由于使用该设备需要时间,因此您希望尽可能少地使用它。

整个黑板的状态在一开始就已经确定,并且在您使用设备时不会改变。


输入

第一个输入按以下格式给出:

N

N (1 \leq N \leq 100) 是一个整数,表示黑板的长度。

在此输入值之后,您的程序必须打印搜索查询。 搜索查询具有以下格式。

s_1
s_2

在这里, s_1 代表黑板的上部, s_2 代表较低。 # in s_1 和 s_2 表示该单元已被使用并且 . 表示该单元格仍未使用。 的长度为 s_1 和 s_2 是任意的,但它们必须相同。 确保在行尾插入换行符。

每次程序打印搜索查询时,都会以以下格式返回表示设备搜索结果的字符串。

r

r 是 T or F 。 各字符的含义如下。

  • T 表示黑板中存在与搜索查询对应的子黑板。
  • F 表示黑板中不存在与搜索查询对应的子黑板。

如果搜索查询等于整个黑板或搜索查询数量超过限制,则字符串 给出 end 而不是 r 。 一旦收到此字符串,请立即退出程序。 如果你的程序在超出限制之前打印整个黑板作为搜索查询,则判断为 已接受。请注意,代表整个黑板的搜索查询也算作搜索查询的数量。

请注意,每次打印输出时都需要刷新输出。 例如,在 C/C++ 中,搜索查询 s1, s2 可以按如下方式打印。

printf("%s\n%s\n", s1, s2); fflush(stdout);

确保您的程序接收来自设备的所有输入。否则,结果可能是 超出时间限制 .


查询限制

最大搜索查询数为 420。 如果查询次数超过限制,结果将是 超出查询限制 .


示例输入和输出

以下是一个示例,其中 N=3 和黑板如下。

.#.
...

请注意,您的程序不知道黑板的状态。

Output of your program Input to your program Explanation
3 The length of the blackboard is given
..
##
Output a search query
F The sub-blackboard does not exist
.
.
Output a search query
T The sub-blackboard exists
..
..
Output a search query
F The sub-blackboard does not exist
.#
..
Output a search query
T The sub-blackboard exists
.#.
...
Output a search query
end Exit your program because the above sub-blackboard equals to the whole blackboard.