Katakanlah kita memiliki kisi n × n ; kita kemudian dapat membagi kisi menjadi dua bagian dengan menggambar garis melalui kisi. Segala sesuatu di satu sisi garis dalam satu set dan semua lainnya di sisi lain.
Berapa banyak cara kita membagi kisi dengan cara itu?
Sebagai contoh mari kita ambil 2 × 2 kisi:
. .
. .
Kita dapat membuat 2 partisi membagi kisi menjadi dua seperti:
× × × o
o o × o
Kami juga dapat mempartisi masing-masing sudut:
× o o × o o o o
o o o o × o o ×
Terakhir kita dapat meletakkan semua poin dalam satu partisi dengan melewatkan kisi sepenuhnya:
× ×
× ×
Ini membuat total 7 partisi. Perhatikan bahwa partisi berikut ini tidak valid karena tidak dapat dibuat dengan garis lurus tunggal.
× o
o ×
Ini adalah 3 × 3 kisi
. . .
. . .
. . .
Ada 4 partisi murni horizontal atau vertikal
× × × × × × × o o × × o
× × × o o o × o o × × o
o o o o o o × o o × × o
Ada 4 partisi sudut
× o o o o × o o o o o o
o o o o o o o o o o o o
o o o o o o o o × × o o
Ada 4 partisi sudut yang lebih besar
× × o o × × o o o o o o
× o o o o × o o × × o o
o o o o o o o × × × × o
Ada 8 partisi sudut parsial
× × o o × × o o × o o o o o o o o o o o o × o o
o o o o o o o o × o o × o o o o o o × o o × o o
o o o o o o o o o o o × o × × × × o × o o o o o
Ada 8 ksatria bergerak partisi
× × o o × × × × × o o o o o × × o o o o o × × ×
× o o o o × o o × o o × o o × × o o × o o × o o
× o o o o × o o o × × × o × × × × o × × × o o o
Dan ada satu partisi utuh
× × ×
× × ×
× × ×
Itu membuat 29 partisi secara total.
Tugas
Mengingat sejumlah n sebagai input, output jumlah partisi yang dapat dibuat dengan cara ini dari n × n kisi.
Ini adalah pertanyaan kode-golf sehingga jawaban akan dinilai dalam byte, dengan lebih sedikit byte yang lebih baik.
Uji Kasus
Berikut adalah 34 izin pertama dari OEIS:
1, 7, 29, 87, 201, 419, 749, 1283, 2041, 3107, 4493, 6395, 8745, 11823, 15557, 20075, 25457, 32087, 39725, 48935, 59457, 71555, 85253, 101251, 119041, 139351, 161933, 187255, 215137, 246691, 280917, 319347, 361329, 407303
sumber
Jawaban:
JavaScript (ES6),
113111 byteDisimpan 2 byte berkat guest44851
Diindeks 0.
Berdasarkan formula yang disebutkan pada OEIS:
Demo
Tampilkan cuplikan kode
sumber
a==1&&
dengana<2&&
.&&x+x+1
dengan|x+x+1
.Python 2 , 116 byte
Cobalah online!
sumber
R=range
? Apakah itu menghemat beberapa byte?Jelly , 14 byte
Cobalah online!
Penjelasan
sumber
Mathematica, 59 byte
milik OEIS (seperti pertanyaannya)
-1 byte dari @ovs
Cobalah online!
sumber
==1
dengan<2
TIO .Python 2, 90 byte
sumber