Задачи
Интерактивное угадывание факториала
Интерактивное угадывание факториала
О нет, это зловещее жюри снова что-то скрывает от Вас, и Вам придется догадаться об этом интерактивно.
На этот раз вам нужно найти целое число $n$. Для этого вы можете задать не более $10$ запросов вида "Какая $k$-я десятичная цифра произведения всех целых чисел от $1$ до $n$ (также известного как факториал и обозначаемого как $n!$)?"
\Interaction{Протокол взаимодействия}
В первой строке содержится целое число $t~(1 \le t \le 100)$ --- количество тестов. Для каждого теста целое число $n$ выбирается заранее. Длина $n!$ не превышает $20000$, поэтому $1 \le n \le 5982$. Вы можете задать не более $10$ запросов вида "\texttt{? k}" $(0 \le k < 20000)$. В ответ на запрос Вы получите одну цифру --- $k$-ю десятичную цифру $n!$ (ответ находится в диапазоне от $0$ до $9$ включительно). Цифры нумеруются с $0$, начиная с наименее значимой цифры. Если $n!$ слишком короткий, и $k$-ой цифры нет, то будет возвращен $0$.
После того как Ваша программа найдет значение $n$, она должна ответить "\texttt{! n}". Если ответ верный, то Вы получите "\textbf{YES}" и должны перейти к следующему тесту или завершить, если это был последний. Если ответ неверный, или Вы пытаетесь угадать, и существует несколько возможных ответов, согласующихся с полученной информацией, то Вы получите "\textbf{NO}". В этом случае Ваше решение получит вердикт "\textbf{Wrong answer}", и Ваш код будет немедленно завершен.
Входные данные #1
2 1 YES 0 2 YES
Выходные данные #1
? 0 ! 1 ? 0 ? 19997 ! 5982