Zaczerpnięte z: OEIS- A071816
Twoim zadaniem, biorąc pod uwagę górną granicę n
, jest znalezienie liczby rozwiązań, które spełniają równanie:
a+b+c = x+y+z, where 0 <= a,b,c,x,y,z < n
Sekwencja zaczyna się zgodnie z opisem na stronie OEIS i jak poniżej (1-indeksowany):
1, 20, 141, 580, 1751, 4332, 9331, 18152, 32661, 55252, 88913, 137292, 204763, 296492, 418503, 577744, 782153, 1040724, 1363573, 1762004, 2248575, 2837164, 3543035, 4382904, 5375005, 6539156, 7896825, 9471196, 11287235, 13371756
Ponieważ n = 1
istnieje tylko jedno rozwiązanie:(0,0,0,0,0,0)
Dla n = 2
istnieją 20 zamawiane rozwiązania (a,b,c,x,y,z)
do a+b+c = x+y+z
:
(0,0,0,0,0,0), (0,0,1,0,0,1), (0,0,1,0,1,0), (0,0,1,1,0,0), (0,1,0,0,0,1),
(0,1,0,0,1,0), (0,1,0,1,0,0), (0,1,1,0,1,1), (0,1,1,1,0,1), (0,1,1,1,1,0),
(1,0,0,0,0,1), (1,0,0,0,1,0), (1,0,0,1,0,0), (1,0,1,0,1,1), (1,0,1,1,0,1),
(1,0,1,1,1,0), (1,1,0,0,1,1), (1,1,0,1,0,1), (1,1,0,1,1,0), (1,1,1,1,1,1).
I & O
- Dane wejściowe oznaczają pojedyncze liczby całkowite
n
. - Dane wyjściowe to pojedyncza liczba całkowita / ciąg znaków
f(n)
, gdzief(...)
jest funkcja powyżej. - Indeksowanie jest dokładnie takie, jak opisano, żadne inne indeksowanie nie jest dopuszczalne.
To jest golf golfowy , wygrana o najniższej liczbie bajtów.
Odpowiedzi:
Galaretka ,
96 bajtówRoztwór O (n 6 ) .
Wypróbuj online!
Jak to działa
źródło
O(n^6)
chociaż: P.Mathematica 17 lub 76 bajtów
Za pomocą wzoru:
(Zapisano 3 bajty na @GregMartin i @ngenisis)
Zamiast używać formuły, tutaj dosłownie obliczam wszystkie rozwiązania i je liczę.
źródło
11/20
przez.55
do oszczędności dwu-bajtowych.Haskell , 48 bajtów
Nie zauważyłem formuły przed napisaniem tego, więc zdecydowanie nie jest to najkrótsza (lub najszybsza) ogólna metoda, ale myślałem, że była ładna.
Wypróbuj online!
f n
generuje wszystkie listy 6 elementów[1..n]
, a następnie zlicza te, których suma naprzemienna wynosi 0. Wykorzystuje fakt, którya+b+c==d+e+f
jest taki sam jaka-(d-(b-(e-(c-f))))==0
, a także, że nie ma znaczenia, jeśli dodamy 1 do wszystkich liczb.źródło
MATL , 12 bajtów
Wypróbuj online!
Wyjaśnienie
Nie mogłem przegapić okazji do ponownego użycia splotu!
Wykorzystuje to następującą charakterystykę z OEIS:
i oczywiście mnożenie wielomianowe to splot.
źródło
Galaretka , 9 bajtów
Nie tak krótki jak @ Dennis's, ale kończy się w mniej niż 20 sekund na wejście
100
.Wypróbuj online!
Jak to działa
źródło
Pyth,
1312 bajtówOszczędność jednego bajtu dzięki Dziurawej Zakonnicy.
Wyjaśnienie
źródło
/LJJ
zamiastm/JdJ
.Python 3 , 28 bajtów
Wypróbuj online!
źródło
TI-BASIC, 19 bajtów
Ocenia formułę OEIS.
źródło
Prompt x
= 2 bajty?Oaza , 17 bajtów
Wypróbuj online!
Oasis to język oparty na stosie, zoptymalizowany pod kątem powtarzających się sekwencji. Jednak formuła rekurencji byłaby w tym przypadku zbyt długa.
źródło
Brachylog , 17 bajtów
Wypróbuj online!
Wyjaśnienie
źródło
ᶜ
powinienem automatycznie przyjechać≜
ᶜ
sam, to metapredykat.JavaScript, 24 bajty
Wykorzystuje formułę ze strony OEIS.
Wypróbuj online!
źródło
x=>x**5*.55+x**3/4+x/5
Oktawa ,
252321 bajtówWypróbuj online!
Wykorzystuje wzór z wpisu OEIS. Zaoszczędzono
dwacztery bajty , zmieniając formułę i używając.55
zamiast11/20
, dzięki fəˈnɛtɪk.źródło
Python 2.7,
1091059996 bajtówDzięki ETHproductions i Dennis za zaoszczędzenie kilku bajtów:
źródło
sum(sum(x[:3])==sum(x[3:])for x ...)
byłby jeszcze krótszy. Ponadtofrom itertools import*
oszczędza bajt.for
. Nie wymagamy też domyślnego nadawania nazw funkcjom, aby można je było usunąćh=
.Mathematica, 52 bajty
Implementacja formuły OEIS przez Kelly Lowder jest znacznie krótsza, ale oblicza to bezpośrednio:
Cóż, w rzeczywistości liczy się liczba rozwiązań
1 <= a,b,c,x,y,z <= n
. Jest to ta sama liczba, ponieważ dodanie 1 do wszystkich zmiennych nie zmienia równości.Objaśnienie:
Range@#~Tuples~6
tworzy wszystkie listy sześciu liczb całkowitych od 1 do n,#~Partition~3&/@
dzieli każdą listę na dwie listy o długości 3,Tr/@
sumuje te listy podrzędne iCount[...,{n_,n_}]
liczy, ile par ma taką samą sumę. Miałem dużo szczęścia w kolejności pierwszeństwa międzyf @
,f /@
a~f~
!źródło
Oktawa , 41 bajtów
Wypróbuj online!
Podobnie do mojej odpowiedzi MATL , ale oblicza splot za pomocą dyskretnej transformaty Fouriera (
fft
) z wystarczającą liczbą punktów (n^2
).~~(1:n)
jest używany jako krótsza wersjaones(1,n)
.round
jest konieczne z powodu błędów zmiennoprzecinkowych.źródło
CJam , 17 bajtów
Wprowadzanie
11
limitów czasu w TIO12
i więcej kończy się pamięć.Wypróbuj online!
Wyjaśnienie
źródło
Clojure, 79 bajtów
Mnóstwo powtórzeń w kodzie, przy większej liczbie zmiennych makro może być krótsze.
źródło