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 结果汇总起来，就得到一份记录。考虑是否存在一组 $(a', b')$，能够针对相同输入产生与这份记录完全一致的 Yes/No 结果。

• 如果无论选择什么 $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