Wyzwanie
Wyobraźmy sobie N
liczbę liczb całkowitych od 0 do M
włącznie i nazwijmy to F
.
Są (M + 1) ** N
możliwe F
s w sumie.
Ile takich F
spełnia wszystkie następujące nierówności (indeks jest oparty na jednym)?
F[n] + F[n+1] <= M
dla1 <= n < N
F[N] + F[1] <= M
Napisać program lub funkcję, która pobiera dwie liczby całkowite dodatnie N
a M
i wysyła odpowiedź w dowolnej dogodnej postaci.
Przypadki testowe
(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
Wyjaśnienie
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)
Zasady
- Jest to wyzwanie o ograniczonej złożoności . Złożoność czasowa kodu powinna być wielomianowa
M
iN
(np. Nie można wygenerować wszystkich(M + 1) ** N
krotek, a następnie sprawdzić warunek). Proszę wyjaśnić swoje podejście w swoim zgłoszeniu. - Obowiązują standardowe zasady gry w golfa . Najkrótsza odpowiedź w bajtach wygrywa.
code-golf
restricted-complexity
Bubbler
źródło
źródło
mat(...,int)
nie wydaje się działać w tychn=100
przypadkach. Metoda jest poprawna (na przykład sympy do sumowania mocy pierwiastków charakterystycznego wielomianu działa, na przykład), ale numpy idzie gdzieś nie tak, jak rosną liczby (może to jest**
operator mocy?)Pyth , 27 bajtów
Demonstracja
Oczekuje danych wejściowych w formacie:
Jest to klasyczne programowanie dynamiczne, nad lewym końcem ustawionych do tej pory wartości, prawym końcem i bieżącym rozmiarem.
Jak to działa, w pseudokodzie / Pythonie:
Q
jest używany doM
,z
jest używanyN
,:
jestfill
,N
jestleft
,T
jestright
,Y
jestgap
.źródło
MATL ,
1312 bajtówWypróbuj online! To jest bezpośrednie tłumaczenie odpowiedzi Xnora na Python i mojej pierwszej odpowiedzi MATL, więc najprawdopodobniej nie jest optymalne. Np. Istnieje prawdopodobnie krótszy sposób, aby uzyskać górną lewą trójkątną matrycę jedności niż
t&lYRP
. Edycja: I okazuje się, że jest:&>~P
. Dzięki Luis Mendo za -1 bajt!źródło
Stax , 17 bajtów
Uruchom i debuguj
Rozpakowane, niepolowane i skomentowane, wygląda to tak.
Uruchom ten
źródło
R , 72 bajty
Wypróbuj online!
Podejście do Xnora.
Nie udaje się w przypadku większych przypadków testowych, ponieważ R ma jedynie 32-bitową obsługę liczb całkowitych (są one rzutowane na wartość
double
po osiągnięciu maksymalnej wartości int), więcgmp
wymagane byłoby użycie innej biblioteki arytmetycznej o dowolnej dokładności.O dziwo, R nie ma operatora mocy macierzy, jak
^
zawsze stosuje się elementarnie.źródło
%^%
w pakiecie jest poprawnie zaimplementowany operatorexpm
, który pozwalałby na -5 bajtów , ale niestety nie jest on dostępny w TIO (musiałem przetestować lokalnie).function(M,N)sum(diag(expm::`%^%`(outer(0:M,0:M,"+")<=M,N)))