← 返回题目列表

AtCoder · discovery_2016_qual_c

C. 自己创建令人惊叹的字符串!

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

問題文

您正在接受 DISCO 的采访。 面试官问你“一个仅由小写英文字母组成的字符串。” S ,所以有 3 来自类型操作 1 只需选择一个并执行即可。 我面临的挑战是“ K 请创建一个你能想到的令人惊叹的字符串。”

允许以下操作: 3 一。

  1. 文字列 S 的 i(1≦i≦|S|) 删除第一个字符。
  2. 文字列 S 的 i(1≦i≦|S|) 将第一个字符替换为另一个小写字母。
  3. 文字列 S 的 i(1≦i≦|S|+1) 将您最喜欢的小写字母插入第一个字符。

你是 K 我决定通过在一次操作中可以创建的字符串中按字典顺序创建最小的字符串来给面试官一个惊喜。

这里是一个字符串 X , |X| 是一个字符串 让它代表 X 的长度。
另外,某个字符串 对于 s=s_1s_2s_3...s_n 和 我讨厌 t=t_1t_2t_3...t_m ,当满足以下任一条件时,进行字典序比较 据说 s<t 。

  • 一些整数 在 i(1≦i≦min(n,m)) , 1≦j<i 的任意整数 对于 j 中 s_j = t_j 成立,并且 s_i<t_i 成立。
  • 任意整数 关于 i(1≦i≦min(n,m)) 关于 s_i = t_i 成立,并且 n<m 成立。

入力

输入是按以下格式从标准输入给出的。

S
K
  • 1 面试官在第 1 行给出的仅由小写字母组成的字符串 S (2≦|S|≦300,000) 。
  • 2 一个整数,表示必须在线执行的操作数 K (1≦K≦|S|-1) 。

出力

S 从 K 通过运算可以创建的字符串中,按字典序排列最小的字符串是 1 行输出。不要忘记最后的换行符。 如果正确答案是满足

部分点

针对此问题设置了部分分数。

  • 2≦|S|≦10, 1≦K≦min(|S|-1,4) 的数据集 10 点。
  • 2≦|S|≦200的数据集,则进一步 10 点。
  • 2≦|S|≦1,000的数据集,则进一步 20 点。
  • 2≦|S|≦300,000的数据集,则进一步 60 给出积分,总分 获得 100 点。 在

入力例 1

abc
1

出力例 1

aabc
  • S 开头 插入了a的字符串 可以在aabc是 存在 1 操作中创建的按字典顺序排列的最小字符串。
  • 在这种情况下, 满足第 1 个部分点的约束。

入力例 2

abc
2

出力例 2

a
  • S 的 2 性格和 3 删除第一个字符的字符串a是 存在 2 操作中创建的按字典顺序排列的最小字符串。
  • 在这种情况下, 满足第 1 个部分点的约束。

入力例 3

acb
1

出力例 3

aab
  • S 的 2 带有替换字符的字符串aab是 存在 1 操作中创建的按字典顺序排列的最小字符串。
  • 在这种情况下, 满足第 1 个部分点的约束。