Opis
Biorąc pod uwagę długość n
i rozmiar alfabetu k>0
, twój program musi określić liczbę ciągów znaków z tymi parametrami, które mają maksymalną liczbę unikalnych podciągów. W przypadku k=2
generuje to OEIS A134457 .
Przykład
Na przykład, 2210
ma podciągi ,
2
, 22
, 221
, 2210
, 2
, 21
, 210
, 1
, 10
, i 0
, w sumie 11. Niemniej jednak, 2
pojawia się dwa razy, tak że ma tylko 10 niepowtarzalnych podciągów.
Jest to możliwe, aż do długości łańcucha 4 zawierającej 3 różne symbole, ale że wiąże się z 35 innych łańcuchów w sumie 36 tieing łańcuchów tym 0012
, 2101
oraz 0121
. Dlatego dla n=4
i k=3
twój program powinien wypisać 36.
Przypadki testowe
n k output
0 5 1
1 3 3
5 1 1
9 2 40
2 3 6
5 5 120
code-golf
combinatorics
użytkownik1502040
źródło
źródło
n=2
,k=3
wyjście 911,12,21,22,31,32,33,13,23
:?Odpowiedzi:
Galaretka , 9 bajtów
Wypróbuj online!
Wprowadź w odwrotnej kolejności. Brutalna siła.
źródło
ṗẆQ$€ZṪL
Pyth, 12 bajtów
Wypróbuj online.
Czysta brutalna siła.
Wyjaśnienie
Q
do programu.n
) wQ
.E
: przeczytaj i oceń linię input (k
).U
: uzyskać zasięg[0, ..., k-1]
.^
: pobierzn
ciągi wszystkich długości[0, ..., k-1]
..M
: znajdź te, które dają maksimum funkcjif(Z)
:.:Z
: znajdź podciągi dlaZ
{
: usuń duplikatyl
: uzyskaj liczbę unikalnych podciągówl
: uzyskaj liczbę takich ciągówźródło
Mathematica, 96 bajtów
źródło
Haskell, 82 bajty
Przykład użycia:
9 # 2
->40
.Jak to działa:
źródło