Você participará de um show de jogos. Um dos desafios funciona da seguinte maneira:

• A primeira sala contém um grande número de bolas idênticas.
• A segunda sala contém uma série de rampas, cada uma com um sensor que conta quantas bolas foram colocadas nela. Uma bola que é colocada em uma rampa não pode ser recuperada.
• Cada chute será acionado após um certo número de bolas (sua contagem de gatilhos ) ter sido colocada nele. Quando acionado, pisca luzes, faz barulho e não deixa dúvidas de que foi acionado.
• Você deve acionar Nrampas para continuar no próximo desafio.
• Você sabe que o gatilho conta, mas não a correspondência entre contagem e rampa.
• Você tem uma oportunidade de levar bolas da primeira sala para a segunda. Depois de colocar uma bola em uma rampa, você não pode voltar para mais bolas.
• Cada bola que você pega deduz dinheiro do jackpot.

Obviamente, você deseja garantir que será aprovado no desafio, mas deseja minimizar a perda de dinheiro do jackpot. Escreva um programa, função, verbo, etc. para dizer quantas bolas você precisa.

Exemplo

Suponha que as contagens de gatilho sejam 2, 4 e 10 e você precise acionar 2 chutes para passar. Existe uma estratégia para passar com 10 bolas: coloque até 4 bolas no primeiro chute, até 4 bolas no segundo chute e até 4 bolas no terceiro chute. Como um dos três chutes será acionado após apenas 2 bolas, você usará apenas um total de 10. Não há estratégia garantida para trabalhar com menos de 10, portanto essa é a saída correta.

Entrada

A entrada consiste em uma matriz de contagens de disparos inteiros e um inteiro que fornece o número de chutes a serem disparados. Você pode pegar as duas entradas em qualquer ordem e, se necessário, pode pegar uma terceira entrada com o comprimento da matriz.

Você pode supor que todas as entradas são maiores que zero e que o número de chutes que devem ser acionados não excede o número de chutes.

Você também pode assumir que as contagens são classificadas (ascendente ou descendente), desde que você indique isso claramente em sua resposta.

Saída

A saída deve ser um número inteiro único, fornecendo o número de bolas requeridas pela estratégia ideal.

Casos de teste

Formato: 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 bytes

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)

O uso é S(2, (2, 4, 10)).

Para testar este programa a qualquer velocidade decente, adicione memorização colocando-o após a definição da função:

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

Fazemos programação dinâmica em uma matriz T que contém o número de bolas que jogamos em cada rampa, inicialmente todos os zeros. Sem fornecer uma prova rigorosa, afirmo que podemos manter T ordenado o tempo todo, ou seja, suponha que sempre jogamos o máximo de bolas na última calha, o que, por sua vez, assumiremos que foi a maior calha.

Se então T, quando elemento correspondente para elemento com P (que é a entrada do nosso problema), tiver pelo menos G (que é o nosso objetivo) elementos maiores, encontramos uma solução e retornamos 0, porque precisamos lançar 0 mais bolas para encontrar uma solução. Isso significa que, se G é 1, o menos jogado no chute deve conter uma quantidade igual ou maior de bolas do que o menor requisito do chute, e assim por diante para o G. maior.

Caso contrário, para cada posição, lançaremos bolas suficientes para atualizar para o próximo requisito de rampa (qualquer coisa entre elas nunca seria observável) e recuaremos. Em seguida, retornamos o mínimo dessas chamadas recursivas.

Haskell, 124 117 100 98 91 80 78 bytes

Guardado 11 bytes graças a @Peter Taylor

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

Experimente online!

(#) recebe um número inteiro e uma lista de números inteiros em ordem decrescente como argumentos

O uso é 1#[10,4,2]

Explicação:

Para cada valor, x, na posição i (1-idexed) na lista, a melhor tática para remover esse elemento (ou alguma quantidade de elementos menor ou igual a x) é derramar x bolas nas rampas i.

Para cada elemento, x, na posição i na lista, (n #) calcula x * i + ((n-1) #) da lista além da posição i (até que n seja 0). Então é preciso o mínimo de todas as possibilidades verificadas.

Haskell , 54 bytes

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

Experimente online!

Leva a lista em ordem crescente.

Python, 73 bytes

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

Resposta do porto de H.PWiz Haskell. Requer que a entrada esteja em ordem decrescente.

CJam (35 bytes)

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

Demonstração online

Considera a entrada N countsassumindo que countsestá classificada em ordem crescente.

Dissecação

Indique as contagens em ordem decrescente como uma matriz indexada em 1 C(portanto, o segundo elemento de Cé a segunda maior contagem). Suponha que acabemos vencendo acionando rampas C[a_0], C[a_1], ... C[a_{N-1}]. Em seguida, no pior caso, para cada C[a_i]pusemos pelo menos C[a_i]bolas em cada um dos chutes 1a a_i. Então colocamos C[a_{N-1}]bolas em a_{N-1}rampas, outras C[a_{N-2}]bolas a_{N-2}nelas, ...

Sobre cada subconjunto de Ncontagens, o que nos dá a menor soma? Então devemos tentar vencer com esse subconjunto de contagens.

NB O código realmente usa as contagens em ordem crescente, mas acho que a ordem decrescente é mais intuitiva.

{         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
}