Este es el código de golf. El ganador es el código válido con el menor número de bytes.

Desafío

Dadas las entradas M y N , el ancho y la altura de una cuadrícula rectangular de cuadrados, genera un polígono que satisface lo siguiente:

• Los bordes del polígono están formados solo por bordes cuadrados: no hay bordes diagonales, todos son verticales u horizontales.
• El polígono no tiene agujeros: se puede llegar a cada cuadrado fuera del polígono mediante pasos ortogonales en cuadrados fuera del polígono, comenzando desde un cuadrado fuera del polígono en el límite exterior del rectángulo.
• El polígono no tiene auto-intersección: de los bordes cuadrados que se encuentran en un vértice, no más de 2 pueden ser parte del perímetro del polígono.
• El polígono está conectado: cualquier cuadrado en el polígono debe ser accesible desde cualquier otro cuadrado en el polígono a través de pasos ortogonales que permanecen dentro del polígono.
• El polígono tiene el perímetro máximo posible: de acuerdo con la fórmula que se muestra a continuación.

Su código debe funcionar para M y N de 1 a 255.

Fórmula para perímetro máximo

El desafío aquí es encontrar el más golfable de esos polígonos con el perímetro máximo. El perímetro máximo en sí mismo siempre está definido por la fórmula:

Esto es cierto porque para un perímetro máximo cada vértice cuadrado debe estar en el perímetro. Para un número impar de vértices esto no es posible y lo mejor que se puede lograr es un vértice menos (ya que el perímetro siempre es par).

Salida

Imprima la forma como una cadena de caracteres separados por nueva línea ( N filas de exactamente M caracteres). Aquí estoy usando espacio para cuadrados fuera del polígono y '#' para cuadrados dentro del polígono, pero puede usar cualquiera de los dos caracteres visualmente distintos, siempre que su significado sea consistente para todas las entradas.

Puede incluir hasta una nueva línea inicial y hasta una nueva línea final.

Si lo desea, puede generar M filas de exactamente N caracteres, y puede elegir M por N para algunas entradas y N por M para otras.

Ejemplos

Inválido debido a un agujero:

###
# #
###

Inválido debido a la intersección (tocando en diagonal: un vértice con 4 bordes cuadrados en el perímetro) y, por cierto, un agujero:

##
# #
###

No válido por estar desconectado:

#
# #
  #

Polígono válido de perímetro máximo:

# #
# #
###

Créditos

Inicialmente subestimé la rapidez con la que se podía calcular el valor del perímetro máximo, y solo iba a pedir ese valor como la salida. Gracias a las personas maravillosamente útiles en el chat por explicar cómo calcular el perímetro máximo para N y M arbitrarios y ayudar a convertir esto en un desafío que durará más de una respuesta ...

Específicamente gracias a:

Sparr , Zgarb , feersum , jimmy23013 .

CJam, 47 bytes

l~_2%{\}|_'#:H*@({N+1$(2md\HS+*H+\SH+R=*++}fR\;

Pruébalo en línea

Explicación:

l~      Get and convert input.
_2%     Calculate second value modulo 2.
{\}|    If value is even, swap the two inputs. This puts odd on top if one is odd.
_'#:H*  Create top row of all # signs. Also save away # character as shortcut for later.
@(      Pull number of rows to top, and decrement because first is done.
{       Start loop over rows.
N+      Add newline.
1$      Copy row length to top of stack.
(2md    Decrement, and calculate mod/div with 2.
\       Swap mod and div, will use div first.
HS+     "# "
*       Repeat it based on div 2 of row length.
H+      Add one more #.
\       Swap mod of earlier division to top.
SH+     " #"
R=      Pick space or # depending on even/odd row number.
*       Repeat 0 or 1 times depending on mod 2 of row length.
+       Add the possible extra character to line.
+       Add line to result.
}fR     End of for loop over lines.
\;      Remove row length from stack, leaving only result string.

Hay dos casos principales para el resultado. Si al menos uno de los tamaños es impar, el patrón es un simple "rastrillo". Por ejemplo, para entrada 7 6:

#######
# # # #
# # # #
# # # #
# # # #
# # # #

Si ambos tamaños son pares, hay una columna adicional donde cada segundo cuadrado está "activado". Por ejemplo, para entrada 8 6:

########
# # # # 
# # # ##
# # # # 
# # # ##
# # # # 

Ahora, para mostrar que estos patrones alcanzan el máximo teórico del perímetro como se indica en la descripción del problema, debemos confirmar que el primer patrón tiene un perímetro (M + 1) * (N + 1)y el segundo el mismo valor menos 1.

Para el primer patrón, tenemos para el perímetro, con Muna dimensión impar:

1. M para el borde superior
2. 2 en el lado de la fila superior.
3. (M - 1) / 2 para los espacios entre los dientes.
4. (M + 1) / 2dientes con perímetro 2 * (N - 1) + 1cada uno.

Esto se suma a:

M + 2 + (M - 1) / 2 + (M + 1) / 2 * (2 * (N - 1) + 1) =
M + 2 + (M - 1) / 2 + (M + 1) * (N - 1) + (M + 1) / 2 =
2 * M + 2 + (M + 1) * (N - 1) =
(M + 1) * 2 + (M + 1) * (N - 1) =
(M + 1) * (N + 1)

Para el segundo caso donde ambos My Nson pares, el perímetro se suma desde:

1. M para el borde superior
2. 2 en el lado de la fila superior.
3. M / 2 para el # abierto en la fila superior.
4. M / 2dientes con perímetro 2 * (N - 1) + 1cada uno para los dientes lisos.
5. El diente más a la derecha tiene 2 * (N / 2 - 1)piezas perimetrales adicionales para las irregularidades.

Agregando esto todo junto:

M + 2 + M / 2 + (M / 2) * (2 * (N - 1) + 1) + 2 * (N / 2 - 1) =
M + 2 + (M / 2) * (2 * (N - 1) + 2) + N - 2 =
M + M * N + N =
(M + 1) * (N + 1) - 1

Ruby, Rev 1, 66

->(m,n){n.times{|i|puts ("#"*m**(1-i%2)).rjust(m,i>n-2?"# ":" ")}}

Se usó el aumento mal poder 0 o 1 para decidir si m #se imprimirá 1 o 's.

Se usa >para probar la última fila en lugar de ==.

¡No se puede deshacer del espacio después de los puestos ni corchetes!

Ruby, Rev 0, 69

->(m,n){n.times{|i|puts ("#"*(i%2==0?m:1)).rjust(m,i==n-1?"# ":" ")}}

Esta es una función lambda anónima. Úselo así:

f=->(m,n){n.times{|i|puts ("#"*(i%2==0?m:1)).rjust(m,i==n-1?"# ":" ")}}

M=gets.to_i
N=gets.to_i
f.call(M,N)

Al final, después de preguntar si M y N podrían intercambiarse, no lo necesitaba.

Salidas típicas para N impar. Si eliminamos el contenido #por su cuenta en el lado derecho, claramente tendremos (N + 1) (M + 1). Al incluirlos para unir la forma, se eliminan 2 cuadrados de perímetro horizontal y se agregan 2 cuadrados de perímetro vertical, por lo que no hay cambio.

Aquí confiamos en la expresión "#"*(i%2==0?m:1)para dar filas alternas de M #símbolos y un #símbolo, y justificar a la derecha a M caracteres.

5                        6
5                        5
#####                    ######
    #                         #
#####                    ######
    #                         #
#####                    ######

Salidas típicas para N pares. 5 6claramente tiene el mismo perímetro 6 5o un incremento de M + 1 = 6 en comparación con la 5 5adición del perímetro vertical debido a la almena de la fila inferior. 6 6tiene lo mismo que 6 5más un incremento de (M + 1) -1 = 6 en el perímetro vertical. Por lo tanto, están de acuerdo con la fórmula.

5                        6
6                        6
#####                    ######
    #                         #
#####                    ######
    #                         #
#####                    ######
# # #                    # # ##

Es muy útil que Ruby's le rjustpermita especificar el relleno que se usará para las celdas vacías. Normalmente, el relleno se establece en " "pero para la última fila cambiamos a "# "(tenga en cuenta que el relleno solo será necesario en la última fila si N es par. Donde N es impar, la última fila estará completa y no habrá justificación, por lo que no verá las almenas).

Compruébalo aquí.

C, 109 97 bytes y prueba de corrección

Estaba escribiendo mi solución, pero @steveverrill me ganó. Pensé que lo compartiría de todos modos, ya que incluí una prueba de corrección para la estrategia utilizada.

Código reducido:

m,n,x;main(){for(scanf("%i%i",&m,&n); n;)putchar(x<m?"# "[x%2*(++x^m||~n&1)&&n^1]:(x=0,n--,10));}

Antes de la reducción:

m,n,x;

main(){
    for(scanf("%i%i",&m,&n); n;) 

        /* If x == m, prints out a newline, and iterates outer 
         * loop (x=0,n--) using comma operator.
         * Otherwise, paints a '#' on :
         *     Every even column (when x%2 is 0)
         *     On odd columns of the last row (++x^m||~n&1 is 0)
         *     On the first row (when n^1 is 0)
         * And a ' ' on anything else (when predicate is 1) */
        putchar(x<m?"# "[x%2*(++x^m||~n&1)&&n^1]:(x=0,n--,10));
}

Estrategia y prueba:

Suponiendo la exactitud de la ecuación del perimitador máximo (M + 1) (N + 1) - ((M + 1) (N + 1)) mod 2 , lo siguiente explica la estrategia óptima utilizada y demuestra su corrección por inducción:

Para M impar, dibujamos una forma de mano con dedos M / 2 + 1, por ejemplo:

3x2
# # 
###

5x3
# # #
# # #
#####

Ahora demostramos que esta estrategia es óptima para todos los M extraños por inducción:

Caso base: M = N = 1
La celda individual está llena. La solución es correcta ya que (1 + 1) * (1 + 1) = 2 * 2 = 4, y un cuadrado tiene 4 lados.

Inducción en el ancho:
suponga que la estrategia de forma de mano funciona para (N, M-2) donde M es impar, es decir, su perímetro es óptimo y es (N + 1) (M - 2 + 1) + ((M -1) (N + 1)) mod 2 . Ahora mostramos que funcionará para (N, M) .

El proceso de agregar un dedo elimina un borde del polígono y agrega 3 + 2N . Por ejemplo:

 5x3 -> 7x3
 # # # $
 # # # $
 #####$$

Combinando esto con nuestra hipótesis de que el perímetro anterior era óptimo, el nuevo perímetro es:

(N + 1)*(M - 2 + 1) - ((M+1)*(N+1)) mod 2 - 1 + 3 + 2*N
(N + 1)*(M + 1) - ((M-1)*(N+1)) mod 2 - 2(N + 1) - 1 + 3 + 2*N
(N + 1)*(M + 1) - ((M-1)*(N+1)) mod 2

Como estamos tratando con la aritmética del módulo 2,

((M-1)*(N+1)) mod 2 = ((M+1)*(N+1)) mod 2

Por lo tanto, probar que aumentar el ancho agregando dedos conduce a un perímetro óptimo.

Inducción en altura:
suponga que la estrategia de forma de mano funciona para (N-1, M) , donde M es impar, es decir, su perímetro es óptimo y es N (M + 1) + ((M + 1) N) mod 2 . Ahora mostramos que funcionará para (N, M) .

Aumentar la altura de la mano simplemente alarga los dedos, ubicados en el primer índice y en todos los demás. Para cada aumento de altura, cada dedo agrega dos al perímetro, y hay (M + 1) / 2 dedos, por lo tanto, un aumento en N conduce a un aumento de 2 (M + 1) / 2 = M + 1 en el perímetro.

Combinando esto con la hipótesis, tenemos que el nuevo perímetro es:

N*(M + 1) + ((M+1)*N) mod 2 + M + 1
(N + 1)*(M + 1) + ((M+1)*N) mod 2

La aritmética modular nos permite simplificar el último término, de modo que obtengamos:

(N + 1)*(M + 1) + ((M+1)*(N+1)) mod 2

Demostrando que la solución es óptima para todos N> 0 y M> 0 impar.

Incluso para M, completamos el tablero de la misma manera que lo haríamos para M impar, pero agregamos crenelaciones al último segmento, por ejemplo:

4x3
# ##
# # 
####

6x4
# # #
# # ##
# # #
######

Ahora demostramos que esta estrategia es óptima.

Inducción para M par:
Suponga que la solución es correcta para (N, M-1), con M-1 impar (como se demostró en el último caso), que tiene un perímetro óptimo de (N + 1) M - ( M (N + 1)) mod 2 . Ahora mostramos que funcionará para (N, M).

Al igual que al aumentar los dedos, cada almena agrega dos al perímetro del polígono. El número total de crenelaciones es (N + N mod 2) / 2 , para un total de N + N mod 2 agregado al perímetro.

Combinando esto con la hipótesis, tenemos que el nuevo perímetro es:

(N + 1)*M - (M*(N+1)) mod 2 + N + N mod 2
(N + 1)*(M + 1) - (M*(N+1)) mod 2 + N mod 2 - 1
(N + 1)*(M + 1) - (M*(N+1)) mod 2 - (N + 1) mod 2

Tenemos eso

(M*(N+1)) mod 2 - (N + 1) mod 2 = ((M+1)*(N+1)) mod 2

Porque si N es impar, entonces esto se reduce a 0 = 0, y si N es par, se reduce a

- A mod 2 - 1 = -(A + 1) mod 2

Por lo tanto, la estrategia es óptima para todos M, N> 0 .