logo AlgoBeat OnlineJudge 返回比赛
登录 注册

B. [TopCoder SRM 855] MinesweeperStrings

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较

题目描述

我们称一个长度为 的字符串为扫雷字符串,当且仅当它满足以下条件:

  • 每个字符要么是 *(表示一颗地雷),要么是数字 012
  • 每个数字字符的值必须等于与其相邻的地雷数量(相邻是指在字符串中左右相邻的位置)。

例如,当 时:

  • 0000000 是一个合法的扫雷字符串,没有地雷。
  • ******* 是一个合法的扫雷字符串,全是地雷。
  • 0001*2* 是一个合法的扫雷字符串,有两颗地雷。
  • 0001000 不是一个合法的扫雷字符串,因为中间的 1 相邻的地雷数量不是
  • **0001* 不是一个合法的扫雷字符串,因为最左边的 0 相邻的地雷数量不是
  • 2*1*02* 不是一个合法的扫雷字符串,所有数字都错误。

现在,我们将所有合法的扫雷字符串按照字典序从小到大排序(依据字符的 ASCII 码值进行排序),并从 开始编号。

给定字符串长度 和一个非负整数 ,请找出在这个排序中排在第 位的扫雷字符串。如果不存在编号为 的字符串(即 大于等于总数),则返回一个空字符串。

输入格式

第一行包含一个整数
第二行包含一个整数

输出格式

一个字符串,表示对应的扫雷字符串;如果不存在,返回空字符串。

样例

样例 #1

样例输入 #1

1
0

样例输出 #1

*

样例解释 #1

对于 ,只有两个合法的扫雷字符串。字典序较小的(第 个)是 *


样例 #2

样例输入 #2

1
1

样例输出 #2

0

样例解释 #2

对于 ,字典序较大的(第 个)是 0


样例 #3

样例输入 #3

1
47

样例输出 #3


样例解释 #3

对于 ,只有两个合法的扫雷字符串,不存在第 个,所以返回空字符串。


样例 #4

样例输入 #4

7
71

样例输出 #4

0001*2*

样例解释 #4

老朋友 0001*2* 在所有长度为 的合法扫雷字符串中排在第 位。

数据范围与提示

  • 字符 *012 的 ASCII 码分别为
  • 在大多数编程语言中,内置的字符串比较运算符就是按字典序进行的。

数据范围