Wyzwanie

W tym zadaniu obliczyłeś, w jaki sposób możemy rozdzielić kule A do komórek B, przy czym każda komórka ma co najmniej jedną piłkę.

Wejścia A i B podane są w jednym wierszu oddzielonym spacją, wejścia są zakończone przez EOF.

Może chcesz sprawdzić swoje rozwiązania tutaj .

Wejście

0 0
1 0
12 4
6 3
18 17
20 19
15 13
18 9
20 20
17 14
9 2
14 13
18 11

Wynik

1
0
14676024
540
54420176498688000
23112569077678080000
28332944640000
38528927611574400
2432902008176640000
21785854970880000
510
566658892800
334942064711654400

Ograniczenia

• Każde A i B można rozróżnić.
• 0 <= A, B <= 20
• Możesz użyć dowolnego wybranego języka
• Najkrótsze rozwiązanie wygrywa!

JavaScript (90 93 )

function f(a,b){n=m=r=1;for(i=b;i>0;n*=-1){r+=n*m*Math.pow(i,a);m=m*i/(b-i--+1)}return--r}

http://jsfiddle.net/RDGUn/2/

Oczywiście, każdy język oparty na matematyce, taki jak APL, pokona mnie z powodu gadatliwości składni i braku wbudowanych konstrukcji matematycznych :)

Edytuj Poza tym nie mam żadnych funkcji związanych z wprowadzaniem danych, z wyjątkiem parametrów przekazanych do funkcji, nie jestem pewien, jak korzystać ze standardowych danych wejściowych w JavaScript ...

Edycja: przejście i--do m=m*wyrażenia; wprowadzić n*=-1się for; zacznij r=1łączyć zadania i usuwać te obce po powrocie. (zapisz 3 znaki)

Golfscript - 56 50 49 48 41 40 38 37 znaków

n%{~),{!}%\{0.@{.@+2$*@)@}/;;]}*)p;}/

Uwaga: obsługuje wiele linii danych wejściowych, jest szybki (1/8 sek., Aby wykonać przypadki testowe) i nie psuje się w przypadku legalnych danych wejściowych.

(Pierwsza wersja była również moim pierwszym programem do gry w golfa; dzięki eBiznesowi za wskazanie kilku sztuczek, które przegapiłem).

Aby uczynić go również użytecznym postem edukacyjnym, oto wyjaśnienie, jak to działa. Zaczynamy od nawrotu f(n, k) = k * (f(n-1, k) + f(n-1, k-1)). Można to zrozumieć kombinatorycznie, mówiąc, że aby umieścić nwyróżniające się kule w kwyróżniających się wiadrach, tak aby każde wiadro zawierało co najmniej jedną piłkę, wybierasz jedno z kwiader dla pierwszej piłki ( k *), a następnie albo będzie ona zawierać co najmniej jeszcze jedną piłkę ( f(n-1, k)) albo nie będzie ( f(n-1, k-1)).

Wynikające z tego wartości tworzą siatkę; przyjmując njako indeks wiersza i kjako indeks kolumny i indeksując oba od 0, zaczyna się

1   0   0   0    0    0   0 ...
0   1   0   0    0    0   0 ...
0   1   2   0    0    0   0 ...
0   1   6   6    0    0   0 ...
0   1  14  36   24    0   0 ...
0   1  30 150  240  120   0 ...
0   1  62 540 1560 1800 720 ...
.   .   .   .    .    .   . .
.   .   .   .    .    .   .  .
.   .   .   .    .    .   .   .

Wracając do programu,

n%{~ <<STUFF>> }/

dzieli dane wejściowe na linie, a następnie dla każdej linii ocenia je, umieszczając ni kna stosie, a następnie wywołuje <<STUFF>>, co jest następujące:

),{!}%\{0.@{.@+2$*@)@}/;;]}*)p;

Oblicza to pierwsze k+1wpisy w n+1th rzędzie tej siatki. Początkowo stos jest n k.
),daje stos n [0 1 2 ... k]
{!}%daje stos n [1 0 0 ... 0]gdzie są k0.
\{ <<MORE STUFF>> }*przynosi ndo góry i sprawia, że wiele razy wykonujemy <<MORE STUFF>>.
Nasz stos jest obecnie rzędem tabeli: [f(i,0) f(i,1) ... f(i,k)]
0.@stawia kilka zer przed tą tablicą. Pierwszy będzie, ja drugi będzie f(i,j-1).
{ <<FINAL LOOP>> }/zapętla się przez elementy tablicy; dla każdego z nich kładzie go na stosie, a następnie wykonuje ciało pętli.
.@+2$*@)@to nudna manipulacja stosami, aby zabrać ... j f(i,j-1) f(i,j)i ... j*(f(i,j-1)+f(i,j)) j+1 f(i,j)
;;]wyskoczyć z resztekk+1 f(i,k)i zbiera wszystko do tablicy, gotowe do następnego okrążenia.
Wreszcie, gdy wygenerowaliśmy nth rząd tabeli,
)p;bierze ostatni element, drukuje go i odrzuca resztę wiersza.

Dla potomnych trzy rozwiązania 38 znaków na tej zasadzie:
n%{~),{!}%\{0.@{.@+@.@*\)@}/;;]}*)p;}/
n%{~),{!}%\{0:x\{x\:x+1$*\)}/;]}*)p;}/
n%{~),{!}%\{0.@{@1$+2$*\@)}/;;]}*)p;}/

J, 40

4 :'|-/x(^~*y!~])i.1x+y'/&.".;._2(1!:1)3 

Na przykład

4 :'-/((x^~|.@:>:)*y&(!~))i.y'/x:".>{.;:(1!:1)3
15 13
28332944640000

<1sek dla wszystkich przypadków testowych.

Edycje

• (52 → 47) Zmniejsz za pomocą -/zamiast na przemian (1 _1)*(pomysł JB)
• (47 → 53) Zauważone zapotrzebowanie na dane wielowierszowe: - /
• (53 → 48) Wykorzystaj symetrię dwumianów.
• (48 → 48) Bądź milczący!
• (48 → 41)
• (41 → 40) Ściśnij przyrost + konwersja do1x+

Common Lisp (83)

(defun b (x y)
  (if (= (* x y) 0)
      (if (= (+ x y) 0) 1 0)
      (* y (+ (b (decf x) y) (b x (1- y)))))))

Wydaje się, że powinien istnieć krótszy sposób na przetestowanie bazowych przypadków, ale nic nie przychodzi mi do głowy od razu.

J, 38–42

W zależności od preferencji dotyczących interaktywnych języków i prezentacji wyników, wybierz spośród spektrum rozwiązań J:

• 38 najkrótsza interaktywna: 4 :'|-/(!&y*^&x)i.1x+y'/&".;._2(1!:1)3
  Uruchom jconsole, wprowadź go, a następnie wklej dane wejściowe (zakończ Cd). Zauważysz, że dane wyjściowe są rozdzielone spacjami (J jest językiem wektorowym, wykonuje obliczenia dla całego wejścia jako całości i zwraca je jako wektor 1D, którego domyślna prezentacja znajduje się w jednym wierszu). Uważam, że ok, duchem tego problemu jest obliczenie, a nie prezentacja. Ale jeśli nalegasz, aby zamiast tego mieć nowe linie:
• 39 dłużej interaktywny: 4 :'|-/(!&y*^&x)i.1x+y'/&.".;._2(1!:1)3
  Zastąpienie Compose ( &) wartością Under ( &.) zwraca wektor ciągów znaków, których prezentacja kończy się na osobnych wierszach.
• 42 tryb wsadowy: 4 :'echo|-/(!&y*^&x)i.1x+y'/&".;._2(1!:1)3
  Uruchom z wiersza polecenia jako$ jconsole balls.ijs < balls.in

Jeśli zagłosowałeś za tym, być może zechcesz również dać uznanie rozwiązaniu Eelvex .

GolfScript - 45 38 36 znaków

Relacja powtarzalności brudnej implementacji o średniej sile ( 38 36 znaków):

n%{~{.2$*{\(.2$f\2$(f+*}{=}if}:f~p}/

Relacja powtarzalności, którą ukradłem z rozwiązania Petera Taylorsa, wygląda następująco:

f(x, y) = y * ( f(x-1, y) + f(x-1, y-1) )

W szczególnych przypadkach, jeśli jedna ze zmiennych ma wartość 0.

Moja implementacja nie wykorzystuje ponownie poprzednich wyników, więc każde wywołanie funkcji rozgałęzia się do dwóch nowych wywołań, chyba że jeden z zerowych przypadków został osiągnięty. Daje to najgorszy przypadek wywołania funkcji 2 ^ 21-1, co zajmuje 30 sekund na moim komputerze.

Rozwiązanie serii Light-force (45 znaków):

n%{~.),0\{.4$?3$,@[>.,,]{1\{)*}/}//*\-}/p;;}/

J, 55 znaków

(wd@(4 :'(y^x)--/(!&y*^&x)|.i.y')/@".@,&'x');._2(1!:1)3

• Przechodzi bieżące przypadki testowe. Myślę , że rozumiem matematykę ...
• j602, tylko konsola ( wd). Wejście na stdin, wyjście na stdout.

Skrypt testowy Bash:

jconsole disballs.ijs <<END
12 4
6 3
END

Golfscript - 26 znaków

Ostrzeżenie: obudowa 12 4 wymaga dużo pamięci (choć nie tyle, co odpowiedź poniżej) i jej uruchomienie zajmuje sporo czasu

~:)\?:x,{x+)base(;.&,)=},,

Oczywiście ta odpowiedź ma pewne problemy, ale zostawię ją tutaj, ponieważ odnoszą się do niej komentarze, a odpowiedź mellamokb jest oparta na niej.

Golfscript - 24 znaki

Ostrzeżenie: obudowa 12 4 wymaga dużo pamięci i jej uruchomienie zajmuje sporo czasu

~:o)\?,{o)base[0]-,o=},,

Python 140 znaków

import sys
f=lambda n,k:(n and k and n>=k and k*(f(n-1,k-1)+f(n-1,k)))or(n+k==0 and 1)or 0
for l in sys.stdin:print f(*(map(int,l.split())))

dc, 100 znaków

[0q]s5[1q]s6[l2l3>5l3 0>5l2 0=6l2 1-S2l3dS3 1-S3l1xL3s9l1xL2s9+L3*]s1[?z0=5S3S2l1xL3L2+s9fs9l4x]ds4x

Niestety, dc nie wydaje się być obsługiwany przez ideone. Może być jeszcze jedna lub dwie postaci do wyciśnięcia, ale przed snem.

Uwaga: obsługuje wiele wierszy danych wejściowych, ma wystarczającą precyzję, aby dać poprawne wyjście nawet dla 20 19(przekląć cię, Perlu, za czas, który zmarnowałem na debugowanie mojego rozwiązania!), I daje prawidłowe wyjście 0 0.

Sugestie Nabb pozwalają na skrócenie przynajmniej o tyle

[0q]sZ[1q]sI[?z0=ZSkSn[lnlk>Zlk0>Zln0=Iln1-SnlkdSk1-SklFxLks9lFxLns9+Lk*]dsFxfs9l4x]ds4x

kosztem pozostawienia śmieci w stosach rejestru (a zatem zabraknie pamięci, jeśli obliczymy miliardy odpowiedzi).

Golfscript (28 31 37 )

~):$\.($\?:@;?,{@+}%{$base$,\-[0]=},,

Modyfikacja gnibblerrozwiązania GolfScript. Myślę, że jest to działające rozwiązanie - przetestowane z [3,2], [4,2], [6,3] i [9,2] z poprawnymi odpowiedziami. (Użyłem $i @dla zmiennych, aby zmniejszyć przestrzeń wokół basesłowa kluczowego).

Istnieją dwa problemy z gnibblerobecnym rozwiązaniem.

1. Sprawdzanie długości po usunięciu [0] nie gwarantuje rozwiązania, ponieważ [1,1,1,1] będzie ważne dla danych wejściowych [4,2], mimo że wszystkie 4 kulki znajdują się w tej samej komórce (1). Zmodyfikowałem więc, aby sprawdzić, czy wszystkie cyfry są użyte, tj. Tablica zawiera 1-2, więc każda komórka zawiera co najmniej jedną kulkę.
2. W przypadku danych wejściowych [4,2] podstawowy format 3 liczb 0–27 ma mniej niż 4 cyfry, a skrajne lewe 0 nie są uwzględniane. Oznacza to, że [1,1] jest uwzględnione jako prawidłowe rozwiązanie, nawet jeśli technicznie faktycznie jest to [0,0,1,1], co oznacza, że ​​pierwszych dwóch piłek nie umieszcza się nigdzie. Naprawiam, dodając 3 ^ 3 do każdego wpisu (ogólnie k ^ n-1 do tablicy wpisów k ^ n), dzięki czemu pierwsze wpisy są przesunięte w górę do posiadania co najmniej n-cyfr w formacie base-k, a ostatni wpisy i tak będą automatycznie nieważne i nie wpłyną na rozwiązanie (ponieważ druga cyfra zawsze będzie wynosić 0).

Edytować

~:@\?:$,{$+}%{@base(;@,\-,0=},,

`~:@\?:$,{$+@base(;@,\-,0=},,`

Jeszcze lepsze rozwiązanie! Nie trzeba zwiększać, po prostu dodaj do wszystkich liczb, aby zaczynały się od [1], a po dekonowaniu tej pierwszej cyfry nie zabraknie żadnych cyfr (w tym lewe dopełnianie zer). To rozwiązanie powinno działać i zostało przetestowane z tymi samymi wpisami powyżej. Jest także o wiele szybszy, ponieważ nie zwiększamy wartości przed wzięciem wykładnika do wygenerowania tablicy (ale nadal cierpi z powodu tego samego problemu z wydajnością / pamięcią dla większych danych wejściowych).

Edycja : Użyj gnibblerpomysłu przeniesienia dodatku $wewnątrz filtra zamiast dodatkowego kroku. (zapisz 3 znaki).

05AB1E , 19 bajtów

#D`ULX.Œʒ€gßĀ}gs_P+

UWAGA: Jest bardzo wolny i już upłynął limit czasu 12 4. Działa jednak zgodnie z przeznaczeniem. Zobaczę, czy mogę wymyślić alternatywną metodę, która działa we wszystkich przypadkach testowych w rozsądnym czasie. Poniżej znajduje się znacznie szybsza wersja, która uruchamia wszystkie przypadki testowe w mniej niż sekundę.

Wypróbuj online lub sprawdź kilka (mniejszych) przypadków testowych .

Wyjaśnienie:

#               # Split the (implicit) input-string by spaces
 D              # Duplicate it
  `             # Push both values to the stack
   U            # Pop and store the second value in variable `X`
    L           # Create a list in the range [1,n] for the first value
     X.Π       # Create a list of all possible ways to divide this list into `X` partitions
                # (including empty sublists, so we'll have to filter them out:)
        ʒ       # Filter this list of lists of partition-lists by:
         €g     #  Get the length of each partition-list
           ß    #  Get the minimum length
            Ā   #  Truthify; 0 remains 0 (falsey); anything else becomes 1 (truthy)
             }g # After the filter, take the length to get the amount left
 s              # Swap so the duplicated input-list is at the top of the stack again
  _             # Check for each value if they're equal to 0 (1 if truthy; 0 if falsey)
   P            # Take the product of the two to check if both input-values are 0
    +           # And add it to the earlier calculated product (edge case for [0,0] = 1)
                # (After which the result is output implicitly)

05AB1E , 29 bajtów

Oto znacznie szybsza wersja, która działa na wszystkich testach w około 0,5 sekundy na TIO:

Î#R`V©LRvyYmX*NÈ·<*+Xy*®y->÷U

Port odpowiedzi JavaScript @mellamokb , więc upewnij się, aby go upvote!

Wypróbuj online lub sprawdź wszystkie przypadki testowe .

Wyjaśnienie:

Î                    # Push (result=) 0 and the input
 #                   # Split the input by spaces
  R`                 # Push the values to the stack reversed
    V                # Pop and store the first value in variable `Y`
     ©               # Store the second value in variable `®` (without popping)
      LRv            # Loop `y` in the range [`®`,1], with index `N` in the range [0,`®`):
         yYm         #  Calculate `y` to the power `Y`
            X*       #  Multiply it by `X`
                     #  (Note: `X` is 1 before setting it to another value initially)
              NÈ     #  Check if index `N` is even (1 if truthy; 0 if falsey)
                ·<   #  Double it; and decrease it by 1 (1 if truthy; -1 if falseY0
                  *  #  Multiply it to the earlier number
                   + #  And add it to the result
         Xy*         #  Push `X` multiplied by `y`
         ®y->        #  Push `®` - `y` + 1
             ÷       #  Integer divide them
              U      #  Pop and store it as new variable `X`
                     # (output the result at the top of the stack implicitly after the loop)

UWAGA: 0 0W tym przypadku działa na wielkość liter (w przeciwieństwie do odpowiedzi JavaScript, z której przeniosłem tę metodę), ponieważ Lwbudowana funkcja utworzy listę [0,1].