Isso é código de golfe. O vencedor é o código válido com o menor número de bytes.

Desafio

Dadas as entradas M e N , a largura e a altura de uma grade retangular de quadrados, produz um polígono que satisfaz o seguinte:

• As arestas do polígono são compostas apenas por arestas quadradas: não há arestas diagonais - todas são verticais ou horizontais.
• O polígono não possui furos: todos os quadrados fora do polígono podem ser alcançados por etapas ortogonais em quadrados fora do polígono, começando de um quadrado fora do polígono no limite externo do retângulo.
• O polígono não tem auto-interseção: das arestas quadradas que se encontram em um vértice, não mais que 2 podem fazer parte do perímetro do polígono.
• O polígono está conectado: qualquer quadrado no polígono deve ser acessível a partir de qualquer outro quadrado no polígono por meio de etapas ortogonais que permanecem dentro do polígono.
• O polígono tem o perímetro máximo possível: de acordo com a fórmula mostrada abaixo.

Seu código deve funcionar para M e N de 1 a 255.

Fórmula para o perímetro máximo

O desafio aqui é encontrar o polígono mais jogável com o perímetro máximo. O próprio perímetro máximo é sempre definido pela fórmula:

Isso é verdade porque, para um perímetro máximo, todo vértice quadrado deve estar no perímetro. Para um número ímpar de vértices, isso não é possível e o melhor que pode ser alcançado é um vértice a menos (uma vez que o perímetro é sempre par).

Resultado

Produza a forma como uma sequência de caracteres separados por nova linha ( N linhas de exatamente M caracteres). Aqui, estou usando espaço para quadrados fora do polígono e '#' para quadrados dentro do polígono, mas você pode usar dois caracteres visualmente distintos, desde que o significado deles seja consistente para todas as entradas.

Você pode incluir até uma nova linha inicial e até uma nova linha final.

Se desejar, você pode enviar M linhas com exatamente N caracteres e escolher M por N de saída para algumas entradas e N por M de saída para outras.

Exemplos

Inválido devido a um furo:

###
# #
###

Inválido devido à interseção (tocando na diagonal - um vértice com 4 arestas quadradas no perímetro) e, aliás, um buraco:

##
# #
###

Inválido por ter sido desconectado:

#
# #
  #

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

# #
# #
###

Créditos

Inicialmente, subestimei a rapidez com que o valor do perímetro máximo podia ser calculado e pedia apenas esse valor como saída. Agradecemos às pessoas maravilhosamente úteis no chat por explicar como calcular o perímetro máximo para N e M arbitrários e ajudar a transformar isso em um desafio que durará mais de uma resposta ...

Especialmente graças a:

Sparr , Zgarb , feersum , jimmy23013 .

CJam, 47 bytes

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

Experimente online

Explicação:

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.

Existem dois casos principais para o resultado. Se pelo menos um dos tamanhos for ímpar, o padrão é um "ancinho" simples. Por exemplo, para entrada 7 6:

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

Se os dois tamanhos forem pares, há uma coluna extra em que cada segundo quadrado está "ativado". Por exemplo, para entrada 8 6:

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

Agora, para mostrar que esses padrões atingem o máximo teórico do perímetro, conforme indicado na descrição do problema, precisamos confirmar que o primeiro padrão possui perímetro (M + 1) * (N + 1)e o segundo o mesmo valor menos 1.

Para o primeiro padrão, temos o perímetro, com Muma dimensão ímpar:

1. M para a borda superior.
2. 2 no lado da linha superior.
3. (M - 1) / 2 para as lacunas entre os dentes.
4. (M + 1) / 2dentes com perímetro 2 * (N - 1) + 1cada.

Isso resulta em:

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 o segundo caso em que ambos Me Nsão pares, o perímetro é adicionado a partir de:

1. M para a borda superior.
2. 2 no lado da linha superior.
3. M / 2 para o # aberto na linha superior.
4. M / 2dentes com perímetro 2 * (N - 1) + 1cada um para os dentes lisos.
5. O dente mais à direita tem um 2 * (N / 2 - 1)perímetro extra para os jaggies.

Adicionando tudo isso 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

Rubi, Rev. 1, 66

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

Utilizado aumentando ma potência 0 o 1 para decidir se 1 ou m #'s serão impressos.

Usado >para testar a última linha em vez de ==.

Não é possível se livrar do espaço depois dos put, nem dos colchetes!

Ruby, Rev. 0, 69

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

Esta é uma função lambda anônima. Use-o assim:

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)

No final, depois de perguntar se M e N poderiam ser trocados, eu não precisava disso.

Saídas típicas para N ímpares. Se deletarmos #por conta própria no lado direito, teremos claramente (N + 1) (M + 1). A inclusão deles para unir a forma remove 2 quadrados do perímetro horizontal e adiciona 2 quadrados do perímetro vertical, para que não haja alterações.

Aqui contamos com a expressão "#"*(i%2==0?m:1)para fornecer linhas alternadas de #símbolos M e um #símbolo e justificar à direita para M caracteres.

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

Saídas típicas para N pares. 5 6tem claramente o mesmo perímetro 6 5ou um incremento de M + 1 = 6 em comparação com a 5 5adição do perímetro vertical devido à ameixa da linha inferior. 6 6tem o mesmo que 6 5mais um incremento de (M + 1) -1 = 6 no perímetro vertical. Assim, eles estão de acordo com a fórmula.

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

É muito útil que o Ruby rjustpermita especificar o preenchimento a ser usado nas células vazias. Normalmente, o preenchimento está definido como, " "mas para a última linha, mudamos para "# "(observe que o preenchimento só será necessário na última linha se N for par. Onde N é ímpar, a última linha será concluída e não haverá justificativa; portanto, você não verá as ameias.)

Confira aqui.

C, 109 97 bytes e prova de correção

Eu estava escrevendo minha solução, mas @steveverrill me superou. Eu pensei em compartilhar tudo da mesma forma, pois incluí uma prova de correção para a estratégia usada.

Código reduzido:

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 da redução:

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));
}

Estratégia e Prova:

Assumindo a exatidão da equação do perímetro máximo (M + 1) (N + 1) - ((M + 1) (N + 1)) mod 2 , o seguinte explica a estratégia ideal usada e comprova sua correção por indução:

Para o ímpar M, desenhamos uma forma semelhante à mão com dedos M / 2 + 1, por exemplo:

3x2
# # 
###

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

Agora provamos que essa estratégia é ideal para todos os M ímpares por indução:

Caso base: M = N = 1
A célula única é preenchida. A solução está correta desde (1 + 1) * (1 + 1) = 2 * 2 = 4, e um quadrado tem 4 lados.

Indução na largura:
Suponha que a estratégia de forma da mão funcione para (N, M-2) onde M é ímpar, ou seja, seu perimitro é ideal e é (N + 1) (M - 2 + 1) + ((M -1) (N + 1)) mod 2 . Agora mostramos que ele funcionará para (N, M) .

O processo de adição de um dedo remove uma borda do polígono e adiciona 3 + 2N . Por exemplo:

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

Combinando isso com nossa hipótese de que o perímetro anterior era ideal, o novo perímetro é:

(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 lidando com aritmética do módulo 2,

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

Assim, provar que aumentar a largura adicionando dedos leva a um perímetro ideal.

Indução na altura:
suponha que a estratégia de forma da mão funcione para (N-1, M) , onde M é ímpar, ou seja, seu perímetro é ideal e é N (M + 1) + ((M + 1) N) mod 2 . Agora mostramos que ele funcionará para (N, M) .

Aumentar a altura da mão apenas alonga os dedos, localizados no primeiro e em qualquer outro índice x. Para cada aumento de altura, cada dedo adiciona dois ao perímetro, e existem (M + 1) / 2 dedos, portanto, um aumento em N leva a um aumento de 2 (M + 1) / 2 = M + 1 no perímetro.

Combinando isso com a hipótese, temos que o novo perímetro é:

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

A aritmética modular nos permite simplificar o último termo, para que possamos obter:

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

Provando que a solução é ideal para todos os N> 0 e ímpares M> 0.

Para M uniforme, preenchemos o quadro da mesma forma que para M ímpar, mas adicionamos ameias ao último segmento, por exemplo:

4x3
# ##
# # 
####

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

Agora, provamos que essa estratégia é ótima.

Indução para M par:
Suponha que a solução esteja correta para (N, M-1), com M-1 ímpar (como foi comprovado no último caso), que possui um perímetro ideal de (N + 1) M - ( M (N + 1)) mod 2 . Agora mostramos que ele funcionará para (N, M).

Como aumentar os dedos, cada amolamento adiciona dois ao perímetro do polígono. O número total de ameias é (N + N mod 2) / 2 , para um total de perímetro N + N mod 2 adicionado.

Combinando isso com a hipótese, temos que o novo perímetro é:

(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

Nós temos isso

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

Porque se N é ímpar, reduz para 0 = 0 e, se N é par, reduz para

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

Portanto, a estratégia é ideal para todos M, N> 0 .