问题2082--01?串

2082: 01?串

[命题人 : ]
时间限制 : 2 sec  内存限制 : 1024 MB

提交

题目描述

Wangy有一个整数N和一个仅由"0"、"1"和"?"组成的字符串S。令T为通过将S中的每个"?"替换为"0"或"1"并将结果解释为二进制整数所得到的值的集合。例如,如果S=?0?,我们有T={000(2),001(2),100(2),101(2)}={0,1,4,5}。

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

简单来说,就是找出能够通过将S中的"?"替换为"0"或"1"所得到的最大二进制整数,并输出该整数的十进制表示。如果没有满足条件的整数,则输出-1。

输入

第一行一个字符串S(仅由0,1,?组成),第二行一个正整数N(1<=N<=1018)
S的长度x(1<=x<=60)

输出

按照题目要求输出

样例输入 Copy

?0?
2

样例输出 Copy

1

提示

如问题描述所示,T={0,1,4,5}。其中,0和1都小于或等于N,因此你应该打印它们中最大的数,即1。