Tantangan
Mari kita bayangkan sebuah N
-tupel bilangan bulat antara 0 dan M
inklusif, dan mari kita sebut saja F
.
Ada (M + 1) ** N
kemungkinan F
total.
Berapa banyak yang F
memenuhi semua ketidaksetaraan berikut (indeks berbasis satu)?
F[n] + F[n+1] <= M
untuk1 <= n < N
F[N] + F[1] <= M
Tulis sebuah program atau fungsi yang mengambil dua bilangan bulat positif N
dan M
dan menghasilkan jawabannya dalam bentuk apa pun.
Uji Kasus
(N,M) => Answer
(1,1) => 1
(2,1) => 3
(3,1) => 4
(4,1) => 7
(1,2) => 2
(2,2) => 6
(3,2) => 11
(4,2) => 26
(10,3) => 39175
(10,4) => 286555
(10,5) => 1508401
(25,3) => 303734663372
(25,4) => 43953707972058
(25,5) => 2794276977562073
(100,3) => 8510938110502117856062697655362747468175263710
(100,4) => 3732347514675901732382391725971022481763004479674972370
(100,5) => 60964611448369808046336702581873778457326750953325742021695001
Penjelasan
M (max value of element) = 1
F[1] + F[1] <= 1; F = [0]
(1,1) => 1
F[1] + F[2] <= 1; F = [0,0], [0,1], [1,0]
(2,1) => 3
F = [0,0,0], [0,0,1], [0,1,0], [1,0,0]
(3,1) => 4
F = [0,0,0,0], [0,0,0,1], [0,0,1,0], [0,1,0,0], [0,1,0,1], [1,0,0,0], [1,0,1,0]
(4,1) => 7
---
M = 2
F[1] + F[1] <= 2; F = [0], [1]
(1,2) => 2
F = [0,0], [0,1], [0,2], [1,0], [1,1], [2,0]
(2,2) => 6
F = [0,0,0], [0,0,1], [0,0,2], [0,1,0], [0,1,1], [0,2,0], [1,0,0], [1,0,1],
[1,1,0], [1,1,1], [2,0,0]
(3,2) => 11
(4,2) => 26 (left as exercise for you)
Aturan
- Ini adalah tantangan dengan kompleksitas terbatas . Kompleksitas waktu kode Anda harus polinomial dalam
M
danN
(mis. Anda tidak dapat menghasilkan semua(M + 1) ** N
tupel dan kemudian memeriksa kondisinya). Tolong jelaskan pendekatan Anda dalam pengiriman Anda. - Aturan standar kode-golf berlaku. Jawaban terpendek dalam byte menang.
code-golf
restricted-complexity
Bubbler
sumber
sumber
mat(...,int)
tampaknya tidak berfungsi untukn=100
kasus tersebut. Metode ini benar (menggunakan sympy untuk menjumlahkan kekuatan akar dari polinomial karakteristik tidak bekerja, misalnya), tetapi numpy salah di suatu tempat dengan meningkatnya angka (mungkin itu adalah**
operator daya?)Pyth , 27 byte
Demonstrasi
Diharapkan input dalam format:
Ini adalah pemrograman dinamis klasik, di ujung kiri nilai yang ditetapkan sejauh ini, ujung kanan, dan ukuran kesenjangan saat ini.
Cara kerjanya, dalam pseudocode / Python:
Q
digunakan untukM
,z
digunakan untukN
,:
adalahfill
,N
adalahleft
,T
adalahright
,Y
adalahgap
.sumber
MATL ,
1312 byteCobalah online! Ini adalah terjemahan langsung dari jawaban Python xnor dan jawaban MATL pertama saya, jadi kemungkinan besar tidak optimal. Misalnya ada kemungkinan cara yang lebih pendek untuk mendapatkan matriks segitiga kiri atas daripada
t&lYRP
. Sunting: Dan ternyata ada, yaitu:&>~P
. Terima kasih kepada Luis Mendo untuk -1 byte!sumber
Stax , 17 byte
Jalankan dan debug itu
Dibongkar, tidak diserang, dan dikomentari, sepertinya ini.
Jalankan yang ini
sumber
R , 72 byte
Cobalah online!
Pendekatan port xnor.
Gagal untuk kasus uji yang lebih besar karena R hanya memiliki dukungan integer 32-bit (mereka dapat dilemparkan ke
double
begitu nilai maks tercapai), sehingga diperlukangmp
atau perpustakaan aritmatika presisi sewenang-wenang lainnya diperlukan.Anehnya, R tidak memiliki operator daya matriks, seperti
^
biasa berlaku elementwise.sumber
%^%
operator yang diimplementasikan dengan benar dalam paketexpm
yang akan memungkinkan untuk -5 byte , tetapi sayangnya, itu tidak tersedia pada TIO (saya harus menguji secara lokal).function(M,N)sum(diag(expm::`%^%`(outer(0:M,0:M,"+")<=M,N)))