Zamierzasz wziąć udział w teleturnieju. Jedno z wyzwań działa w następujący sposób:

• Pierwszy pokój zawiera dużą liczbę identycznych piłek.
• Drugi pokój zawiera szereg zsypów, z których każdy ma czujnik, który zlicza ile piłek zostało w nim umieszczonych. Piłki umieszczonej w rynnie nie można odzyskać.
• Każda rynna uruchomi się po umieszczeniu w niej określonej liczby piłek (jej liczba aktywacji ). Po uruchomieniu miga światłem, wydaje dźwięk i nie pozostawia wątpliwości, że się uruchomił.
• Musisz uruchomić Nrynny, aby przejść do następnego wyzwania.
• Wiesz, że wyzwalacz się liczy, ale nie zgodność między zliczaniem a rynną.
• Masz jedną okazję, aby wziąć piłki z pierwszego pokoju do drugiego. Po włożeniu piłki do rynny nie można wrócić po więcej piłek.
• Każda zabrana piłka odejmuje pieniądze od jackpota.

Oczywiście chcesz mieć pewność, że przejdziesz wyzwanie, ale chcesz zminimalizować stratę pieniędzy z jackpota. Napisz program, funkcję, czasownik itp., Aby powiedzieć, ile piłek potrzebujesz.

Przykład

Załóżmy, że liczba wyzwalaczy wynosi 2, 4 i 10, a aby przejść, musisz uruchomić 2 rynny. Istnieje strategia podania z 10 piłkami: umieść do 4 piłek w pierwszym rynnie, do 4 piłek w drugim rynnie i do 4 piłek w trzeciej rynnie. Ponieważ jeden z trzech zsypów uruchomi się po zaledwie 2 piłkach, używasz tylko w sumie 10. Nie ma strategii, która gwarantowałaby pracę z mniejszą niż 10, więc jest to prawidłowy wynik.

Wkład

Dane wejściowe składają się z tablicy liczb całkowitych wyzwalacza i liczby całkowitej określającej liczbę zsypów do wyzwolenia. Możesz wziąć dwa wejścia w dowolnej kolejności, a jeśli to konieczne, możesz wziąć trzecie wejście o długości tablicy.

Możesz założyć, że wszystkie wejścia są większe od zera i że liczba rynien, które należy uruchomić, nie przekracza liczby rynien.

Możesz również założyć, że liczby są posortowane (rosnąco lub malejąco), o ile wyraźnie zaznaczasz to w swojej odpowiedzi.

Wydajność

Wyjście powinno być jedną liczbą całkowitą, podając liczbę piłek wymaganych przez optymalną strategię.

Przypadki testowe

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 bajtów

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)

Wykorzystanie jest S(2, (2, 4, 10)).

Aby przetestować ten program przy dowolnej przyzwoitej prędkości, dodaj notatkę, umieszczając ją po definicji funkcji:

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

Programujemy dynamicznie na tablicy T, która zawiera liczbę piłek, które wrzuciliśmy do każdej rynny, początkowo wszystkie zera. Nie dostarczając dokładnego dowodu, twierdzę, że przez cały czas możemy utrzymywać sortowanie w T, to znaczy zakładamy, że zawsze wrzucamy najwięcej piłek do ostatniej rynny, co z kolei zakładamy, że była największą rynną.

Jeśli więc T, gdy element dopasowany do elementu z P (który jest naszym problemem wejściowym), ma przynajmniej G (co jest naszym celem) elementy większe, znaleźliśmy rozwiązanie i zwracamy 0, ponieważ musimy wyrzucić 0 więcej piłek, aby znaleźć rozwiązanie. Oznacza to, że jeśli G wynosi 1, nasz najmniejszy wrzucony do rynny musi zawierać taką samą lub większą liczbę piłek, jak najmniejszy wymóg rynny, i tak dalej dla większych G.

W przeciwnym razie dla każdej pozycji wrzucamy wystarczającą liczbę piłek, aby przejść do następnego wymogu spadochronu (nic pośredniego nigdy nie będzie możliwe do zaobserwowania) i powrócić. Następnie zwracamy minimum tych rekurencyjnych połączeń.

Haskell, 124 117 100 98 91 80 78 bajtów

Zaoszczędź 11 bajtów dzięki @Peter Taylor

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

Wypróbuj online!

(#) przyjmuje jako argumenty liczbę całkowitą i listę liczb całkowitych w porządku malejącym

Zastosowanie jest 1#[10,4,2]

Wyjaśnienie:

Dla każdej wartości x w pozycji i (1-idexed) na liście najlepszą taktyką do usunięcia tego elementu (lub pewnej liczby elementów mniejszej lub równej x) jest wlanie x piłek do i-zsypów.

Dla każdego elementu x w pozycji i na liście (n #) oblicza x * i + ((n-1) #) listy poza pozycją i (aż n wynosi 0). Następnie bierze minimum wszystkich sprawdzonych możliwości.

Haskell , 54 bajty

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

Wypróbuj online!

Ustawia listę w kolejności rosnącej.

Python, 73 bajty

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

Port odpowiedzi Haskella H.PWiza. Wymaga wprowadzania danych w kolejności malejącej.

CJam (35 bajtów)

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

Demo online

Pobiera dane wejściowe jako N countsPrzyjmuje założone, że countssą sortowane w porządku rosnącym.

Sekcja

Oznacz liczby w kolejności malejącej jako tablicę z 1 indeksem C(więc drugi element Cto druga największa liczba). Załóżmy, że ostatecznie wygramy, uruchamiając rynny C[a_0], C[a_1], ... C[a_{N-1}]. Następnie, w najgorszym przypadku, dla każdego C[a_i]umieściliśmy co najmniej C[a_i]piłki w każdym zsypu 1do a_i. Więc wkładamy C[a_{N-1}]piłki do a_{N-1}zsypów, dodatkoweC[a_{N-2}] piłki doa_{N-2} nich ...

Nad każdym podzbiorem NKtóry daje nam najmniejszą sumę w liczb? Następnie powinniśmy dążyć do wygrania z tym podzbiorem liczb.

Uwaga: Kod faktycznie używa liczb w kolejności rosnącej, ale myślę, że kolejność malejąca jest bardziej intuicyjna.

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