Vas a participar en un concurso de juegos. Uno de los desafíos funciona de la siguiente manera:

• La primera sala contiene una gran cantidad de bolas idénticas.
• La segunda sala contiene una serie de rampas, cada una de las cuales tiene un sensor que cuenta cuántas bolas se han colocado en ella. Una bola que se coloca en una rampa no puede recuperarse.
• Cada rampa se disparará después de que se haya colocado un cierto número de bolas (su conteo de disparadores ). Cuando se dispara, enciende luces, hace un ruido y no le deja ninguna duda de que se ha disparado.
• Debes disparar Nrampas para continuar con el próximo desafío.
• Usted sabe que el gatillo cuenta, pero no la correspondencia entre el conteo y la tolva.
• Tienes una oportunidad para llevar pelotas de la primera habitación a la segunda. Una vez que pones una pelota en una rampa, no puedes volver por más bolas.
• Cada bola que tomas deduce dinero del premio gordo.

Obviamente, desea asegurarse de que superará el desafío, pero desea minimizar la pérdida de dinero del premio gordo. Escribe un programa, función, verbo, etc. para decirte cuántas bolas necesitas.

Ejemplo

Suponga que los recuentos de gatillo son 2, 4 y 10, y necesita activar 2 chutes para pasar. Hay una estrategia para pasar con 10 bolas: coloque hasta 4 bolas en la primera rampa, hasta 4 bolas en la segunda rampa y hasta 4 bolas en la tercera rampa. Como una de las tres rampas se disparará después de solo 2 bolas, solo usará un total de 10. No existe una estrategia que garantice que funcione con menos de 10, por lo que esa es la salida correcta.

Entrada

La entrada consiste en una matriz de recuentos de disparos de enteros y un entero que da el número de chutes para disparar. Puede tomar las dos entradas en cualquier orden, y si es necesario, puede tomar una tercera entrada con la longitud de la matriz.

Puede suponer que todas las entradas son mayores que cero y que el número de canales que deben activarse no excede el número de canales.

También puede suponer que los recuentos están ordenados (ascendentes o descendentes), siempre que lo indique claramente en su respuesta.

Salida

La salida debe ser un número entero único, dando el número de bolas requerido por la estrategia óptima.

Casos de prueba

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)

El uso es S(2, (2, 4, 10)).

Para probar este programa a cualquier velocidad decente, agregue una memoria colocando esto después de la definición de la función:

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

Hacemos programación dinámica en una matriz T que contiene el número de bolas que hemos lanzado en cada rampa, inicialmente todos ceros. Sin proporcionar una prueba rigurosa, afirmo que podemos mantener T ordenada en todo momento, es decir, supongamos que siempre tiramos la mayoría de las bolas en el último conducto, que a su vez asumiremos que fue el conducto más grande.

Si entonces T, cuando coincide elemento por elemento con P (que es nuestro problema de entrada), tiene al menos G (que es nuestro objetivo) elementos más grandes, hemos encontrado una solución y devolvemos 0, porque necesitamos lanzar 0 Más bolas para encontrar una solución. Esto significa que si G es 1, nuestro tiro menos inclinado debe contener una cantidad igual o mayor de bolas que el requerimiento de tolva más pequeño, y así sucesivamente para una G. más grande

De lo contrario, para cada posición arrojamos suficientes bolas para actualizar al siguiente requisito de rampa (cualquier cosa en el medio nunca sería observable) y recurrimos. Luego devolvemos el mínimo de estas llamadas recursivas.

Haskell, 124 117 100 98 91 80 78 bytes

Guardado 11 bytes gracias 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]

Pruébalo en línea!

(#) toma un entero y una lista de enteros en orden descendente como argumentos

El uso es 1#[10,4,2]

Explicación:

Para cada valor, x, en la posición i (1-idexed) en la lista, la mejor táctica para eliminar ese elemento (o una cierta cantidad de elementos menor o igual a x) es verter x bolas en i canales.

Para cada elemento, x, en la posición i en la lista, (n #) calcula x * i + ((n-1) #) de la lista más allá de la posición i (hasta que n sea 0). Luego toma el mínimo de todas las posibilidades marcadas.

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

Pruébalo en línea!

Toma la lista en orden ascendente.

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))

La respuesta de Haskell del puerto de H.PWiz. Requiere que la entrada esté en orden descendente.

CJam (35 bytes)

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

Demostración en línea

Toma información como N countsasumiendo que countsestá ordenada en orden ascendente.

Disección

Denote los recuentos en orden descendente como una matriz indexada 1 C(por lo que el segundo elemento de Ces el segundo recuento más grande). Supongamos que terminamos ganando activando rampas C[a_0], C[a_1], ... C[a_{N-1}]. Luego, en el peor de los casos, para cada uno C[a_i]hemos puesto al menos C[a_i]bolas en cada una de las tolvas 1a a_i. Así que colocamos C[a_{N-1}]bolas en a_{N-1}toboganes, C[a_{N-2}]bolas adicionales en a_{N-2}ellas, ...

Sobre cada subconjunto de Ncuentas, ¿cuál nos da la suma más pequeña? Entonces deberíamos apuntar a ganar con ese subconjunto de conteos.

Nota: el código en realidad usa los recuentos en orden ascendente, pero creo que el orden descendente es más intuitivo.

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