Ini golf kode. Pemenangnya adalah kode yang valid dengan jumlah byte terkecil.

Tantangan

Diberikan input M dan N , lebar dan tinggi kotak persegi panjang, menghasilkan poligon yang memenuhi berikut:

• Tepi poligon hanya terdiri dari tepi persegi: tidak ada tepi diagonal - semuanya vertikal atau horizontal.
• Poligon tidak memiliki lubang: setiap kotak di luar poligon dapat dicapai dengan langkah ortogonal pada kotak di luar poligon, mulai dari kotak di luar poligon pada batas luar persegi panjang.
• Poligon tidak memiliki persimpangan-sendiri: dari pertemuan tepi persegi pada titik, tidak lebih dari 2 dapat menjadi bagian dari perimeter poligon.
• Poligon terhubung: setiap kotak dalam poligon harus dapat dijangkau dari kotak lain dalam poligon melalui langkah ortogonal yang tetap berada dalam poligon.
• Poligon memiliki perimeter maksimum yang mungkin: sesuai dengan rumus di bawah ini.

Kode Anda harus berfungsi untuk M dan N dari 1 hingga 255.

Formula untuk batas maksimum

Tantangannya di sini adalah menemukan poligon yang paling golf dengan batas maksimum. Batas maksimum itu sendiri selalu ditentukan oleh rumus:

Ini benar karena untuk perimeter maksimum, setiap titik persegi harus pada perimeter. Untuk jumlah simpul yang ganjil, ini tidak mungkin dan yang terbaik yang bisa dicapai adalah satu simpul lebih sedikit (karena perimeter selalu genap).

Keluaran

Keluarkan bentuk sebagai string karakter yang dipisahkan baris baru ( N baris tepat karakter M ). Di sini saya menggunakan ruang untuk kotak di luar poligon, dan '#' untuk kotak di dalam poligon, tetapi Anda dapat menggunakan dua karakter yang berbeda secara visual, asalkan artinya konsisten untuk semua input.

Anda dapat memasukkan hingga satu baris baru dan satu baris baru.

Jika Anda mau, Anda bisa menghasilkan baris M dengan karakter N persis , dan Anda dapat memilih output M demi N untuk beberapa input dan keluaran N oleh M untuk yang lain.

Contohnya

Tidak valid karena lubang:

###
# #
###

Tidak valid karena persimpangan (menyentuh secara diagonal - sebuah simpul dengan 4 tepi persegi pada perimeter) dan, kebetulan, sebuah lubang:

##
# #
###

Tidak valid karena terputus:

#
# #
  #

Poligon valid perimeter maksimum:

# #
# #
###

Kredit

Saya awalnya meremehkan seberapa cepat nilai perimeter maksimum dapat dihitung, dan hanya akan meminta nilai itu sebagai output. Terima kasih kepada orang-orang yang sangat membantu dalam obrolan karena menjelaskan cara mengerjakan batas maksimum untuk N dan M yang sewenang-wenang dan membantu menjadikannya sebuah tantangan yang akan bertahan selama lebih dari satu jawaban ...

Secara khusus terima kasih kepada:

Sparr , Zgarb , feersum , jimmy23013 .

CJam, 47 byte

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

Cobalah online

Penjelasan:

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.

Ada dua kasus utama untuk hasilnya. Jika setidaknya salah satu ukurannya aneh, polanya adalah "rake" polos. Misalnya, untuk input 7 6:

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

Jika kedua ukuran genap, ada kolom tambahan tempat setiap kotak kedua "menyala". Misalnya, untuk input 8 6:

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

Sekarang, untuk menunjukkan bahwa pola-pola ini mencapai maksimum teoretis perimeter seperti yang diberikan dalam deskripsi masalah, kita perlu mengkonfirmasi bahwa pola pertama memiliki perimeter (M + 1) * (N + 1), dan yang kedua memiliki nilai yang sama minus 1.

Untuk pola pertama, kita memiliki perimeter, dengan Mdimensi aneh:

1. M untuk tepi atas.
2. 2 di sisi baris atas.
3. (M - 1) / 2 untuk celah di antara gigi.
4. (M + 1) / 2gigi dengan perimeter 2 * (N - 1) + 1masing-masing.

Ini menambahkan hingga:

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)

Untuk kasus kedua di mana keduanya Mdan Nbahkan, perimeter bertambah dari:

1. M untuk tepi atas.
2. 2 di sisi baris atas.
3. M / 2 untuk # terbuka di baris atas.
4. M / 2gigi dengan perimeter 2 * (N - 1) + 1masing-masing untuk gigi biasa.
5. Gigi paling kanan memiliki 2 * (N / 2 - 1)potongan perimeter ekstra untuk jaggies.

Menambahkan ini bersama-sama:

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

Digunakan menaikkan mke daya 0 o 1 untuk memutuskan apakah 1 atau m #akan dicetak.

Digunakan >untuk menguji baris terakhir, bukan ==.

Tidak dapat menyingkirkan ruang setelah meletakkan, atau tanda kurung!

Ruby, Rev 0, 69

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

Ini adalah fungsi lambda anonim. Gunakan seperti ini:

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)

Pada akhirnya, setelah bertanya apakah M dan N bisa dipertukarkan, saya tidak membutuhkannya.

Output khas untuk N odd. Jika kita menghapusnya #sendiri di sisi kanan, jelas kita akan memiliki (N +1) (M +1). Termasuk mereka untuk bergabung dengan bentuk menghilangkan 2 kuadrat perimeter horisontal dan menambahkan 2 kuadrat perimeter vertikal, sehingga tidak ada perubahan.

Di sini kita bergantung pada ekspresi "#"*(i%2==0?m:1)untuk memberikan baris bergantian #simbol M dan satu #simbol, dan benar membenarkan untuk karakter M.

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

Output khas untuk N even. 5 6jelas memiliki perimeter yang sama dengan 6 5, atau peningkatan M + 1 = 6 dibandingkan dengan 5 5penambahan perimeter vertikal karena crenelation baris bawah. 6 6memiliki sama dengan 6 5ditambah kenaikan (M + 1) -1 = 6 di perimeter vertikal. Jadi mereka sesuai dengan formula.

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

Sangat berguna karena Ruby rjustmemungkinkan Anda menentukan padding yang akan digunakan untuk sel-sel kosong. Biasanya padding diatur ke " "tetapi untuk baris terakhir kita beralih ke "# "(perhatikan bahwa padding hanya akan diperlukan pada baris terakhir jika N adalah genap. Dimana N aneh, baris terakhir akan selesai dan tidak akan ada pembenaran, sehingga Anda tidak akan melihat crenelations.)

Lihat disini.

C, 109 97 byte dan bukti kebenaran

Saya sedang mengerjakan solusi saya tetapi @steveverrill mengalahkan saya untuk itu. Saya pikir saya akan membagikannya sama saja, karena saya menyertakan bukti kebenaran untuk strategi yang digunakan.

Kode yang Dikurangi:

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

Sebelum Pengurangan:

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

Strategi dan Bukti:

Dengan asumsi kebenaran dari persamaan pembatas maksimum (M + 1) (N + 1) - ((M + 1) (N + 1)) mod 2 , berikut ini menjelaskan strategi optimal yang digunakan dan membuktikan kebenarannya dengan induksi:

Untuk M aneh, kami menggambar bentuk seperti tangan dengan jari-jari M / 2 + 1, misalnya:

3x2
# # 
###

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

Kami sekarang membuktikan strategi ini optimal untuk semua M aneh dengan induksi:

Kasus Dasar: M = N = 1
Sel tunggal terisi. Solusinya benar karena (1 + 1) * (1 + 1) = 2 * 2 = 4, dan kotak memiliki 4 sisi.

Lebar induksi:
Asumsikan bahwa strategi bentuk tangan bekerja untuk (N, M-2) di mana M aneh, yaitu pembatasnya optimal dan (N + 1) (M - 2 + 1) + ((M -1) (N +1)) mod 2 . Kami sekarang menunjukkan bahwa itu akan bekerja untuk (N, M) .

Proses menambahkan jari menghilangkan satu sisi dari poligon, dan menambahkan 3 + 2N . Sebagai contoh:

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

Menggabungkan ini dengan hipotesis kami bahwa perimeter sebelumnya optimal, perimeter baru adalah:

(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

Karena kita berurusan dengan modulo 2 aritmatika,

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

Dengan demikian, membuktikan bahwa meningkatkan lebar dengan menambahkan jari mengarah ke perimeter optimal.

Induksi pada ketinggian:
Asumsikan strategi bentuk tangan bekerja untuk (N-1, M) , di mana M aneh, yaitu, perimeternya optimal dan N (M + 1) + ((M + 1) N) mod 2 . Kami sekarang menunjukkan bahwa itu akan bekerja untuk (N, M) .

Meningkatkan tinggi tangan hanya memanjang jari-jari, terletak di x-indeks pertama dan setiap lainnya. Untuk setiap kenaikan tinggi, setiap jari menambahkan dua ke perimeter, dan ada (M + 1) / 2 jari, dengan demikian, peningkatan N mengarah ke peningkatan 2 (M + 1) / 2 = M + 1 di perimeter.

Menggabungkan ini dengan hipotesis, kita memiliki bahwa perimeter baru adalah:

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

Aritmatika modular memungkinkan kita untuk menyederhanakan istilah terakhir, sehingga kita memperoleh:

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

Membuktikan bahwa solusinya optimal untuk semua N> 0 dan aneh M> 0.

Untuk genap M, kami mengisi papan seperti yang kami lakukan untuk M aneh, tetapi kami menambahkan crenelation ke segmen terakhir, misalnya:

4x3
# ##
# # 
####

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

Kami sekarang membuktikan bahwa strategi ini optimal.

Induksi untuk genap M:
Asumsikan bahwa solusinya benar untuk (N, M-1), dengan M-1 ganjil (seperti yang dibuktikan dalam kasus terakhir), yang memiliki perimeter optimal (N + 1) M - ( M (N + 1)) mod 2 . Kami sekarang menunjukkan bahwa itu akan bekerja untuk (N, M).

Seperti menambah jari, setiap crenelation menambahkan dua ke perimeter poligon. Jumlah total crenelations adalah (N + N mod 2) / 2 , untuk total N + N mod 2 perimeter ditambahkan.

Menggabungkan ini dengan hipotesis, kita memiliki bahwa perimeter baru adalah:

(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

Kami memilikinya

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

Karena jika N ganjil, maka ini berkurang menjadi 0 = 0, dan jika N adalah genap, itu berkurang menjadi

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

Dengan demikian strategi optimal untuk semua M, N> 0 .