← 返回题目列表

AtCoder · abc301_d

G. 位掩码

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

分数: 400 点

问题陈述

给你一个整数 N 和一个字符串 S 组成 0, 1,和 ?。 让 T 是通过替换每个值可以获得的一组值 ? in S 与 0 or 1 并将结果解释为二进制整数。 例如,如果 S= ?0?,我们有 T=\lbrace 000_{(2)},001_{(2)},100_{(2)},101_{(2)}\rbrace=\lbrace 0,1,4,5\rbrace.

打印(作为十进制整数)中的最大值 T 小于或等于 N。 如果 T 不包含小于或等于的值 N,打印 -1 代替。

约束

  • S 是一个由以下组成的字符串 0, 1,和 ?.
  • 的长度 S 介于 1 和 60,包括在内。
  • 1\leq N \leq 10^{18}
  • N 是一个整数。

输入

输入由标准输入按以下格式给出:

S
N

输出

打印答案。


示例输入 1

?0?
2

示例输出 1

1

如问题陈述所示, T=\lbrace 0,1,4,5\rbrace。 其中, 0 和 1 小于或等于 N,所以你应该打印其中最大的一个, 1.


示例输入 2

101
4

示例输出 2

-1

我们有 T=\lbrace 5\rbrace,不包含小于或等于的值 N.


示例输入 3

?0?
1000000000000000000

示例输出 3

5