20

Gra wideo Tranzystor ma bardzo interesujący system umiejętności. Zbierasz 16 „Funkcji”, z których możesz korzystać w 16 różnych miejscach. Co ciekawe, istnieją 3 typy gniazd i każda funkcja zachowuje się inaczej w zależności od tego, w którym z nich używasz:

Istnieją 4 pasywne automaty .
Istnieją 4 aktywne automaty .
Każde aktywne miejsce ma 2 miejsca na ulepszenia .

Chcemy dowiedzieć się, ile daje nam różnych zestawów umiejętności.

Jednak niektóre kombinacje są równoważne. W szczególności w obrębie każdej z tych grup gniazd określone położenie funkcji nie ma znaczenia. Z drugiej strony, działanie funkcji w uaktualnieniu Slot nie zależą od funkcji konkretnego stosowanego w macierzystej aktywnym slocie.

Dlatego też, używając cyfr szesnastkowych, aby zastąpić Funkcje, wszystkie następujące kombinacje są równoważne:

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.

a także dowolną kombinację tych zmian. Zauważ, że w trzecim przypadku Sloty Upgrade zostały zamienione wraz z Aktywnymi Slots, aby zachować ten sam ogólny efekt.

Z drugiej strony następujące kombinacje różnią się od powyższego zestawu:

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.

Według moich obliczeń daje to 22 270 268 000 możliwych (funkcjonalnie odrębnych) kombinacji, przy założeniu, że wszystkie Funkcje są używane.

Jeśli masz do dyspozycji mniej niż 16 funkcji, niektóre miejsca pozostaną puste. Należy jednak pamiętać, że nie można umieścić funkcji w gnieździe aktualizacji, jeśli macierzysty aktywny slot jest pusty.

Wyzwanie

Musisz określić liczbę możliwych konfiguracji w zależności od liczby posiadanych funkcji. Ponadto nieznacznie uogólnię problem, zmieniając liczbę gniazd, aby zapobiec trywialnym rozwiązaniom związanym z twardym kodowaniem.

Napisz program lub funkcję, która, biorąc pod uwagę dwie dodatnie liczby całkowite M ≥ 1i 1 ≤ N ≤ 4M, określa liczbę możliwych (funkcjonalnie odrębnych) zestawów umiejętności, zakładając, że Ndo wypełnienia jak największej liczby Mpasywnych, Maktywnych i 2Mulepszonych miejsc używa się dokładnie różnych funkcji .

Możesz napisać program lub funkcję, pobierając dane wejściowe przez STDIN (lub najbliższą alternatywę), argument wiersza poleceń lub argument funkcji i wypisując wynik przez STDOUT (lub najbliższą alternatywę), wartość zwracaną funkcji lub parametr funkcji (wyjściowej).

Twój kod musi być w stanie obsłużyć wszelkie dane wejściowe w M = 8ciągu jednej minuty włącznie na rozsądnej maszynie stacjonarnej. Jest w tym trochę swobody, ale powinno to wykluczyć rozwiązania brutalnej siły. Zasadniczo nie powinno być problemu z rozwiązaniem któregokolwiek z tych danych wejściowych w mniej niż sekundę.

To jest kod golfowy, wygrywa najkrótsza odpowiedź (w bajtach).

Przypadki testowe

Każdy przypadek testowy ma formę 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

Są to wszystkie dane wejściowe, które Twój kod musi obsłużyć w ciągu jednej minuty (każda), ale w zasadzie powinno działać dla większych danych wejściowych. Możesz użyć niektórych z poniższych M = 10przypadków testowych, aby to sprawdzić:

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
źródło

Czy wypełnienie jak największej liczby miejsc jest obowiązkowe?

feersum

7

Chyba miał lepszą czekać na mój turn()przed I help()wasget() żadnych odpowiedzi load(), albo może muszę ping()cię od void()po I spark()i crash()..... człowiek ...

FryAmTheEggman

@feersum Tak, wszystkie Nfunkcje są w użyciu.

Martin Ender

18

CJam (56 bajtów)

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$

$λ_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$

Tak więc dla każdej partycji jest liczba dystrybucji funkcji

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

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

Powyższy kod oblicza partycje przy użyciu tego samego podejścia, co Dennis (jest oczywisty i krótki, choć niezbyt skalowalny), a następnie przetwarza każdą partycję w tablicę podobną do tej, [N X λ_0-1 ... λ_k-1 μ_1 μ_2 μ_3]w której może podnieść funkcję silnią, a następnie złożyć podział.

Peter Taylor
źródło

9

CJam, 74 67 bajtów

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

Sprawdziłem wszystkie przypadki testowe na komputerze stacjonarnym za pomocą interpretera Java . Zajęło to 2,2 sekundy dla 1 ≤ M ≤ 8 i 3,5 minuty dla M = 10 .

Próbować to skrzypce w interpretatorze CJam lub sprawdź jednocześnie pierwsze 84 przypadki testowe .

Pomysł

Zasadniczo możemy wypełnić każde aktywne miejsce i odpowiadające mu miejsce ulepszeń funkcjami 0 , 1 , 2 lub 3 . W przypadku 4-minutowych slotów bierzemy wszystkie wektory V z {0, 1, 2, 3} ^M i odfiltrowujemy te, dla których suma (V)> N (więcej funkcji w szczelinach nie pasywny niż całkowite dostępnych funkcji) lub sumy ( V) + M <N (niewystarczająca liczba pasywnych gniazd dla nieaktywnych funkcji). Sortujemy i deduplikujemy wszystkie przechowywane wektory, ponieważ kolejność rodzin gniazd nie jest ważna.

Przy funkcjach N i funkcjach V = (x ₁ ,…, x _M ) w nie pasywnych częściach rodzin gniazd, obliczamy liczbę kombinacji w następujący sposób:

Jeśli x ₁ = 0 , dla tej rodziny gniazd jest tylko jedna możliwość.

Jeśli x ₁ = 1 , istnieje N możliwości, ponieważ mamy N funkcji, a funkcja musi przejść do aktywnego gniazda.

Jeśli x ₁ = 2 , musimy umieścić jedną funkcję w aktywnym gnieździe, a drugą w gnieździe aktualizacji (nie ma znaczenia, który). Istnieje aktywny wybór N dla aktywnego slotu i N-1 pozostały wybór dla slotu ulepszeń, co daje łącznie N (N-1) kombinacji.

Jeśli x ₁ = 3 , istnieje N opcji dla aktywnego gniazda, N - 1 pozostałe opcje dla pierwszego slotu aktualizacji i N - 2 dla drugiego slotu aktualizacji. Ponieważ miejsca na ulepszenia nie mają kolejności, liczy się każda kombinacja dwa razy, więc istnieją unikalne kombinacje N (N - 1) (N - 2) .

W każdym razie istnieje N! / ((N - x ₁ )! × (x ₁ - 1)! Kombinacje dla tej rodziny.
Zużyliśmy x funkcji ₁ , więc ustaw N: = N - x ₁ i powtórz krok 1 dla x ₂ , a następnie x ₃ itd.
Jeśli V zawiera duplikaty, iloczyn powyższych wyników policzy wszystkie kombinacje wiele razy. Dla każdego unikalnego elementu V , jeśli występuje on r razy w V , istnieje r! równoważne sposoby ułożenia tych rodzin gniazd, więc wynik z góry musi być podzielony przez r! .
Ostatecznym wynikiem jest liczba unikalnych kombinacji dla tego V .

Aby obliczyć całkowitą liczbę unikalnych kombinacji, wystarczy obliczyć sumę wyników dla każdej z nich V .

Kod

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
źródło

Kombinatoryka tranzystora

Wyzwanie

Przypadki testowe

Odpowiedzi:

CJam (56 bajtów)

CJam, 74 67 bajtów

Pomysł

Kod