← 返回题目列表

AtCoder · ddcc2020_qual_e

E. 大多数球

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

分数: 800 点

问题陈述

这是一项交互式任务。

我们有 2N 球排列成一排,编号 1, 2, 3, ..., 2N 从左到右,其中 N 是奇数。其中,有 N 红球和 N 蓝色球。

蒙住眼睛时,您将面临最多询问正确猜测每个球的颜色的挑战 210 以下形式的问题:

  • 您选择任何 N 的 2N 球并询问其中红球是否比蓝球多 N 球。

现在,让我们开始吧。

约束

  • 1 \leq N \leq 99
  • N 是奇数。

输入和输出

首先,接收每种颜色的球的数量, N,来自标准输入:

N

然后,提出问题,直到找出每个球的颜色。 问题应按以下格式打印到标准输出:

? A_1 A_2 A_3 ... A_N

这意味着您要询问的是 N 球 A_1, A_2, A_3, ..., A_N,其中 1 \leq A_i \leq 2N 和 A_i \neq A_j (i \neq j) 必须保留。

回应 此问题的 T 将从标准输入中按以下格式给出:

T

这里 T 是以下字符串之一:

  • Red:其中 N 已选球,红球多于蓝球。
  • Blue:其中 N 所选择的球,蓝球多于红球。
  • -1: 您打印了一个无效的问题(包括您问了超过 210 问题),或其他无效的内容。

如果法官返回 -1,您的提交已被判定为不正确。在这种情况下,程序应立即退出。

当您找出每个球的颜色时,按以下格式将您的猜测打印到标准输出:

! c_1c_2c_3...c_{2N}

这里 c_i 应该是代表球颜色的字符 i;使用 R 为红色和 B 为蓝色。

通知

  • 每次打印内容时刷新标准输出。 如果不这样做可能会导致 TLE.
  • 打印你的猜测(或收到 -1 回应)。否则,判决将是不确定的。
  • 如果您的程序打印出无效的内容,则结论将是不确定的。

示例输入和输出

输入 输出
3
? 1 2 3
Red
? 2 4 6
Blue
! RRBBRB

在此示例中, N = 3,以及球的颜色 1, 2, 3, 4, 5, 6 分别是红、红、蓝、蓝、红、蓝。

  • 第一题中,球中有两个红球和一个蓝球 1, 2, 3,所以法官返回 Red.
  • 第二题,球中有一个红球,两个蓝球 2, 4, 6,所以法官返回 Blue.