logo AlgoBeat OnlineJudge
登录 注册

#214658. [RMI 2018] 密码 / Password

内存限制:512 MiB 时间限制:3000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

翻译来自于 LibreOJ

在洛谷提交本题时,请使用不低于 C++17 的语言标准,并且声明函数:

int query(string str);

你不应引入外部头文件。


题目译自 Romanian Master of Informatics 2018 Day1 T2 「Password

你又忘记了自己的密码!现在,你正坐在电脑前,尝试输入各种密码,只记得密码只包含小写字母。幸运的是,登录系统不仅会提示“密码错误”,还会告诉你输入的密码中最长的前缀长度,这个前缀作为密码的一个(不一定连续的)子序列出现。形式上,对于密码 和输入 ,系统返回最大的 ,满足存在编号 ,使得对于所有 。系统还会告诉你 (密码长度)和 (密码仅使用字母表的前 个字母)。例如, 意味着密码只包含 abcd(但不一定全包含)。

请帮助你找回密码!

输入格式

这是一个交互题。你需要实现以下函数:

string guess(int n, int s);
  • 参数,如上所述。
  • 返回值:正确的密码。

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

int query(string str);
  • 参数:一个长度为 的字符串,包含字母表前 个字母中的字符。
  • 返回值:一个介于 和字符串长度之间的整数,表示登录系统对你的查询的回答。
  • 为避免编译错误,你应在全局作用域内使用上述确切声明,在调用前定义。
  • 每个测试点最多调用该函数 次。

你的程序可以定义其他辅助函数。

我们提供了示例评分程序 grader.{c,cpp},供你在本地测试代码。评分程序从文件 password.in 读取输入,格式如下:

  • 行:
  • 行:密码

你可以将评分程序与你的代码一起编译,然后运行生成的可执行文件,以测试你的猜测策略对给定输入的表现。

样例

样例输入 1


样例输出 1


数据范围与提示

样例

假设密码为 aab。评分程序调用 guess(3, 2)。调用日志可能如下:

调用 返回值
query("ab")
query("abb")
query("bab")
query("aab")

此时,guess(3, 2) 应返回 "aab"

数据范围

对于所有输入数据,满足:

  • 每个测试点最多调用 query 函数

详细子任务附加限制及分值如下表所示。

子任务 分值 附加限制
,密码中的所有字母互不相同