¡Volví a olvidar mi contraseña! Estoy sentado frente a mi computadora tecleando contraseñas incorrectas. Todo lo que recuerdo es que mi contraseña contiene únicamente letras minúsculas. Por suerte, el sistema de inicio de sesión responde con algo más que solo «contraseña incorrecta». También me dice la longitud del prefijo más largo de mi entrada que aparece como una subsecuencia (no necesariamente contigua) en la contraseña. Formalmente, para una contraseña $P = p_1 p_2 \dots p_N$ y una entrada $Q = q_1 q_2 \dots q_N$, la respuesta del sistema de inicio de sesión es el mayor $L$ para el cual existen índices $1 \le k_1 < k_2 < \dots < k_L \le N$ tales que $q_i = p_{k_i}$ para todo $1 \le i \le L$. El sistema también me dice $N$, la longitud de mi contraseña, y $S$, lo que significa que mi contraseña solo utiliza las primeras $S$ letras del alfabeto. Por ejemplo, $S = 4$ significa que mi contraseña solo contiene $\text{a}$, $\text{b}$, $\text{c}$ y $\text{d}$ (pero no necesariamente todas ellas).
¡Por favor, ayúdame a recuperar mi contraseña!
Detalles de implementación
Este problema es interactivo. Debes implementar la función
C: char* guess(int n, int s);
C++: string guess(int n, int s);
- Argumentos: $N$ y $S$ como se describió anteriormente.
- Valor de retorno: la contraseña correcta.
Tu programa puede llamar a la función
C: int query(char* str);
C++: int query(string str);
- Argumento: una cadena de $1$ a $N$ letras de entre las primeras $S$ letras del alfabeto.
- Valor de retorno: un entero entre $0$ y la longitud de
str, que representa la respuesta del sistema de inicio de sesión a tu consulta. - Para evitar errores de compilación, debes declarar esta función usando exactamente el texto anterior, en cualquier lugar del ámbito global antes de llamarla.
- Puedes llamar a esta función como máximo $50\,000$ veces por cada caso de prueba.
Tu programa puede definir funciones adicionales.
Evaluador de ejemplo
Se proporciona un grader.{c,cpp} de ejemplo para que pruebes tu código localmente. El evaluador de ejemplo lee la entrada desde el archivo password.in con el siguiente formato:
- línea $1$: $N$ $S$
- línea $2$: contraseña
Puedes compilar el evaluador junto con tu solución. Luego puedes ejecutar el binario resultante para probar tu estrategia de adivinanza con la entrada dada.
Subtareas
Los casos de prueba pueden evaluarse por grupos. En orden, las subtareas son:
| Subtarea | Porcentaje de puntos | Restricciones de entrada |
|---|---|---|
| 1 | 10% | $N \le S \le 26$; todas las letras de la contraseña son distintas |
| 2 | 20% | $2 \le N \le 100$ y $2 \le S \le 4$ |
| 3 | 20% | $2 \le N \le 2\,000$ y $2 \le S \le 20$ |
| 4 | 30% | $2 \le N \le 3\,500$ |
| 5 | 20% | $2 \le N \le 5\,000$ |
Ejemplos
Sea $\text{aab}$ la contraseña. El evaluador llama a guess(3, 2). El registro de llamadas puede ser
| Llamada | Valor de retorno |
|---|---|
guess("ab") |
2 |
guess("abb") |
2 |
guess("bab") |
1 |
guess("aab") |
3 |
En este punto, guess(3, 2) debería devolver "aab".