P15499 [ICPC 2025 APC] Secret Lilies and Roses

有 $n$ 朵花从左到右排成一行，依次编号为 $1$ 到 $n$。每朵花要么是百合，要么是玫瑰。对于介于 $0$ 到 $n$ 之间（包含两端）的整数 $j$，令 $l_{j}$ 表示最左边 $j$ 朵花中百合的数量，$r_{j}$ 表示最右边 $n - j$ 朵花中玫瑰的数量。 初始时，你只知道花的数量 $n$。花的种类是隐藏的。你可以通过进行 **查询** 来获取花朵的信息。每次查询，你可以执行以下操作之一。 - **类型查询：** 指定一个介于 $1$ 到 $n$ 之间（包含两端）的整数 $i$。你将收到第 $i$ 朵花的类型。 - **乘法查询：** 指定一个介于 $0$ 到 $n$ 之间（包含两端）的整数 $j$。你将收到 $l_{j} \times r_{j}$ 的值。 你的任务是通过有限次查询找到一个介于 $0$ 到 $n$ 之间（包含两端）的整数 $k$，使得 $l_{k} = r_{k}$。你可以假设对于给定的花朵类型排列，至少存在一个这样的整数。注意，你不需要识别每一朵花的类型。 ### 交互过程 输入的第一行包含一个整数 $t$（$1 \le t \le 100$），表示测试用例的数量。之后是 $t$ 个测试用例，每个测试用例的格式如下。 每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 100$）。读取该整数后，你的程序即可开始进行查询。对于每次查询，你的程序应输出一行，包含以下格式之一： - `type i` 表示进行类型查询，其中 $i$ 为指定的整数（$1 \le i \le n$）。作为响应，输入中将有一行包含一个字符串 `lily` 或 `rose`，表示第 $i$ 朵花的类型。 - `multi j` 表示进行乘法查询，其中 $j$ 为指定的整数（$0 \le j \le n$）。作为响应，输入中将有一行包含整数 $l_{j} \times r_{j}$ 的值。 对于每个测试用例，你的程序最多允许进行 $10$ 次查询。这意味着类型查询和乘法查询的总次数不得超过 $10$。如果查询次数超过 $10$，你将得到“答案错误”的评判结果。 当你的程序确定了某个整数 $k$ 满足 $l_{k} = r_{k}$ 时，应输出一行，格式为 `answer k`（$0 \le k \le n$）。注意，提供答案不计入查询次数。 输入保证至少存在一个正确答案。如果有多个正确答案，任意一个都将被接受。 输出答案行后，你的程序应开始处理下一个测试用例。当所有 $t$ 个测试用例都处理完毕后，交互结束，你的程序应当终止。 **关于交互式评测的说明：** - 评测是非对抗性的，即花的类型是预先选定的，而不是根据你的查询动态调整的。 - 输出后不要忘记刷新输出缓冲区。详情请参见“评测细节”文档。 - 我们提供了一个用于本地测试的命令行工具，以及对应于示例交互的输入文件。你可以从 DOMjudge 下载这些文件。该工具顶部有注释说明其用法。

无

无

**示例交互 #1 的解释** 对于第一个测试用例，九朵花的排列如下图所示。对于第三个查询，返回 $l_{6} \times r_{6} = 3 \times 2 = 6$；对于第四个查询，返回 $l_{3} \times r_{3} = 1 \times 3 = 3$。由于 $l_{5} = r_{5} = 3$，$k = 5$ 是一个正确答案。 :::align{center}  ::: 对于第二个测试用例，假设所有三朵花都是玫瑰。 翻译由 DeepSeek 完成