问题1163--菜哭武的01串

1163: 菜哭武的01串

[命题人 : ]
时间限制 : 1.000 sec  内存限制 : 256 MB

题目描述

天才程序员菜哭武和张老师在玩一个很无聊的游戏,菜哭武有一个由0和1组成的字符串,张老师给菜哭武一个正整数的二进制表示形式,让菜哭武找到一个相同的子序列。这个游戏太无聊了,张老师想知道菜哭武的01串的子序列能构成前多少个整数的二进制形式。
张老师希望你能解决的问题是,已知菜哭武的一个01字符串,找到最大的一个正整数N,这个01串的所有子序列可以构成所有1-N的正整数。
子序列是原字符串当中有序但不一定连续的字符组成的字符串。如01串101有1,0,10,11,01,101一共六个不同的子序列,其中子序列1有两种取法。

输入

输入一行包含一个字符串s(1<=|s|<=1e6,|s|为s的长度),s是一个01字符串。

输出

输出一行,包含一个01字符串t,表示s能构成的1-N的最大整数N,使用二进制表示。如果不能构成任意正整数,输出0。

样例输入 Copy

101

样例输出 Copy

11

提示

101可以构成1(取第一个或第三个字符)、10(取前两个字符)、11(取第一个和第三个字符),但是不能构成100。

输入样例2
011
输出样例2
1
011可以构成1(取第二个或第三个字符),不能构成10

来源/分类