Vous allez participer à un gameshow. L'un des défis fonctionne comme suit:

• La première salle contient un grand nombre de balles identiques.
• La deuxième salle contient une série de chutes, chacune dotée d'un capteur qui compte le nombre de balles qui y ont été placées. Une balle placée dans un parachute ne peut alors pas être récupérée.
• Chaque chute se déclenchera après qu'un certain nombre de balles (son nombre de déclencheurs ) y auront été placées. Quand il se déclenche, il fait clignoter des lumières, fait du bruit et ne laisse aucun doute qu'il s'est déclenché.
• Vous devez déclencher des Nchutes pour continuer vers le prochain défi.
• Vous connaissez le nombre de déclencheurs, mais pas la correspondance entre le nombre et la goulotte.
• Vous avez une occasion de prendre des balles de la première salle dans la seconde. Une fois que vous avez mis une balle dans une goulotte, vous ne pouvez plus y retourner pour plus de balles.
• Chaque balle que vous prenez déduit de l'argent du jackpot.

Évidemment, vous voulez vous assurer de réussir le défi, mais vous voulez minimiser la perte d'argent du jackpot. Écrivez un programme, une fonction, un verbe, etc. pour vous dire combien de balles vous avez besoin.

Exemple

Supposons que le nombre de déclencheurs soit 2, 4 et 10 et que vous devez déclencher 2 goulottes pour passer. Il y a une stratégie pour passer avec 10 balles: placez jusqu'à 4 balles dans la première chute, jusqu'à 4 balles dans la deuxième chute, et jusqu'à 4 balles dans la troisième chute. Étant donné que l'un des trois chutes se déclenchera après seulement 2 balles, vous n'utilisez qu'un total de 10. Il n'y a pas de stratégie qui est garantie de fonctionner avec moins de 10, donc c'est la sortie correcte.

Contribution

L'entrée se compose d'un tableau de nombres de déclencheurs entiers et d'un entier donnant le nombre de goulottes à déclencher. Vous pouvez prendre les deux entrées dans l'un ou l'autre ordre et, si nécessaire, vous pouvez prendre une troisième entrée avec la longueur du tableau.

Vous pouvez supposer que toutes les entrées sont supérieures à zéro et que le nombre de chutes à déclencher ne dépasse pas le nombre de chutes.

Vous pouvez également supposer que les décomptes sont triés (croissant ou décroissant), tant que vous le dites clairement dans votre réponse.

Sortie

La sortie doit être un seul entier, donnant le nombre de billes requis par la stratégie optimale.

Cas de test

Format: 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 octets

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)

L'utilisation est S(2, (2, 4, 10)).

Afin de tester ce programme à n'importe quelle vitesse décente, ajoutez la mémorisation en plaçant ceci après la définition de la fonction:

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

Nous faisons une programmation dynamique sur un tableau T qui contient le nombre de billes que nous avons lancées dans chaque chute, initialement tous des zéros. Sans fournir une preuve rigoureuse, je prétends que nous pouvons garder T tri en tout temps, c'est-à-dire, supposons que nous jetons toujours le plus de balles dans la dernière goulotte, qui à notre tour supposera que c'était la plus grande goulotte.

Si alors T, lorsque l'élément correspond à l'élément avec P (qui est notre entrée de problème), a au moins G (ce qui est notre objectif), les éléments sont plus grands, nous avons trouvé une solution et nous retournons 0, car nous devons lancer 0 plus de balles pour trouver une solution. Cela signifie que si G est 1, notre moins lancé dans la chute doit contenir une quantité égale ou supérieure de billes que la plus petite exigence de chute, et ainsi de suite pour un plus grand G.

Sinon, pour chaque position, nous lançons suffisamment de balles pour passer à la prochaine exigence de chute (tout ce qui se trouve entre les deux ne sera jamais observable) et recurse. Nous retournons ensuite le minimum de ces appels récursifs.

Haskell, 124 117 100 98 91 80 78 octets

Sauvegardé 11 octets grâce à @Peter Taylor

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

Essayez-le en ligne!

(#) prend un entier et une liste d'entiers dans l'ordre décroissant comme arguments

L'utilisation est 1#[10,4,2]

Explication:

Pour chaque valeur, x, en position i (1-idexed) dans la liste, la meilleure tactique pour supprimer cet élément (ou une certaine quantité d'éléments inférieurs ou égaux à x) est de verser x boules dans i chutes.

Pour chaque élément, x, en position i dans la liste, (n #) calcule x * i + ((n-1) #) de la liste au-delà de la position i (jusqu'à ce que n soit 0). Il faut alors le minimum de toutes les possibilités vérifiées.

Haskell , 54 octets

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

Essayez-le en ligne!

Prend la liste en ordre croissant.

Python, 73 octets

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

Réponse de Haskell de H.PWiz. Nécessite que l'entrée soit dans l'ordre décroissant.

CJam (35 octets)

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

Démo en ligne

Prend l'entrée comme N countssupposant qu'elle countsest triée par ordre croissant.

Dissection

Désigner les décomptes dans l'ordre décroissant comme un tableau indexé sur 1 C(donc le deuxième élément de Cest le deuxième décompte le plus grand). Supposons que nous finissions par gagner en déclenchant des chutes C[a_0], C[a_1], ... C[a_{N-1}]. Puis , dans le pire des cas, pour chaque , C[a_i]nous avons mis au moins des C[a_i]balles dans chacune des goulottes 1à a_i. Nous avons donc mis des C[a_{N-1}]balles dans des a_{N-1}goulottes, des C[a_{N-2}]balles supplémentaires dans a_{N-2}celles-ci, ...

Sur chaque sous-ensemble de Ncomptes, qui nous donne la plus petite somme? Ensuite, nous devrions viser à gagner avec ce sous-ensemble de comptes.

NB Le code utilise en fait les décomptes dans l'ordre croissant, mais je pense que l'ordre décroissant est plus intuitif.

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