分数: 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