Я снова забыл свой пароль! Я сижу за компьютером и ввожу неправильные пароли. Всё, что я помню, — это то, что мой пароль состоит только из строчных букв. К счастью, система входа отвечает не просто «неверный пароль». Она также сообщает мне длину наибольшего префикса моего ввода, который встречается в пароле как (не обязательно непрерывная) подпоследовательность. Формально, для пароля $P = p_1 p_2 \dots p_N$ и ввода $Q = q_1 q_2 \dots q_N$ ответом системы входа является наибольшее $L$, для которого существуют индексы $1 \le k_1 < k_2 < \dots < k_L \le N$ такие, что $q_i = p_{k_i}$ для всех $1 \le i \le L$. Система также сообщает мне $N$ — длину моего пароля, и $S$, означающее, что в моём пароле используются только первые $S$ букв алфавита. Например, $S = 4$ означает, что мой пароль содержит только буквы $\text{a}$, $\text{b}$, $\text{c}$ и $\text{d}$ (но не обязательно все из них).
Пожалуйста, помогите мне восстановить мой пароль!
Детали реализации
Это интерактивная задача. Вам необходимо реализовать функцию
C: char* guess(int n, int s);
C++: string guess(int n, int s);
- Аргументы: $N$ и $S$, как описано выше.
- Возвращаемое значение: правильный пароль.
Ваша программа может вызывать функцию
C: int query(char* str);
C++: int query(string str);
- Аргумент: строка длины от $1$ до $N$, состоящая из букв среди первых $S$ букв алфавита.
- Возвращаемое значение: целое число от $0$ до длины
str, представляющее ответ системы входа на ваш запрос. - Во избежание ошибок компиляции вы должны объявить эту функцию, используя в точности приведённый выше текст, в любом месте глобальной области видимости перед её вызовом.
- Вы можете вызвать эту функцию не более $50\,000$ раз в каждом тесте.
Ваша программа может определять дополнительные функции.
Пример грейдера
Для локального тестирования вашего кода предоставляется пример grader.{c,cpp}. Пример грейдера считывает входные данные из файла password.in в следующем формате:
- строка $1$: $N$ $S$
- строка $2$: пароль
Вы можете скомпилировать грейдер вместе с вашим решением. Затем вы можете запустить полученный исполняемый файл, чтобы протестировать вашу стратегию угадывания на заданных входных данных.
Подзадачи
Тесты могут оцениваться группами. По порядку подзадачи таковы:
| Подзадача | Доля баллов | Ограничения на входные данные |
|---|---|---|
| 1 | 10% | $N \le S \le 26$; все буквы в пароле различны |
| 2 | 20% | $2 \le N \le 100$ и $2 \le S \le 4$ |
| 3 | 20% | $2 \le N \le 2\,000$ и $2 \le S \le 20$ |
| 4 | 30% | $2 \le N \le 3\,500$ |
| 5 | 20% | $2 \le N \le 5\,000$ |
Примеры
Пусть пароль равен $\text{aab}$. Грейдер вызывает guess(3, 2). Протокол вызовов может выглядеть так:
| Вызов | Возвращаемое значение |
|---|---|
guess("ab") |
2 |
guess("abb") |
2 |
guess("bab") |
1 |
guess("aab") |
3 |
В этот момент guess(3, 2) должна вернуть "aab".