UOJ Logo Universal Online Judge

UOJ

#405. 【IOI2018】组合动作

统计

你在玩一个动作游戏。游戏控制器有 $ 4 $ 个按键,ABXY。在游戏中,你用组合动作来赚金币。你可以依次按这些按键来完成一个组合动作。

这个游戏有一个隐藏的按键序列,可以表示为由这 $ 4 $ 个字符组成的串 $ S $。你并不知道这个串 $ S $,但是你知道它的长度为 $ N $。

你还知道,$S$ 的首字符不会在串中重复出现。例如,$S$ 可以是“ABXYY”或者“XYYAA”,但不能是“AAAAA”或“BXYBX”。

你可以依次按最多 $ 4N $ 个按键来完成一个组合动作。串 $ p $ 为你所按的按键序列。你用这个组合动作赚到的金币数量,等于同时为 $ p $ 之子串和 $ S $ 之前缀的最长字符串的长度。串 $ t $ 的子串定义为 $ t $ 中的连续字符序列(可以为空)。$ t $ 的前缀定义为 $ t $ 的子串,其或者为空,或者包含 $ t $ 的首字符。

例如,如果 $S$ 是“ABXYY”,而 $ p $ 是“XXYYABYABXAY”,你会得到 $ 3 $ 个金币,因为“ABX”是可作为 $ p $ 的子串的 $ S $ 的前缀中最长的。

你的任务是,用少量的组合动作,找出隐藏字符串 $ S $。

实现细节

你需要实现下面的函数:

std::string guess_sequence(int N)
  • N:串 $S$ 的长度。
  • 对每个测试用例,该函数被调用恰好一次。
  • 该函数应返回串 $S$。

你的程序可以调用下面的函数:

int press(std::string p)
  • p:你的按键序列。
  • p 必须是长度为从 $0$ 到 $4N$ 的串(包括 $0$ 和 $4N$)。p 的每个字符必须是 ABX 或者 Y
  • 对每个测试用例,你调用该函数的次数不能超过 $8\ 000$ 次。
  • 该函数的返回结果是,当按出按键序列 p 后你赚到的金币数量。

如果不满足上面的条件,你的程序将被判为 Wrong Answer。否则,你的程序将被判为 Accepted,而你的得分将根据 press 的调用次数来计算(参见子任务)。

例子

设 $S$ 为“ABXYY”。评测程序调用了 guess_sequence(5)。数据交互过程的例子如下所示:

调用 返回值
$ \texttt{press("XXYYABYABXAY")} $ $ 3 $
$ \texttt{press("ABXYY")} $ $ 5 $
$ \texttt{press("ABXYYABXYY")} $ $ 5 $
$ \texttt{press("")} $ $ 0 $
$ \texttt{press("X")} $ $ 0 $
$ \texttt{press("BXYY")} $ $ 0 $
$ \texttt{press("YYXBA")} $ $ 1 $
$ \texttt{press("AY")} $ $ 1 $

对于 press 的第 $1$ 次调用,“ABX”是“XXYYABYABXAY”的子串,而“ABXY”不是,因此返回 $3$。

对于 press 的第 $3$ 次调用,“ABXYY”本身是“ABXYYABXYY”的子串,因此返回 $5$。

对于 press 的第 $6$ 次调用,除了空串以外没有“ABXYY”的其他前缀可以是“BXYY”的子串,因此返回 $0$。

最后,guess_sequence(5) 应当返回“ABXYY”。

在样例数据下载中的文件ex_combo1.in对应于本例。注意:样例包中的输出没有任何意义。

限制条件

  • $1\le N\le 2\ 000$
  • 串 $S$ 的每个字符必须是 ABXY
  • $S$ 的首字符不会再 $S$ 中重复出现。

在本题中,评测程序不是适应性的。意思是说,在评测程序开始运行的时候 $S$ 就固定下来,而且不依赖于你的程序所做的询问。

子任务

  1. (5分)$N=3$
  2. (95分)没有附加限制。对该子任务,你在每个测试用例上的得分将计算如下。设 $q$ 为调用 press 的次数。
    • 如果 $q\le N+2$ ,你的得分为 $95$。
    • 如果 $N+2 \lt q \le N+10$,你的得分为 $95-3(q-N-2)$。
    • 如果 $N+10\lt q \le 2N+1$,你的得分为 $25$。
    • 如果 $\max\{N+10,2N+1\}\lt q \le 4N$,你的得分为 $5$。
    • 否则,你的得分为 $0$。

注意,你在每个子任务上的得分,等于你在该子任务下所有测试用例上的最低得分。

请注意:在测试中,如果你的程序的询问次数超过 $ N + 2 $,则会得到 $ 0 $ 分。

评测程序示例

评测程序示例将读取如下格式的输入:

  • 第 $1$ 行:$S$

如果你的程序被判为 Accepted,评测系统示例将打印出 Accepted: q,这里 q 为函数 press 的调用次数。

如果你的程序被判为 Wrong Answer,它打印出 Wrong Answer: MSG。各类 MSG 的含义如下:

  • invalid press:输入到 press 的值 p 是无效的。也就是说,p 的长度不在 $0$ 到 $4N$ 之间(含 $0$ 和 $4N$),或者 p 的某些字符不是 ABXY
  • too many moves:函数 press 的调用次数超过 $8\ 000$ 次。
  • wrong guessguess_sequence 返回的不是 $S$。

约定及限制

对于所支持的各种编程语言,下面列出了对应的数据类型。对于数据类型的细节等,参见实现示例。

语言 $\texttt{int}$ $\texttt{int64}$ $\texttt{int[]}$ 数组$a$的长度 $\texttt{string}$
$\texttt{C++}$$\texttt{int}$$\texttt{long long}$$\texttt{std::vector<int>}$$\texttt{a.size()}$$\texttt{std::string}$

时间限制:$1\texttt{s}$

空间限制:$268\texttt{MB}$

下载

样例数据下载