#2863. 「IOI2018」组合动作

内存限制:268 MiB 时间限制:1000 ms 题目类型:交互
上传者: spj

题目描述

你在玩一个动作游戏。游戏控制器有 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

输入格式

你需要实现下面的函数:

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

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

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

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

样例

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

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

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

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

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

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

附件压缩包中的文件 sample-01-in.txt 对应于本例。

数据范围与提示

  • 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<q\le N+10 ,你的得分为 95-3(q-N-2)
  • 如果 N+10<q\le 2N+1 ,你的得分为 25
  • 如果 \max\{N+10,2N+1\}<q\le 4N ,你的得分为 5
  • 否则,你的得分为 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