Вы собираетесь участвовать в игровом шоу. Одна из задач работает следующим образом:

• Первая комната содержит большое количество одинаковых шаров.
• Вторая комната содержит серию желобов, каждый из которых имеет датчик, который подсчитывает, сколько шариков было помещено в него. Мяч, помещенный в желоб, не может быть восстановлен.
• Каждый желоб будет срабатывать после того, как в него будет помещено определенное количество шариков ( количество срабатываний ). Когда он срабатывает, он мигает светом, издает шум и не оставляет никаких сомнений в том, что он сработал.
• Вы должны активировать Nжелоба, чтобы перейти к следующему вызову.
• Вы знаете количество триггеров, но не соответствие между количеством и желобом.
• У вас есть одна возможность забрать шары из первой комнаты во вторую. После того, как вы положили мяч в желоб, вы не сможете вернуться за другими шарами.
• Каждый мяч, который вы берете, вычитает деньги из джекпота.

Очевидно, вы хотите убедиться, что вы пройдете испытание, но вы хотите минимизировать потерю джекпота. Напишите программу, функцию, глагол и т. Д., Чтобы сказать, сколько шариков вам нужно.

пример

Предположим, что количество триггеров равно 2, 4 и 10, и вам нужно запустить 2 парашюта для прохождения. Существует стратегия прохождения с 10 шарами: поместите до 4 шаров в первый желоб, до 4 шаров во второй желоб и до 4 шаров в третий желоб. Поскольку один из трех желобов сработает только после 2 шаров, вы используете всего 10 баллов. Не существует стратегии, которая гарантированно работала бы с менее чем 10, так что это правильный выход.

вход

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

Вы можете предположить, что все входы больше нуля, и что количество лотков, которые должны быть запущены, не превышает количество лотков.

Вы также можете предположить, что счетчик отсортирован (по возрастанию или по убыванию), если вы четко указали это в своем ответе.

Выход

Вывод должен быть одним целым числом, дающим количество шаров, необходимое для оптимальной стратегии.

Контрольные примеры

Формат: N counts solution

1 [2 4 10] 6
2 [2 4 10] 10
3 [2 4 10] 16
1 [3 5 5 5 5 5 5 5 5 5] 5
2 [1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 8 11] 8
2 [1 2 6 6 6 6 6 6 6 10] 16
2 [1 2 3 3 4 4 6 6 6 11] 17
3 [1 2 3 4 5 5 6] 16
3 [2 4 7 7 7 7 7 7 7] 21
5 [1 2 2 3 3 3 3 3 5 9 9 11] 27
2 [5 15 15] 25
1 [4 5 15] 10
3 [1 4 4 4] 10
2 [1 3 4] 6
2 [1 3 3 8] 8

Python, 222 198 байт

def S(G,P,T=0):
 T=T or[0]*len(P);r=[0]*(sum(t>=p for t,p in zip(T,P))>=G)
 for i,t in enumerate(T):
    if t<max(P):a=next(p for p in P if p>t)-t;T[i]+=a;r+=[a+S(G,P,sorted(T))];T[i]-=a
 return min(r)

Использование есть S(2, (2, 4, 10)).

Чтобы протестировать эту программу на любой приличной скорости, добавьте памятку, поставив ее после определения функции:

old_s = S
mem = {}
def S(G, P, T=0):
    k = (G, tuple(P), T and tuple(T) or 0)
    if k in mem: return mem[k]
    r = old_s(G, P, T)
    mem[k] = r
    return r

Мы выполняем динамическое программирование для массива T, который содержит количество шариков, которые мы бросили в каждый желоб, изначально все нули. Не предоставляя строгих доказательств, я утверждаю, что мы можем постоянно сортировать T, то есть предположим, что мы всегда бросаем наибольшее количество шаров в последний желоб, который, в свою очередь, мы предположим, был самым большим желобом.

Если тогда T, когда соответствует элемент для элемента с P (который является нашей входной задачей), имеет по крайней мере G (что является нашей целью) элементов больше, мы нашли решение, и мы возвращаем 0, потому что нам нужно выбросить 0 больше шаров, чтобы найти решение. Это означает, что если G равно 1, то наш наименьший брошенный в желоб лоток должен содержать такое же или большее количество шаров, чем минимальное требование к желобу, и так далее для большего G.

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

Haskell, 124 117 100 98 91 80 78 байт

Сохранено 11 байтов благодаря @Peter Taylor

0#_=0
n#a=minimum$zipWith(\x y->x*y+(n-1)#(snd.splitAt y$a))a[1..length a-n+1]

Попробуйте онлайн!

(#) принимает в качестве аргументов целое число и список целых чисел в порядке убывания

Использование 1#[10,4,2]

Explaination:

Для каждого значения x в позиции i (1-idexed) в списке, лучшая тактика удаления этого элемента (или некоторого количества элементов, меньших или равных x), состоит в том, чтобы вылить x шариков в i желоба.

Для каждого элемента x в позиции i в списке (n #) вычисляется x * i + ((n-1) #) списка за пределами позиции i (до тех пор, пока n не станет 0). Тогда требуется минимум всех проверенных возможностей.

Haskell , 54 байта

(%)0
(p%l)n|h:t<-l=p+min(p%t$n)(h%t$n-1)|n<1=p|1>0=1/0

Попробуйте онлайн!

Принимает список в порядке возрастания.

Python, 73 байта

f=lambda n,c:n and min(c[i]*-~i+f(n-1,c[-~i:])for i in range(len(c)-n+1))

Порт H.PWiz's Haskell ответ. Требуется, чтобы вход был в порядке убывания.

CJam (35 байт)

{:A,,e!f<{$__(;A,+.-\Af=.*1bz}%:e<}

Онлайн демо

Принимает ввод как N countsпредполагающий, что countsон отсортирован в порядке возрастания.

рассечение

Обозначим счетчики в порядке убывания как массив с 1 индексом C(так что второй элемент Cявляется вторым по величине счетчиком). Предположим, что мы в конечном итоге выиграли, запуская парашюты C[a_0], C[a_1], ... C[a_{N-1}]. Тогда в худшем случае для каждогоC[a_i] мы поставили по крайней мере C[a_i]шаров в каждый из желобов 1в a_i. Таким образом, мы помещаем C[a_{N-1}]шары в a_{N-1}желоба, дополнительные C[a_{N-2}]шары в a_{N-2}них, ...

По каждому подмножеству Nотсчетов, что дает нам наименьшую сумму? Тогда мы должны стремиться к победе с этим набором очков.

NB Код фактически использует счет в порядке возрастания, но я думаю, что порядок убывания более интуитивно понятен.

{         e# Define a block
  :A      e#   Store the sorted counts as A
  ,,e!f<  e#   Get all N-element subsets of A's indices
  {       e#   Map over these subsets S:
    $__   e#     Sort the subset and get a couple of copies
    (;A,+ e#     Remove the first element from one copy and append len(A)
    .-    e#     Pointwise subtraction, giving [S[0]-S[1] S[1]-S[2] ...]
    \Af=  e#     Get the counts [A[S[0]] A[S[1]] ...]
    .*    e#     Pointwise multiplication
    1bz   e#     Sum and take absolute value, giving the worst case score
  }%
  :e<     e#   Select the minimum worst case score
}