Приготовься умереть?

Задний план

Один из источников тоски в настольных ролевых играх связан с бросками, включающими много кубиков. Разыгрывание заклинания «Распад» может быть мгновенным, но бросать и складывать вместе 40 кубиков, конечно же, нельзя!

Ряд предложений для решения этой проблемы обсуждаются на rpg.stackexchange.com . Однако некоторые из них, такие как использование роликовых программ или усреднение кубиков, лишают игроков удовольствия и чувства контроля. Другие, такие как бросание 4 кубиков и умножение общей суммы на 10, делают результаты намного более плавными (в то время как усреднение кубиков действует в противоположном направлении).

Этот вопрос касается метода уменьшения количества бросков костей без изменения среднего результата (среднее значение) или его изменчивости (дисперсия).

Обозначения и математика

В этом вопросе мы будем использовать следующие обозначения для представления бросков костей:

• n d k (например, 40d6) относится к сумме n бросков кубика с k-гранью.
• n d k * c (например, 4d6 * 10) описывает умножение результата на константу c.
• Мы также можем добавить броски (например, 4d6 * 10 + 40d6) и константы (например, 4d6 + 10).

Для одного броска кубика мы можем показать, что:

• Среднее значение : E [1d k ] = (k + 1) / 2
• Дисперсия : Var (1d k ) = (k-1) (k + 1) / 12

Используя основные свойства среднего и дисперсии, мы можем сделать вывод, что:

• Среднее значение : E [ m d k * a + n d l * b + c ] = am .E [1d k ] + bn . [1d l ] + c
• Разница : вар ( м д к * + п д л * Ь + с ] = . ² м .var (1d к ) + б ². П .var (1d л )

задача

Учитывая три целых числа n , k и r , ваша программа должна вывести способ аппроксимации n d k не более чем за r бросков со следующими ограничениями:

• Решение должно иметь то же среднее значение и дисперсию, что и n d k .
• Решение должно содержать максимально возможное количество рулонов, меньшее или равное r , поскольку большее количество рулонов обеспечивает более плавное распределение.
• Вы должны ограничить свои решения только использованием k- сторонней игры в кости, если вы не стремитесь к Бонусу (см. Ниже).
• Если решения не существует (так как r слишком мало), программа должна вывести строку «Я - сексуальный безжалостный бог войны!».
• Параметры передаются в виде одной строки через пробел.
• Вы можете предположить, что 1 ≤ n ≤ 100, 1 ≤ r ≤ n и что k является одним из 4, 6, 8, 10, 12 и 20 (стандартные кости, используемые в столешницах).
• Вывод должен быть в формате, описанном в нотации (например, 4d6 * 10 + 5), с дополнительными пробелами вокруг + s, но нигде больше. Множители единиц также необязательны: действительны как 4d6 * 1, так и 4d6.

Вы можете написать программу или функцию, используя ввод через STDIN (или ближайшую альтернативу), аргумент командной строки или аргумент функции. Результаты должны быть напечатаны в STDOUT (или ближайшую альтернативу) или возвращены в виде строки.

Примеры

>> "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!

счет

Самый короткий код выигрывает. Стандартные правила применяются.

бонус

-33% (округляется до вычитания), если ваша программа также возвращает решения, которые содержат действительные кости, отличные от k (где действительные значения, как упомянуто выше, составляют 4, 6, 8, 10, 12 и 20). Если вы решите сделать это, то вы всегда должны возвращать такие решения, когда это уместно, и обрабатывать решения, которые используют несколько типов штампов. Пример:

>> "7 4 3"
3d6+7

GolfScript ( 163 143 133 байта)

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

Онлайн демо

Если не смешивать типы кубиков, проблема сводится к выражению nв виде суммы не более rквадратов и не kимеет значения, за исключением вычисления константы в конце. Основная часть этого ответа является бухучет требуется , чтобы выразить результат в желаемом формате: фактический расчет , ^\?,{^base}%{0\{.*+}/^=},чтобы найти факторы умножения a, bи т.д .; и ^@{-}/@)*.2/рассчитать постоянную.

рассечение

~                # 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

Python, 487 461 452 - 33% = 303 байта

Так как никто другой не сделал этого, вот решение, которое обрабатывает различные виды костей. Как и другое решение, оно генерирует ряд возможных решений и фильтрует их. Он использует тот факт, что (k + 1) (k-1) = k ^ 2-1 и две полузащиты в спецификации (упс!): Отсутствие запрета на печать избыточной формы 0d k * a (что экономит все 5 байтов!), и отсутствие ограничения времени выполнения (оно замедляется довольно быстро, хотя и запускает все приведенные примеры).

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!"

Для более приятного вывода добавить if x[0]после "%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!