Przygotuj się na śmierć?

tło

Jednym ze źródeł ennui w stołowych grach RPG jest rzut na wiele kości. Rzucenie zaklęcia Dezintegracji może być natychmiastowe, ale rzucanie i łączenie 40 kości na pewno nie jest!

Szereg sugestii dotyczących rozwiązania tego problemu omówiono na stronie rpg.stackexchange.com . Jednak niektóre z nich, takie jak używanie programu na kółkach lub uśrednianie kości, zabierają graczom trochę zabawy i kontroli. Inne, takie jak rzucanie 4 kostkami i pomnożenie sumy przez 10, sprawiają, że wyniki są znacznie bardziej wahliwe (podczas gdy uśrednianie kości działa w przeciwnym kierunku).

To pytanie dotyczy metody zmniejszania liczby rzutów kostką bez zmiany ani średniego wyniku (średnia), ani jego zmienności (wariancji).

Notacja i matematyka

W tym pytaniu użyjemy następującej notacji do przedstawienia rzutów kostką:

• n d K (np 40d6) oznacza sumę n rolek k-kostka.
• n d k * c (np. 4d6 * 10) opisuje pomnożenie wyniku przez stałą c.
• Możemy również dodawać rolki (np. 4d6 * 10 + 40d6) i stałe (np. 4d6 + 10).

W przypadku pojedynczego rzutu kostką możemy pokazać, że:

• Średnia : E [1d k ] = (k + 1) / 2
• Wariancja : Var (1d k ) = (k-1) (k + 1) / 12

Korzystając z podstawowych właściwości średniej i wariancji, możemy ponadto wnioskować, że:

• Oznacza : E [ m d k * a + n d l * b + c ] = am .E [1d k ] + bn . [1d l ] + c
• Wariancja var ( m d k * + n d l * b + c ] = . ² m .Var (1d k ) + b ². N .Var (1d L )

Zadanie

Biorąc pod uwagę trzy liczby całkowite n , k i r , Twój program powinien wypisać sposób zbliżony n d k w co najwyżej r rolkach, z następującymi ograniczeniami:

• Rozwiązanie powinno mieć taką samą średnią i wariancję jak n d k .
• Rozwiązanie powinno zawierać największą możliwą liczbę rolek mniejszą lub równą r , ponieważ większa liczba rolek zapewnia płynniejszy rozkład.
• Powinieneś ograniczyć swoje rozwiązania tylko do używania k- stronnych kości, chyba że celujesz w Bonus (patrz poniżej).
• Jeśli nie ma rozwiązania (ponieważ r jest za małe), program powinien wypisać ciąg „JESTEM SEKSOWNYM BUTEM BOGA WOJNY!”.
• Parametry są przekazywane jako pojedynczy ciąg rozdzielany spacjami.
• Możesz założyć, że 1 ≤ n ≤ 100, 1 ≤ r ≤ n i że k jest jednym z 4, 6, 8, 10, 12 i 20 (standardowe kostki używane w blatach).
• Dane wyjściowe powinny mieć format opisany w Notacji (np. 4d6 * 10 + 5), z opcjonalnymi spacjami wokół + s, ale nigdzie indziej. Mnożniki jednostek są również opcjonalne: ważne są zarówno 4d6 * 1, jak i 4d6.

Możesz napisać program lub funkcję, przyjmując dane wejściowe przez STDIN (lub najbliższą alternatywę), argument wiersza poleceń lub argument funkcji. Wyniki należy wydrukować do STDOUT (lub najbliższej alternatywy) lub zwrócić jako ciąg.

Przykłady

>> "10 6 10"
10d6
>> "10 6 4"
2d6*2+2d6+14
>> "10 6 3"
1d6*3+1d6+21
>> "10 6 2"
1d6*3+1d6+21
>> "10 6 1"
I AM A SEXY SHOELESS GOD OF WAR!

Punktacja

Najkrótszy kod wygrywa. Obowiązują standardowe zasady.

Premia

-33% (zaokrąglone w dół przed odejmowaniem), jeśli twój program zwraca również rozwiązania zawierające prawidłowe kości inne niż k (gdzie prawidłowe wartości, jak wspomniano powyżej, to 4, 6, 8, 10, 12 i 20). Jeśli zdecydujesz się to zrobić, powinieneś zawsze zwracać takie rozwiązania, gdy jest to właściwe, i obsługiwać rozwiązania wykorzystujące wiele rodzajów matryc. Przykład:

>> "7 4 3"
3d6+7

GolfScript ( 163 143 133 bajty)

~@:^\?,{^base 0-}%{0\{.*+}/^=},.{{,}$-1=..&{[[1$[1$]/,(3$@]'d*+'1/]zip}%^@{-}/@)*.2/\1&'.5'*}{];'I AM A SEXY SHOELESS GOD OF WAR!'}if

Demo online

Kiedy nie miesza się typów kości, problem sprowadza się do wyrażenia njako sumy nie większej niż rkwadraty i kjest nieistotny, z wyjątkiem obliczania stałej na końcu. Większość tej odpowiedzi jest księgowość obowiązek wyrazić wynik w wybranym formacie: faktyczne wyliczenie jest ^\?,{^base}%{0\{.*+}/^=},znaleźć mnożników a, bitp .; i ^@{-}/@)*.2/obliczyć stałą.

Sekcja

~                # Stack: n k r
@:^\?,{          # Store n in ^, and for 0 to n**r
  ^base 0-       #   convert to base n and remove 0s.
}%               # Stack: k [arrays of up to r values from 1 to n-1]
{0\{.*+}/^=},    # Filter them to arrays whose sum of squares is n,
                 #   i.e. to multipliers which have the right variance
.{               # If any multiplier array passes the filter...
  {,}$-1=        #   Pick one with the greater number of rolls
                 #   Stack: k [multipliers]
  ..&{           #   Map each distinct multiplier a...
    [[           #     Gather in nested array for later zip
      1$[1$]/,(  #       Split a copy of the multipliers around a to count the as
                 #       Let's denote that count as m
                 #       Stack: k [multipliers] a [ [ m
      3$@        #       Copy k and rotate the a inside the nested array
     ]           #       Stack: k [multipliers] [ [m k a]
      'd*+'1/    #       Push an array ['d' '*' '+'] and close nested array
    ]zip         #       Giving [[m 'd'] [k '*'] [a '+']]
                 #       which will be printed as mdk*a+
  }%             #   Stack: k [multipliers] [string representations of dice]
  ^@{-}/@)*      #   Compute (n - sum(multipliers)) * (k + 1)
                 #   That's twice the constant we need to add to fix the mean
  .2/\1&'.5'*    #   And convert it to a renderable form, including .5 if needed
}{               # Otherwise clear the stack and push the error message
  ];'I AM A SEXY SHOELESS GOD OF WAR!'
}if

Pyton, 487 461 452–33% = 303 bajtów

Ponieważ nikt inny tego nie zrobił, oto rozwiązanie, które obsługuje różne rodzaje kości. Podobnie jak inne rozwiązanie, generuje szereg możliwych rozwiązań i filtruje je. Wykorzystuje fakt, że (k + 1) (k-1) = k ^ 2-1 i dwie pół-luki w specyfikacji (ups!): Brak zakazu drukowania zbędnej formy 0d k * a (co oszczędza wszystkie 5 bajtów!) i brak ograniczenia czasu działania (działa dość wolno dość szybko, choć działają wszystkie podane przykłady).

from itertools import*
N,K,R=map(int,input().split())
S=lambda l:sum([x[0]for x in l])
s=[x for x in product(*[[(n,k,a)for n in range(N*(K**2-1)/((k**2-1)*a**2)+1)]for a in range(1,N+1)for k in[4,6,8,10,12,20]if a**2<=N])if sum([n*(k**2-1)*a**2 for n,k,a in x])==N*K**2-N and S(x)<=R]
if s:s=max(s,key=S);print"+".join(["%sd%s*%s"%x for x in s]+[str(int(N*(K+1)/2.-sum([n*a*(k+1)/2.for n,k,a in s])))])
else:print"I AM A SEXY SHOELESS GOD OF WAR!"

Dla ładniejszego wyjścia dodaj if x[0]po"%sd%s*%s"%x for x in s :

>> "7 4 3"
3d6+7
>> "10 6 3"
1d6*1+1d8*1+1d8*2+18
>> "10 6 2"
1d6*1+1d6*3+21
>> "10 6 1"
I AM A SEXY SHOELESS GOD OF WAR!