Minus Operator

시간 제한2초메모리 제한2048 MB

요약

E ::= x | (E - E) 형태의 숨겨진 이진 수식을 추측한다. n개의 잎에 비트를 대입하는 질의를 하면 마이너스 연산으로 계산한 값 0 또는 1을 돌려받는다.

난이도: 보통10점 중 7점
유형: 분할 정복, 재귀, 트리, 수학
정답자: 아직 제출이 없습니다

문제

The minus operator on binary values $a$ and $b$ is defined by $(a − b) = 1$ if $a = 1$ and $b = 0$ ; otherwise, $(a − b) = 0$ . Also, the syntax of an expression is defined as follows. Here, x, parentheses, and the minus are terminal symbols, and $E$ is the start symbol.

$E ::=$ x $| (E − E)$

The judge program possesses an expression adhering to $E$ . The expression is hidden from you. At the start, you are only provided with the number of terminal symbols x in the expression, denoted by $n$ .

Your task is to guess the expression by making a limited number of queries.

In a single query, you specify a binary string $S$ of length $n$ . The judge program then temporarily replaces each occurrence of the $i$ -th terminal symbol x from the left with $S\_i$ , for $i = 1, \dots , n$ , and evaluates the replaced expression based on the definition of the minus operator. After that, the judge program returns the evaluated value to you, which is either $0$ or $1$ .

예제2

예제 1
입력
```
3

0
```
예상 출력
```
query 111

answer ((x-x)-x)
```

예제 2

입력

예상 출력


query 0000

query 1001

answer ((x-x)-(x-x))