Infinite Pattern Matching

시간 제한1초메모리 제한256 MB

요약

1, 2, 3, ...을 이진수로 이어 붙인 무한 문자열의 길이 L인 접두사가 A로 끝나는 가장 작은 L을 구한다.

난이도: 보통10점 중 7점
유형: 문자열, 수학, 이분 탐색, 구현
정답자: 아직 제출이 없습니다

문제

Consider the infinite binary string $I$ formed by concatenating the binary representations of all the strictly positive integers in increasing order: $I =$ "11011100...".

You are given a binary string $A$ . Your task is to find the smallest integer $L$ such that $A$ is a suffix of $I\[1 \ldots L]$ .

입력

The only line of input contains the binary string $A$ , $1 \le \left\lvert A \right\rvert \le 55$ .

출력

Print a single line with a single integer: the number $L$ .

예제2

예제 1
입력
```
11
```
예상 출력
```
2
```
예제 2
입력
```
011011
```
예상 출력
```
42
```