It's Showtime!

네루

플레이어는 게임머신과 게임을 할 수 있습니다!

각 게임머신은 $1$ 이상의 양의 정수 $N$, $N$이하의 양의 정수 $a$, 연산자를 의미하는 문자 $b$로 설정되어 있습니다. 이때 연산자 $b$는 $+$와 $\times$중 하나입니다!

각 게임머신은 정수 $N$은 알려주지만, 정수 $a$와 연산자의 종류 $b$는 알려주지 않습니다. 플레이어는 게임머신에 $1$이상 $N$이하의 정수를 입력할 수 있습니다. 플레이어가 정수를 입력할 때마다 게임머신은 내부 동작에 따라 Yes 혹은 No를 화면에 표시합니다. 내부 동작 과정은 다음과 같습니다.

• 게임머신 내부에 저장되어 있는 값을 $x$라고 합니다. 초기에는 $x = a$입니다.

• 매 라운드마다 플레이어는 정수를 입력할 수 있습니다.

  • 플레이어가 입력한 정수를 $y$라고 하며, $y$는 $1$ 이상 $N$ 이하의 정수이어야 합니다.

플레이어는 연산자 $b$를 맞추는 것이 목표이며 정수 $a$는 알아내지 않아도 됩니다. 최종적으로 연산자 $b$를 알아내게 된다면 라운드 수가 적을 수록 많은 재화를 획득합니다.

아스나는 선내를 돌아다니며 우연히 모든 게임머신의 정보가 적혀있는 쪽지를 주웠다. 이 쪽지에는 모든 게임머신이 각각 어떤 $a$, $b$로 설정되어있는지 쓰여있다. 아스나는 쪽지에 적힌 정보를 이용하여 각 라운드에 입력할 정수를 자유롭게 선택할 수 있으며, 정수를 입력하는 과정에서는 카지노의 의심을 받지 않는다.

연산자 $b$를 바로 맞출 경우 카지노에서 의심받게 되어 쫓겨날 수도 있다고 생각한 아스나는 의심받지 않는 최소한의 라운드만 진행하려고 한다.

아스나가 지금까지 입력한 정수들과 그때마다 나온 Yes/No 결과를 모두 모으면 하나의 기록이 된다. 이 기록과 완전히 동일한 Yes/No 결과를 만들어낼 수 있는 $(a', b')$ 쌍이 존재하는지 생각해 보자.

• 만약 어떤 $a'$를 택하더라도 $b'=+$라면 해당 기록이 불가능하고, $b'=\times$인 경우만 가능하다면 임을 확정할 수 있다.

아스나가 연산자를 정답으로 말할 때에는, 지금까지의 기록이 나올 수 있는 연산자의 종류가 하나뿐일 때에만 의심받지 않는다. 정수 $N$, $a$와 연산자 $b$로 설정된 게임머신이 주어졌을 때, 아스나가 의심받지 않고 정답을 맞출 수 있는 최소 라운드 수를 구해보자.

입력으로 주어지는 $\texttt{*}$는 $\times$를 의미한다.

두 번째 게임머신

• 첫 번째 라운드에 $1$을 입력하면 Yes가 표시된다.

  • 이때 가능한 $(a, b)$ 쌍은 $(1, \times)$, $(2, \times)$, $(3, \times)$, $(1, +)$, $(2, +)$ 이므로 확정할 수 없다.

• 두 번째 라운드에 $1$을 입력하면 Yes가 표시된다.

  • 이때 가능한 $(a, b)$ 쌍은 $(1, \times)$, $(2, \times)$, $$, 이므로 확정할 수 없다.

• 세 번째 라운드에 $1$을 입력하면 Yes가 표시된다.

  • 이때 가능한 $(a, b)$ 쌍은 $(1, \times)$, $(2, \times)$, $$ 이므로 가 임을 확정할 수 있다.

$3$번보다 적게 정수를 넣어서 $b$를 확정할 수 있는 방법은 없다.

시간 제한

1000 ms

메모리 제한

1024 MB

체커

CUSTOM