Sie werden an einer Gameshow teilnehmen. Eine der Herausforderungen sieht folgendermaßen aus:

• Der erste Raum enthält eine große Anzahl identischer Kugeln.
• Der zweite Raum enthält eine Reihe von Rutschen, von denen jede mit einem Sensor ausgestattet ist, der die Anzahl der darin platzierten Kugeln misst. Ein Ball, der in eine Rutsche gelegt wird, kann dann nicht geborgen werden.
• Jeder Schacht wird ausgelöst, nachdem eine bestimmte Anzahl von Bällen (seine Auslöseanzahl ) in ihn gelegt wurde. Wenn es ausgelöst wird, blinkt es, macht ein Geräusch und lässt Sie keinen Zweifel daran, dass es ausgelöst hat.
• Sie müssen NRutschen auslösen , um mit der nächsten Herausforderung fortzufahren.
• Sie kennen die Anzahl der Auslöser, aber nicht die Entsprechung zwischen Anzahl und Rutsche.
• Sie haben eine Möglichkeit, Bälle aus dem ersten Raum in den zweiten zu werfen. Sobald Sie einen Ball in eine Rutsche gelegt haben, können Sie nicht mehr Bälle einwerfen.
• Jeder Ball, den Sie nehmen, zieht Geld vom Jackpot ab.

Natürlich möchten Sie sicherstellen, dass Sie die Herausforderung bestehen, aber Sie möchten den Jackpot-Geldverlust minimieren. Schreiben Sie ein Programm, eine Funktion, ein Verb usw., um festzustellen, wie viele Bälle Sie benötigen.

Beispiel

Angenommen, die Anzahl der Auslöser ist 2, 4 und 10, und Sie müssen 2 Rutschen auslösen, um zu passen. Es gibt eine Strategie, mit 10 Bällen zu passen: Platzieren Sie bis zu 4 Bälle in der ersten Rutsche, bis zu 4 Bälle in der zweiten Rutsche und bis zu 4 Bälle in der dritten Rutsche. Da einer der drei Schächte nach nur 2 Bällen auslöst, verwenden Sie nur insgesamt 10. Es gibt keine Strategie, die garantiert mit weniger als 10 funktioniert, sodass die Ausgabe korrekt ist.

Eingang

Der Eingang besteht aus einem Array von ganzzahligen Triggerzählern und einer Ganzzahl, die die Anzahl der auszulösenden Rutschen angibt. Sie können die beiden Eingaben in beliebiger Reihenfolge vornehmen und bei Bedarf eine dritte Eingabe mit der Länge des Arrays vornehmen.

Sie können davon ausgehen, dass alle Eingänge größer als Null sind und die Anzahl der zu triggernden Rutschen die Anzahl der Rutschen nicht überschreitet.

Sie können auch davon ausgehen, dass die Zählungen sortiert sind (aufsteigend oder absteigend), solange Sie dies in Ihrer Antwort klar angeben.

Ausgabe

Die Ausgabe sollte eine einzelne Ganzzahl sein, die die Anzahl der Bälle angibt, die für die optimale Strategie erforderlich sind.

Testfälle

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

Verwendung ist S(2, (2, 4, 10)).

Um dieses Programm bei einer angemessenen Geschwindigkeit zu testen, fügen Sie Memoization hinzu, indem Sie dies nach der Funktionsdefinition einfügen:

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

Wir programmieren dynamisch auf einem Array T, das die Anzahl der Kugeln enthält, die wir in jede Rutsche geworfen haben, anfangs alle Nullen. Ohne einen strengen Beweis zu erbringen, behaupte ich, dass wir T jederzeit sortiert halten können, das heißt, wir werfen immer die meisten Bälle in die letzte Rutsche, von der wir wiederum annehmen, dass es die größte Rutsche war.

Wenn dann T, wenn Element für Element mit P (was unsere Problemeingabe ist) abgeglichen wird, mindestens G (was unser Ziel ist) Elemente größer hat, haben wir eine Lösung gefunden und wir geben 0 zurück, weil wir 0 werfen müssen mehr Bälle, um eine Lösung zu finden. Dies bedeutet, dass wenn G 1 ist, unser am wenigsten in den Schacht geworfener Ball mindestens die gleiche Anzahl an Kugeln enthalten muss wie der kleinste Schachtbedarf, und so weiter für größere G.

Andernfalls werfen wir für jede Position genügend Bälle ein, um auf die nächste Rutschenanforderung aufzurüsten (alles dazwischen wäre niemals beobachtbar) und fluchen erneut. Wir geben dann das Minimum dieser rekursiven Aufrufe zurück.

Haskell, 124 117 100 98 91 80 78 Bytes

11 Bytes dank @Peter Taylor eingespart

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

Probieren Sie es online!

(#) verwendet eine Ganzzahl und eine Liste von Ganzzahlen in absteigender Reihenfolge als Argumente

Verwendung ist 1#[10,4,2]

Erklärung:

Für jeden Wert x an Position i (1-idexed) in der Liste besteht die beste Taktik zum Entfernen dieses Elements (oder einer bestimmten Anzahl von Elementen, die kleiner oder gleich x sind) darin, x Kugeln in i Rutschen zu gießen.

Für jedes Element berechnet x an Position i in der Liste (n #) x * i + ((n-1) #) der Liste nach Position i (bis n 0 ist). Dann braucht es das Minimum aller überprüften Möglichkeiten.

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

Probieren Sie es online!

Nimmt die Liste in aufsteigender Reihenfolge.

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

Port von H.PWiz's Haskell Antwort. Erfordert, dass die Eingabe in absteigender Reihenfolge erfolgt.

CJam (35 Bytes)

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

Online-Demo

Übernimmt die Eingabe als N counts , dass diecounts in aufsteigender Reihenfolge sortiert ist.

Präparation

Bezeichnen Sie die Zählungen in absteigender Reihenfolge als ein 1-indiziertes Array C(das zweite Element von Cist also die zweitgrößte Zählung). Nehmen wir an, wir gewinnen, indem wir Rutschen auslösen C[a_0], C[a_1], ... C[a_{N-1}]. Dann im schlimmsten Fall, für jeden C[a_i]haben wir zumindest setzen C[a_i]Kugeln in jede von Rutschen 1zu a_i. Also legen wir C[a_{N-1}]Bälle in a_{N-1}Rutschen, zusätzliche C[a_{N-2}]Bälle hinein a_{N-2}, ...

Was Nergibt über jede Untergruppe von Zählungen die kleinste Summe? Dann sollten wir versuchen, mit dieser Untergruppe von Zählungen zu gewinnen.

NB Der Code verwendet die Zählungen tatsächlich in aufsteigender Reihenfolge, aber ich denke, absteigende Reihenfolge ist intuitiver.

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