Mamy 40 drążków o tej samej szerokości, ale różnych wysokościach. Ile jest możliwych ustawień, aby umieścić je obok siebie, aby spojrzeć z prawej strony na 10 drążków, a kiedy spojrzeć z lewej strony, ponownie zobaczymy dokładnie 10 drążków?
Na przykład takie zamówienie to:
Czarne patyki są ukryte, czerwone patyki są widoczne, gdy patrzysz z lewej strony, niebieskie patyki są widoczne, gdy patrzysz z prawej strony, a fioletowe (tj. Najdłuższe) to te, które można zobaczyć z obu stron.
Jako przypadki testowe:
- Gdybyśmy mieli 3 drążki liczba zamówień, aby zobaczyć 2 z lewej, a 2 z prawej to 2
- Gdybyśmy mieli 5 drążków liczba zamówień, aby zobaczyć 3 z lewej, a 3 z prawej to 6
- Gdybyśmy mieli 10 drążków liczba zamówień, aby zobaczyć 4 z lewej, a 4 z prawej to 90720
code-golf
combinatorics
permutations
Kumpel
źródło
źródło
10!/40 = 90720
... czy to zbieg okoliczności?Odpowiedzi:
PARI / GP, 80
Liczba widocznych drążków jest również nazywana liczbami wieżowców , po grze ołówkiem / siatką. Ten kod jest oparty na (tylko nieznacznie zmienionej) formule z OEIS A218531 . Nie znam dużo PARI, ale tak naprawdę nie sądzę, że jest tu dużo golfa.
Przypadki testowe są pokazane na ideone.com . Wynik
f(40,10)
jest następujący:źródło
v
patyczkami widocznymi z lewej strony to liczba Stirlingas(n,v)
. Jeśli najwyższy drążek znajduje się na pozycjik
, to drążki widoczne po lewej stronie są drążkami, a drążki widoczne po lewej stronie w permutacji na lewo odk-1
wartości po lewej stronie pozycjik
. Tak więc, aby miećv
patyczki widoczne z lewej strony i patyczki widoczne zv
prawej strony, możnas(k,v-1)
dokonać permutacji lewej połowy,s(n-k-1,v-1)
permutacji prawej połowy ibinomial(n-1,k)
podzielić pałeczki na dwie połowy.f(n,v,s=stirling)=abs(sum(k=1,n--,binomial(n,k)*s(k,v-1)*s(n-k,v-1)))
. Zapisujesterling
to zmienną do ponownego użycia, pomija ostatni argument, ponieważ 1 jest wartością domyślną i odejmuje 1 od n jeden raz, a nie trzy razy.Python 3, 259 bajtów
Nie bardzo z tego zadowolony.
Przykładowe dane wejściowe i wyjściowe:
Generuje wszystkie możliwe kombinacje podanego zakresu, a następnie przechodzi przez nie, sprawdzając każdą liczbę w nich, aby sprawdzić, czy jest równa maksymalnej liczbie poprzednich liczb. Następnie robi to samo do tyłu, a jeśli liczba do przodu (t) = liczba do tyłu (d) = podany numer widoku (k) jest prawidłowy. Dodaje to do licznika (c) i drukuje to na końcu.
źródło
R 104
Trochę grałem w golfa:
źródło
Pyth -
3836 bajtówZasadniczo port odpowiedzi R. Dość wolno, nawet nie można ukończyć
10, 4
online.Jedyne, czego Pyth nie ma, to cummax i
==
wektory ponad, ale te zajęły tylko kilka bajtów do wdrożenia.Wyjaśnienie i dalsza gra w golfa już wkrótce.
Wypróbuj tutaj online .
źródło