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 ラウンド目に $1$ を入力すると、Yes が表示される。

  • 可能な $(a, b)$ の組は $(1, \times)$、$(2, \times)$、$(3, \times)$、$(1, +)$、$(2, +)$ なので、まだ確定できない。

• 2 ラウンド目に $1$ を入力すると、Yes が表示される。

  • 可能な $(a, b)$ の組は $(1, \times)$、$(2, \times)$、$$、 なので、まだ確定できない。

• 3 ラウンド目に $1$ を入力すると、Yes が表示される。

  • 可能な $(a, b)$ の組は $(1, \times)$、$(2, \times)$、$$ なので、 は と確定できる。

$3$ 回未満の入力で $b$ を確定する方法はない。

実行時間制限

1000 ms

メモリ制限

1024 MB

チェッカー

CUSTOM