Invirtiendo matrices


Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type
Allowed languages
C++

A Humberto le regalaron dos matrices bidimensionales A y B del mismo tamaño N \times M llenas de letras minúsculas. Humberto estaba decepcionado de que las matrices fueran diferentes y decidió arreglar eso. Para ello, elige cualquier fila o columna de la matriz A e invierte el orden de los elementos en ella. Pero estas matrices tienen un sistema automático que resulta bastante molesto: cada vez que Humberto invierte la i-ésima fila, el sistema automático invierte la fila (N-i+1)-ésima, y cada vez que Humberto invierte la j-ésima columna, el sistema automático invierte la columna (M-j+1)-ésima. El sistema automático realiza operaciones en la matriz A. Humberto está harto de este sistema automático y pide tu ayuda. Encuentra el mínimo número de operaciones que Humberto debe realizar para que ambas matrices se vuelvan idénticas, o di que es imposible.

Subtareas

Este problema se compone de 7 subtareas, que cumplen con las siguientes restricciones:

  • N = 2, M = 2, tipo = 1. Vale 8 puntos.
  • N \times M \le 10, tipo = 1. Vale 13 puntos.
  • N = 2, tipo = 1. Vale 9 puntos.
  • 3 \le N, N \times M \le 100, tipo = 1. Vale 7 puntos.
  • N \times M \le 1000, tipo = 1. Vale 13 puntos.
  • tipo = 0. Vale 23 puntos.
  • tipo = 1. Vale 27 puntos.

Entrada

La primera línea de la entrada contiene tres enteros no negativos N, M y tipo (N \le M, 1\le N \times M \le 10^6, 0 \le tipo \le 1) --- los lados de las matrices bidimensionales y el tipo del caso de prueba actual. Las siguientes N líneas contienen M letras minúsculas sin espacios en blanco que describen la matriz bidimensional A. Las siguientes N líneas describen la matriz B.

Salida

Imprime "NO" (sin comillas) si la respuesta no existe, de lo contrario imprime "YES" (sin comillas). Para tipo = 1 debe imprimir una segunda línea que contiene el número mínimo de operaciones.

Ejemplo de entrada

2 2 1
ab
ba
ba
ab

Ejemplo de salida

YES
1

Comments


  • 1
    humbertoyusta  commented on Feb. 19, 2024, 3:43 p.m.

    Debido a problemas técnicos con el procesamiento de la salida, se modificará la manera de la salida del problema, se cambiará el texto del problema de acuerdo, si tipo=0 solo hay que decir si es posible resolver el problema o no, por lo que la salida será solo YES o NO, si tipo=1, también habrá que especificar el número optimo K de operaciones para resolver el problema.

    Pedimos disculpas por las molestias causadas y esperen a enviar a que se avise del cambio, estamos trabajando en cambiarlo lo más pronto posible.