To jest kod golfowy. Zwycięzcą jest prawidłowy kod o najmniejszej liczbie bajtów.

Wyzwanie

Przy danych wejściowych M i N szerokość i wysokość prostokątnej siatki kwadratów daje wielokąt spełniający następujące kryteria:

• Krawędzie wielokątów składają się tylko z kwadratowych krawędzi: nie ma krawędzi ukośnych - wszystkie są pionowe lub poziome.
• Wielokąt nie ma otworów: do każdego kwadratu poza wielokątem można dotrzeć prostopadłymi krokami na kwadratach poza wielokątem, zaczynając od kwadratu poza wielokątem na zewnętrznej granicy prostokąta.
• Wielokąt nie ma własnego przecięcia: kwadratowych krawędzi spotykających się w wierzchołku nie więcej niż 2 mogą stanowić część obwodu wielokąta.
• Wielokąt jest połączony: każdy kwadrat w wielokącie musi być osiągalny z dowolnego innego kwadratu w wielokącie poprzez ortogonalne kroki, które pozostają w obrębie wielokąta.
• Wielokąt ma maksymalny możliwy obwód: zgodnie ze wzorem pokazanym poniżej.

Twój kod musi działać dla M i N od 1 do 255.

Wzór na maksymalny obwód

Wyzwanie polega na znalezieniu grywalnych wielokątów o maksymalnym obwodzie. Sam maksymalny obwód jest zawsze określony przez wzór:

Jest tak, ponieważ dla maksymalnego obwodu każdy kwadratowy wierzchołek musi znajdować się na obwodzie. W przypadku nieparzystej liczby wierzchołków nie jest to możliwe, a najlepsze, co można osiągnąć, to jeden wierzchołek mniej (ponieważ obwód jest zawsze równy).

Wynik

Wyjście kształtu jako ciąg znaków rozdzielonych znakiem nowej linii ( N wierszy dokładnie M znaków). Tutaj używam spacji dla kwadratów poza wielokątem i „#” dla kwadratów wewnątrz wielokąta, ale możesz użyć dowolnych dwóch wizualnie różnych znaków, pod warunkiem, że ich znaczenie jest spójne dla wszystkich danych wejściowych.

Możesz dołączyć do jednego wiodącego nowego wiersza i do jednego końcowego nowego wiersza.

Jeśli chcesz, możesz zamiast tego wypisać M wierszy dokładnie N znaków i możesz wybrać wyjście M na N dla niektórych danych wejściowych i N na M danych wyjściowych dla innych.

Przykłady

Nieprawidłowy z powodu dziury:

###
# #
###

Nieprawidłowy ze względu na przecięcie (dotykanie po przekątnej - wierzchołek o 4 kwadratowych krawędziach na obwodzie) i, nawiasem mówiąc, otwór:

##
# #
###

Nieprawidłowy z powodu odłączenia:

#
# #
  #

Prawidłowy wielokąt maksymalnego obwodu:

# #
# #
###

Kredyty

Początkowo nie doceniałem, jak szybko można obliczyć wartość maksymalnego obwodu, i zamierzałem po prostu poprosić o tę wartość jako wynik. Dzięki cudownie pomocnym osobom na czacie za wyjaśnienie, jak obliczyć maksymalny obwód dla arbitralnych liczb N i M, i pomóc przekształcić to w wyzwanie, które przetrwa więcej niż jedną odpowiedź ...

W szczególności dzięki:

Sparr , Zgarb , feersum , jimmy23013 .

CJam, 47 bajtów

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

Wypróbuj online

Wyjaśnienie:

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.

Istnieją dwa główne przypadki wyniku. Jeśli co najmniej jeden z rozmiarów jest nieparzysty, wzór jest prostym „prowizją”. Na przykład dla danych wejściowych 7 6:

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

Jeśli oba rozmiary są równe, istnieje dodatkowa kolumna, w której co drugi kwadrat jest włączony. Na przykład dla danych wejściowych 8 6:

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

Teraz, aby pokazać, że te wzory osiągają teoretyczne maksimum obwodu, jak podano w opisie problemu, musimy potwierdzić, że pierwszy wzór ma obwód (M + 1) * (N + 1), a drugi tę samą wartość minus 1.

Dla pierwszego wzoru mamy obwód Mo nieparzystym wymiarze:

1. M dla górnej krawędzi.
2. 2 z boku górnego rzędu.
3. (M - 1) / 2 do przerw między zębami.
4. (M + 1) / 2zęby o obwodzie 2 * (N - 1) + 1każdy.

Daje to w sumie:

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)

W drugim przypadku, gdy zarówno Ma Nnawet, obwód sumuje się z:

1. M dla górnej krawędzi.
2. 2 z boku górnego rzędu.
3. M / 2 dla open # w górnym rzędzie.
4. M / 2zęby o obwodzie 2 * (N - 1) + 1każdy dla zębów prostych.
5. Prawy ząb ma dodatkowe 2 * (N / 2 - 1)elementy obwodowe dla postrzępionych zębów .

Dodając to wszystko razem:

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?"# ":" ")}}

Wykorzystano podniesienie mdo potęgi 0 o 1, aby zdecydować, czy 1 lub m #'s zostaną wydrukowane.

Służy >do testowania ostatniego wiersza zamiast ==.

Nie można pozbyć się miejsca po putach ani nawiasów!

Ruby, Rev 0, 69

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

To anonimowa funkcja lambda. Użyj tego w ten sposób:

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)

W końcu, po zapytaniu, czy M i N mogą być zamienione, nie potrzebowałem tego.

Typowe wyjścia dla N nieparzystych. Jeśli usuniemy #je po prawej stronie, oczywiście będziemy mieli (N + 1) (M + 1). Włączenie ich do kształtu usuwa 2 kwadraty z obwodu poziomego i dodaje 2 kwadraty z obwodu pionowego, więc nie ma zmian.

Tutaj polegamy na wyrażeniu, "#"*(i%2==0?m:1)które daje naprzemienne rzędy #symboli M i jednego #symbolu, i odpowiednio uzasadnia M. znaki.

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

Typowe wyjścia nawet dla N. 5 6wyraźnie ma ten sam obwód 6 5lub przyrost M + 1 = 6 w porównaniu z 5 5dodaniem pionowego obwodu ze względu na crenelację dolnego rzędu. 6 6ma to samo co 6 5plus przyrost (M + 1) -1 = 6 na obwodzie pionowym. Zatem są one zgodne ze wzorem.

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

Bardzo przydatne jest to, że Ruby rjustpozwala określić dopełnienie, które ma być używane dla pustych komórek. Zwykle wypełnienie jest ustawione na, " "ale dla ostatniego rzędu przełączamy się na "# "(pamiętaj, że wypełnienie będzie potrzebne tylko w ostatnim rzędzie, jeśli N. jest parzyste. Gdy N jest nieparzyste, ostatni rząd będzie pełny i nie będzie żadnego uzasadnienia, więc nie zobaczę crenelacji).

Sprawdź to tutaj.

C, 109 97 bajtów i dowód poprawności

Pisałem swoje rozwiązanie, ale @steveverrill mnie pobiło. Myślałem, że podzielę się tym samym, ponieważ dołączyłem dowód poprawności zastosowanej strategii.

Kod zredukowany:

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

Przed redukcją:

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

Strategia i dowód:

Zakładając poprawność równania maksymalnego ogranicznika (M + 1) (N + 1) - ((M + 1) (N + 1)) mod 2 , poniżej wyjaśniono zastosowaną optymalną strategię i udowodniono jej poprawność przez indukcję:

W przypadku nieparzystego M rysujemy kształt dłoni za pomocą palców M / 2 + 1, na przykład:

3x2
# # 
###

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

Udowadniamy teraz, że ta strategia jest optymalna dla wszystkich nieparzystych M przez indukcję:

Przypadek podstawowy: M = N = 1
Pojedyncza komórka jest wypełniona. Rozwiązanie jest poprawne, ponieważ (1 + 1) * (1 + 1) = 2 * 2 = 4, a kwadrat ma 4 boki.

Indukcja szerokości:
Załóżmy, że strategia kształtu dłoni działa dla (N, M-2), gdzie M jest nieparzysta, to znaczy, że jej obwód jest optymalny i wynosi (N + 1) (M - 2 + 1) + ((M -1) (N + 1)) mod 2 . Teraz pokazujemy, że będzie działać dla (N, M) .

Proces dodawania palca usuwa jedną krawędź z wielokąta i dodaje 3 + 2N . Na przykład:

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

Łącząc to z naszą hipotezą, że poprzedni obwód był optymalny, nowy obwód jest:

(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

Ponieważ mamy do czynienia z arytmetyką modulo 2,

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

W ten sposób udowodnienie, że zwiększenie szerokości przez dodanie palców prowadzi do optymalnego obwodu.

Indukcja na wysokości:
Załóżmy, że strategia kształtu dłoni działa dla (N-1, M) , gdzie M jest nieparzysta, to znaczy, jej obwód jest optymalny i jest to N (M + 1) + ((M + 1) N) mod 2 . Teraz pokazujemy, że będzie działać dla (N, M) .

Zwiększenie wysokości ręki jedynie wydłuża palce, znajdujące się na pierwszym i co drugim indeksie x. Z każdym wzrostem wysokości każdy palec dodaje dwa do obwodu i są (M + 1) / 2 palce, a zatem wzrost N prowadzi do wzrostu o 2 (M + 1) / 2 = M + 1 w obwód.

Łącząc to z hipotezą, mamy nowy obwód:

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

Arytmetyka modułowa pozwala nam uprościć ostatni termin, dzięki czemu uzyskujemy:

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

Udowodnienie, że rozwiązanie jest optymalne dla wszystkich N> 0 i nieparzystych M> 0.

W przypadku parzystej litery M wypełniamy planszę tak samo, jak w przypadku nieparzystej litery M, ale dodajemy crenelacje do ostatniego segmentu, na przykład:

4x3
# ##
# # 
####

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

Udowadniamy teraz, że ta strategia jest optymalna.

Indukcja dla parzystego M:
Załóżmy, że rozwiązanie jest poprawne dla (N, M-1), z nieparzystym M-1 (jak udowodniono w ostatnim przypadku), który ma optymalny obwód (N + 1) M - ( M (N + 1)) mod 2 . Teraz pokazujemy, że będzie działać dla (N, M).

Podobnie jak zwiększenie palców, każde crenelacja dodaje dwa do obwodu wielokąta. Całkowita liczba crenelacji wynosi (N + N mod 2) / 2 , dla sumy dodanego obwodu N + N mod 2 .

Łącząc to z hipotezą, mamy nowy obwód:

(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

Mamy to

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

Ponieważ jeśli N jest nieparzyste, to zmniejsza się do 0 = 0, a jeśli N jest parzyste, zmniejsza się do

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

Zatem strategia jest optymalna dla wszystkich M, N> 0 .