20

Video game Transistor memiliki sistem kemampuan yang sangat menarik. Anda mengumpulkan 16 "Fungsi" yang dapat Anda gunakan di 16 slot berbeda. Apa yang menarik adalah bahwa ada 3 jenis slot dan setiap Fungsi berperilaku berbeda sesuai dengan slot tempat Anda menggunakannya:

Ada 4 Slot Pasif .
Ada 4 Slot Aktif .
Setiap Slot Aktif memiliki 2 Slot Peningkatan .

Kami ingin mengetahui berapa banyak set keterampilan yang berbeda yang memberi kami.

Namun, beberapa kombinasi sama. Secara khusus, dalam masing-masing kelompok slot, posisi spesifik suatu Fungsi tidak masalah. Di sisi lain, efek dari suatu Fungsi dalam Slot Peningkatan memang tergantung pada Fungsi spesifik yang digunakan dalam Slot Aktif induk.

Oleh karena itu, menggunakan digit heksadesimal untuk bertahan dalam Fungsi, kombinasi berikut semuanya sama:

Passive Slots:    0     1     2     3
Active Slots:     4     5     6     7
Upgrade Slots:   8 9   A B   C D   E F

Passive Slots:    2     0     1     3    # Permutation of passive slots.
Active Slots:     4     5     6     7
Upgrade Slots:   8 9   A B   C D   E F

Passive Slots:    0     1     2     3
Active Slots:     5     6     4     7    # Permutation of active slots together
Upgrade Slots:   A B   C D   8 9   E F   # with their upgrade slots.

Passive Slots:    0     1     2     3
Active Slots:     4     5     6     7
Upgrade Slots:   8 9   B A   C D   F E   # Permutation within upgrade slots.

serta kombinasi dari pengaturan ulang ini. Perhatikan bahwa dalam kasus ketiga Upgrade Slots bertukar bersama dengan Active Slots untuk mempertahankan efek keseluruhan yang sama.

Di sisi lain, kombinasi berikut semuanya berbeda dari set di atas:

Passive Slots:    4     5     6     7    # Passive slots swapped
Active Slots:     0     1     2     3    # with active slots.
Upgrade Slots:   8 9   A B   C D   E F

Passive Slots:    0     1     2     3
Active Slots:     5     4     6     7    # Permutation of active slots without
Upgrade Slots:   8 9   A B   C D   E F   # changing upgrade slots.

Passive Slots:    0     1     2     3
Active Slots:     4     5     6     7
Upgrade Slots:   8 A   9 B   C D   E F   # Permutation between different upgrade slots.

Menurut perhitungan saya, Anda memberi 2.270.268.000 kemungkinan kombinasi (berbeda secara fungsional), dengan asumsi semua Fungsi digunakan.

Jika Anda memiliki kurang dari 16 Fungsi yang Anda inginkan, beberapa slot akan tetap kosong. Namun, perhatikan bahwa Anda tidak dapat menempatkan suatu Fungsi dalam Slot Peningkatan jika Slot Aktif induk kosong.

Tantangan

Anda harus menentukan jumlah konfigurasi yang mungkin tergantung pada berapa banyak fungsi yang Anda miliki. Selanjutnya, saya akan sedikit menggeneralisasikan masalah dengan membuat jumlah slot variabel, untuk mencegah solusi hardcoding sepele.

Tulis sebuah program atau fungsi yang, diberi dua bilangan bulat positif M ≥ 1dan 1 ≤ N ≤ 4M, menentukan jumlah set keterampilan yang mungkin (berbeda secara fungsional) dengan asumsi NFungsi yang berbeda persis digunakan untuk mengisi sebanyak mungkin Slot MPasif, MAktif , dan 2MPeningkatan.

Anda dapat menulis sebuah program atau fungsi, mengambil input melalui STDIN (atau alternatif terdekat), argumen baris perintah atau argumen fungsi dan mengeluarkan hasilnya melalui STDOUT (atau alternatif terdekat), nilai pengembalian fungsi atau parameter function (out).

Kode Anda harus dapat menangani input apa pun hingga dan termasuk M = 8dalam satu menit pada mesin desktop yang masuk akal. Ada beberapa kelonggaran dalam hal ini, tetapi harus mengesampingkan solusi brute force. Pada prinsipnya seharusnya tidak ada masalah untuk menyelesaikan input tersebut dalam waktu kurang dari satu detik.

Ini adalah kode golf, jawaban terpendek (dalam byte) menang.

Uji Kasus

Setiap test case ada dalam formulir M N => Result.

1 1 => 2
1 2 => 4
1 3 => 9
1 4 => 12
2 1 => 2
2 2 => 6
2 3 => 21
2 4 => 78
2 5 => 270
2 6 => 810
2 7 => 1890
2 8 => 2520
3 1 => 2
3 2 => 6
3 3 => 23
3 4 => 98
3 5 => 460
3 6 => 2210
3 7 => 10290
3 8 => 44520
3 9 => 168840
3 10 => 529200
3 11 => 1247400
3 12 => 1663200
4 1 => 2
4 2 => 6
4 3 => 23
4 4 => 100
4 5 => 490
4 6 => 2630
4 7 => 14875
4 8 => 86030
4 9 => 490140
4 10 => 2652300
4 11 => 13236300
4 12 => 59043600
4 13 => 227026800
4 14 => 718918200
4 15 => 1702701000
4 16 => 2270268000
5 1 => 2
5 2 => 6
5 3 => 23
5 4 => 100
5 5 => 492
5 6 => 2672
5 7 => 15694
5 8 => 98406
5 9 => 644868
5 10 => 4306932
5 11 => 28544670
5 12 => 182702520
5 13 => 1101620520
5 14 => 6122156040
5 15 => 30739428720
5 16 => 136670133600
5 17 => 524885961600
5 18 => 1667284819200
5 19 => 3959801445600
5 20 => 5279735260800
6 1 => 2
6 2 => 6
6 3 => 23
6 4 => 100
6 5 => 492
6 6 => 2674
6 7 => 15750
6 8 => 99862
6 9 => 674016
6 10 => 4787412
6 11 => 35304654
6 12 => 265314588
6 13 => 1989295308
6 14 => 14559228684
6 15 => 101830348620
6 16 => 667943115840
6 17 => 4042651092480
6 18 => 22264427465280
6 19 => 110258471363040
6 20 => 484855688116800
6 21 => 1854067032417600
6 22 => 5894824418683200
6 23 => 14025616720315200
6 24 => 18700822293753600
7 1 => 2
7 2 => 6
7 3 => 23
7 4 => 100
7 5 => 492
7 6 => 2674
7 7 => 15752
7 8 => 99934
7 9 => 676428
7 10 => 4849212
7 11 => 36601554
7 12 => 288486132
7 13 => 2349550632
7 14 => 19504692636
7 15 => 162272450340
7 16 => 1328431104000
7 17 => 10507447510560
7 18 => 78942848624640
7 19 => 554967220167360
7 20 => 3604592589998400
7 21 => 21411337810262400
7 22 => 115428212139240000
7 23 => 561247297649438400
7 24 => 2439121536313862400
7 25 => 9283622495827680000
7 26 => 29520583763711040000
7 27 => 70328449554723360000
7 28 => 93771266072964480000
8 1 => 2
8 2 => 6
8 3 => 23
8 4 => 100
8 5 => 492
8 6 => 2674
8 7 => 15752
8 8 => 99936
8 9 => 676518
8 10 => 4852992
8 11 => 36722169
8 12 => 291621462
8 13 => 2418755196
8 14 => 20834571186
8 15 => 184894557705
8 16 => 1672561326150
8 17 => 15217247948760
8 18 => 137122338089880
8 19 => 1204392465876600
8 20 => 10153538495100000
8 21 => 81007229522419200
8 22 => 604136189949692400
8 23 => 4168645459350372000
8 24 => 26403795950145213600
8 25 => 152700324078982680000
8 26 => 803784718213396920000
8 27 => 3838761204861983400000
8 28 => 16503742828841748480000
8 29 => 62545434470667308160000
8 30 => 198853691115980300400000
8 31 => 474189571122722254800000
8 32 => 632252761496963006400000

Ini semua input yang harus ditangani kode Anda dalam satu menit (masing-masing), tetapi pada prinsipnya harus bekerja untuk input yang lebih besar. Anda dapat menggunakan beberapa M = 10kasus uji berikut untuk memeriksa bahwa:

10 1 => 2
10 2 => 6
10 3 => 23
10 4 => 100
10 5 => 492
10 6 => 2674
10 7 => 15752
10 8 => 99936
10 9 => 676520
10 10 => 4853104
10 11 => 36727966
10 12 => 291849866
10 13 => 2426074222
10 14 => 21033972388
10 15 => 189645995396
10 16 => 1773525588406
10 17 => 17155884420532
10 18 => 171073929494468
10 19 => 1750412561088334
10 20 => 18258387148774916
10 21 => 192475976310317700
10 22 => 2028834600633220380
10 23 => 21127206177119902860
10 24 => 214639961631544809360
10 25 => 2101478398293813739200
10 26 => 19602967930531817832000
10 27 => 172444768103233181556000
10 28 => 1417975382888905296456000
10 29 => 10820259026484304813416000
10 30 => 76213534343700480310584000
10 31 => 493916052421168703366040000
10 32 => 2941900199368102067135040000
10 33 => 16113144277547868007416960000
10 34 => 81222252655277786422930560000
10 35 => 376309102059179385262246080000
10 36 => 1589579966324953534441910400000
10 37 => 5981477408861097281112374400000
10 38 => 19005991357166148698688124800000
10 39 => 45381652832417130566255318400000
10 40 => 60508870443222840755007091200000

code-golf game combinatorics permutations Martin Ender
sumber

Apakah wajib mengisi slot sebanyak mungkin?

feersum

7

Saya kira saya sebaiknya menunggu jawaban saya turn()sebelum help()Anda , atau kalau tidak saya akan perlu dari Anda setelah dan ..... Man ...get()load()ping()void()spark()crash()

FryAmTheEggman

@feersum Ya, semua Nfungsi sedang digunakan.

Martin Ender

18

CJam (56 byte)

q~4@:Nm*:$_&{:+1$\-N),&},f{1$1$:+-\0-:(_e`0f=+++:m!:/}:+

Demo online

N $n$ $k$ mn $M$ $N$

$X$ $0 \le X \le M$ $N-X$ $\frac{N!}{X!(N-X)!}$ $N-X$ $M$ $3$

Ambil partisi . Kami dapat menetapkan bagian ke konstelasi slot pertama, ke yang kedua, dll di cara (multinomial), tetapi kita perlu mengganti dua faktor. Pertama, jika kita memiliki maka rasi bintang dapat dipertukarkan, jadi kita selanjutnya membagi dengan faktorial dari banyaknya setiap bagian, . (Misalnya, partisi memiliki , , ). Kedua, kami memiliki slot "aktif" yang ditentukan di setiap rasi bintang, jadi untuk setiap kami kalikan dengan $λ_0, λ_1, \ldots, λ_k$ $λ_0$ $λ_1$ $\frac{(N-X)!}{λ_0! λ_1! ... λ_k!}$ $λ_i = λ_j$ $μ_i$ 3 2 2 1 $μ_3 = 1$ $μ_2 = 2$ $μ_1 = 1$ $λ_i$ $λ_i$ cara untuk memilih fungsi aktif.

Jadi untuk setiap partisi jumlah distribusi fungsi adalah

\frac{N!}{X! (λ_{0} - 1)! \dots (λ_{k} - 1)! μ_{1}! μ_{2}! μ_{3}!}

$\frac{N!}{X! (λ_0-1)! \ldots (λ_k-1)! μ_1! μ_2! μ_3!}$

Kode di atas menghitung partisi menggunakan pendekatan yang sama dengan Dennis (jelas dan pendek, meskipun tidak terlalu scalable) dan kemudian memproses setiap partisi menjadi array yang mirip dengan [N X λ_0-1 ... λ_k-1 μ_1 μ_2 μ_3]yang dapat mengangkat fungsi faktorial dan kemudian lipat pembagian.

Peter Taylor
sumber

9

CJam, 74 67 byte

q~4@:Mm*:$L|{:+W$\-M),&},f{0-:F1@@{_m!\I-:Nm!/I(m!/*N}fI;Fm!Fe=/}:+

Saya telah memverifikasi semua kasus uji pada komputer desktop saya menggunakan Java interpreter . Ini memakan waktu 2,2 detik untuk 1 ≤ M ≤ 8 dan 3,5 menit untuk M = 10 .

Coba biola ini dalam juru bahasa CJam atau verifikasi 84 kasus uji pertama sekaligus .

Ide

Pada prinsipnya, kita dapat mengisi setiap slot aktif dan slot pemutakhirannya yang sesuai dengan fungsi 0 , 1 , 2 atau 3 . Untuk total slot 4M , kami mengambil semua vektor V dari {0, 1, 2, 3} ^M dan menyaring yang jumlahnya (V)> N (lebih banyak fungsi dalam slot non-pasif daripada total fungsi yang tersedia) atau jumlah ( V) + M <N (slot pasif tidak cukup untuk fungsi tidak aktif). Kami mengurutkan dan menduplikasi semua vektor yang disimpan, karena urutan keluarga slot tidak penting.

Dengan fungsi N dan fungsi V = (x ₁ ,…, x _M ) di bagian non-pasif dari kelompok slot, kami menghitung jumlah kombinasi sebagai berikut:

Jika x ₁ = 0 , hanya ada satu kemungkinan untuk keluarga slot itu.

Jika x ₁ = 1 , ada kemungkinan N , karena kita memiliki fungsi N , dan fungsi harus masuk dalam slot aktif.

Jika x ₁ = 2 , kita harus menempatkan satu fungsi di slot aktif dan lainnya di slot upgrade (tidak masalah yang mana). Ada N pilihan untuk slot aktif dan N-1 pilihan tersisa untuk slot upgrade, memberikan total kombinasi N (N-1) .

Jika x ₁ = 3 , ada pilihan N untuk slot aktif, N - 1 pilihan tersisa untuk slot upgrade pertama dan N - 2 untuk slot upgrade kedua. Karena slot upgrade tidak memiliki urutan, ini menghitung setiap kombinasi dua kali, jadi ada kombinasi unik N (N - 1) (N - 2) .

Bagaimanapun, ada N! / ((N - x ₁ )! × (x ₁ - 1)! Kombinasi untuk keluarga ini.
Kami telah menggunakan fungsi x ₁ , jadi atur N: = N - x ₁ dan ulangi langkah 1 untuk x ₂ , lalu x ₃ , dll.
Jika V berisi duplikat, produk dari hasil di atas akan menghitung semua kombinasi beberapa kali. Untuk setiap elemen unik V , jika itu terjadi r kali dalam V , ada r! cara yang setara untuk mengatur keluarga slot ini, sehingga hasil dari atas harus dibagi dengan r! .
Hasil akhir adalah jumlah kombinasi unik untuk V tersebut .

Untuk menghitung jumlah total kombinasi yang unik, semua yang kiri lakukan adalah untuk menghitung jumlah hasil untuk masing-masing V .

Kode

q~        e# Read an evaluate all input from STDIN. Pushes M and N.
4@:M      e# Push 4, rotate the M, and formally save it in M.
m*        e# Push {0, 1, 2, 3}^M.
:$        e# Sort each vector.
L|        e# Perform set union with the empty list (deduplicates).
{         e# For each sorted vector:
  :+      e#   Compute the sum of its coordinates.
  W$\-    e#   Subtract the sum from N (bottom of the stack).
  M),&    e#   Push [0 ... M] and intersect.
},        e# If the intersection was not empty, keep the vector.
f{        e# For each kept vector, push N and V; then:
  0-:F    e#   Save the non-zero elements of V in F.
  1@@     e#   Push 1 (accumulator), and rotate N and F on top of it.
  {       e#   For each I in F:
    _m!   e#     Push I and push factorial(I).
    \I-:N e#     Subtract I from N and update N.
    m!/   e#     Divide factorial(N) (original N) by factorial(N) (updated N).
    I(m!/ e#     Divide the quotient by factorial(I - 1).
    *     e#    Multiply the accumulator by the resulting quotient.
    N     e#    Push N for the next iteration.
  }fI     e#
  ;       e#   Pop N.
  Fm!     e#   Push all non-unique permutations of F.
  Fe=     e#   Count the number of times F appears.
  /       e#   Divide the accumulator by the result.
}         e#
:+        e# Add all resulting quotients.

Dennis
sumber

Combinatorics of Transistor

Tantangan

Uji Kasus

Jawaban:

CJam (56 byte)

CJam, 74 67 byte

Ide

Kode