잃어버린 수

시간 제한3초메모리 제한512 MB

요약

이진법 산술식에서 최대 다섯 개의 읽을 수 없는 점을 숫자, 연산자, 괄호로 채워 문법을 지키면서 결과가 가장 크게 나오는 값을 구한다.

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

문제

때는 3xxx년, 고도로 발달한 문명은 정체기에 접어들었다. 역사가들은 이 상황을 타개하려고 과거의 지혜를 배우기로 했다. 주목한 것은 컴퓨터 태동기의 천재가 남긴 자료이다. 이 자료에는 계산식이 적혀 있고 그 계산 결과를 알고 싶지만, 안타깝게도 일부 글자가 흐려져 읽을 수 없게 되었다. 어쩔 수 없이 계산 결과로 가능한 가장 큰 수를 구하기로 했다. 계산식은 2진수로 적혀 있으며 연산은 덧셈, 뺄셈, 곱셈 세 가지이다. 괄호도 사용되지만 괄호 안이 숫자만인 경우는 없다. 정확히는 다음 BNF로 정의된 문법을 만족해야 한다.

<expression> ::= <number> | <expression> <operation> <expression>
| ( <expression> <operation> <expression> )
<number> ::= <digit> | <number> <digit>
<operation> ::= + | - | *
<digit> ::= 0 | 1

당시 컴퓨터의 계산 능력 한계 때문에 숫자는 0 이상 210 미만의 정수이고 계산 중에도 이 범위를 벗어나지 않는다. 단 계산은 괄호 안을 먼저 하고 곱셈은 덧셈, 뺄셈보다 먼저 한다. 그 외의 경우에는 왼쪽에서 오른쪽으로 계산한다.

입력

입력은 1행으로 이루어지며, 해독해야 할 수식이 하나 주어진다. 수식은 1글자 이상 100글자 이하이다. 하나의 수식에 대해 최대 5글자가 읽히지 않으며 .로 표현된다. 주어지는 수식에 포함되는 문자는 01+-*(). 중 하나이다.

출력

원래 수식으로 가능한 것 중 계산 결과가 최대가 되는 것을 구하고, 계산 결과를 10진법으로 출력하라. 읽히지 않는 글자를 어떻게 채워도 원래 수식으로 가능한 것을 만들 수 없을 때는 -1을 출력하라.

제한

수식은 1글자 이상 100글자 이하
줄바꿈을 제외한 모든 문자는 01+-*(). 중 하나
.의 개수는 5개 이하

예제5

예제 1
입력
```
000
```
예상 출력
```
0
```
예제 2
입력
```
0.0
```
예상 출력
```
2
```
예제 3
입력
```
...
```
예상 출력
```
7
```
예제 4
입력
```
(1.1)
```
예상 출력
```
2
```
예제 5
입력
```
0-1.
```
예상 출력
```
-1
```