QOJ.ac

QOJ

実行時間制限: 3 s メモリ制限: 512 MB 満点: 100 難易度: [表示] インタラクティブ

#194. Contraseña

統計

¡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".

Editorials

IDTypeStatusTitlePosted ByLast UpdatedActions
EditorialOpen Official EditorialQingyu- Download

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.