Pista 1

Cada palabra que Firulais puede ladrar tiene exactamente dos caracteres. Al concatenar varias palabras, las posibles subcadenas de longitud 2 aparecen dentro de una misma palabra, o entre el segundo carácter de una palabra y el primero de la siguiente.

Pista 2

Para que la contraseña \(P = P[0]P[1]\) aparezca como subcadena, basta con que ocurra uno de estos dos casos:

• exista una palabra que sea exactamente igual a P, o
• exista alguna palabra cuyo segundo carácter sea P[0] y otra cuyo primer carácter sea P[1], de modo que al concatenarlas se forme P.

Solución

Se analizan las palabras conocidas por Firulais para verificar si es posible formar la contraseña \(P\) como subcadena.

Existen dos escenarios en los que el celular puede desbloquearse:

• Coincidencia directa
  Si alguna de las palabras es exactamente igual a \(P\), entonces Firulais puede ladrarla y desbloquear el celular.

• Coincidencia por concatenación
  Si no existe una coincidencia directa, se busca lo siguiente:

  • una palabra cuyo segundo carácter coincida con \(P[0]\), y
  • una palabra cuyo primer carácter coincida con \(P[1]\).

  Si ambas existen, Firulais puede ladrarlas en ese orden para formar una cadena que contenga \(P\) como subcadena.

Si ocurre al menos uno de estos casos, la respuesta es "SI". En caso contrario, es "NO".

Procedimiento

1. Leer la contraseña \(P\).
2. Leer el número de palabras \(N\).
3. Para cada palabra:
   • Verificar si es exactamente igual a \(P\).
   • Verificar si su segundo carácter coincide con \(P[0]\).
   • Verificar si su primer carácter coincide con \(P[1]\).
4. Si existe coincidencia directa o ambas coincidencias parciales, imprimir "SI".
5. En caso contrario, imprimir "NO".

Implementación en C++

El_Smartphone_de_Osito.cpp

Complejidad

• Tiempo: Para cada caso de prueba, se recorren las N palabras una sola vez, por lo que la complejidad es O(N).

• Memoria: El uso de memoria es O(1), ya que solo se utilizan variables auxiliares de tamaño constante.