LOL P88630

En la jerga de internet, LOL, el acrónimo inglés de “laughing out loud” (riendo a carcajadas) se usa con frecuencia para describir una situación supuestamente divertida. Veamos si este problema os parece divertido...

Dados dos naturales $n$ y $m$, debéis escribir una matriz $n \times m$ con los caracteres ‘L’ y ‘O’, de manera que el número de “LOL”s que contenga sea el máximo posible, contando las apariciones horizontales, verticales y diagonales.

Por ejemplo, para $n = 3$ y $m = 7$ la solución óptima es

LLLLLLL
OOOOOOO
LLLLLLL

con 17 apariciones de “LOL”. Como otro ejemplo, para $n = 1$ y $m = 2$

OL

es una de las cuatro soluciones posibles, todas con ninguna aparición de “LOL”.

Entrada

La entrada consiste en dos naturales $n$ y $m$, ambos entre 1 y 100.

Salida

Sea $q$ el máximo número de “LOL”s que habéis encontrado para esta combinación de $n$ y $m$. Escribid primero una línea con $n$, $m$ y $q$ separadas con un espacio. Escribid a continuación $n$ lineas con $m$ caracteres ‘L’ o ‘O’ cada una. La matriz debe contener exactamente $q$ “LOL”s. Si hay más de una posible matriz, escribid cualquiera de ellas.

Puntuación

Hay 50 juegos de pruebas privados, todos diferentes, que se evalúan independientemente. Para cada uno, si el formato de vuestra salida no es exactamente el requerido, o si $q$ no es exactamente el número de “LOL”s de la matriz escrita, tendréis cero puntos. En otro caso, recibiréis dos puntos si vuestra $q$ es igual (o superior) a la mejor que ha sido capaz de encontrar el autor de este problema para esta combinación de $n$ y $m$.