Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

PIEC - Piec

Restauracja Calabria, która częstowała pizzą uczestników III Warmińsko-Mazurskich zawodów
w programowaniu, jest wyposażona w automatyczny piec do wypiekania ciast. Piec ma na wejściu
taśmę z ułożonymi ciastami (każde ciasto ma swój czas wypiekania). Piec mieści naraz M sztuk ciast.
Twoim zadaniem jest tak podzielić ciasta na kolejne wkłady do pieca aby zminimalizować czas
wypiekania. Kolejny wkład można umieścić w piecu tylko jak skończą się wypiekać wszystkie ciasta
z poprzedniego. Nie możemy zmieniać kolejności ciast na taśmie, możemy za to dowolnie dzielić
ciasta na kolejne wkłady (maksymalnie M kolejnych ciast). Trzeba obliczyć i wyświetlić najkrótszy
możliwy czas wypiekania.

Przykładowo, piec mieści dwa ciasta (M=2). Na taśmie mamy kolejne czasy wypiekania:
2 10 10. Najkrótszy całkowity czas będzie wynosił 12. Pierwszy wkład ─ pierwsze ciasto, drugi wkład ─
równocześnie ciasto drugie i trzecie. Gdybyśmy podzielili ciasta inaczej, to czas wypiekania byłby 20.

Wejście

Wejście zaczyna się od liczby całkowitej N (N<23) określającej liczbę przypadków. Każdy
przypadek składa się z dwóch linii. W pierwszej linii znajduje się liczba M (liczba ciast mieszczących się
w piecu) oraz liczba K, długość taśmy (K<1001). W drugiej linii jest M liczb naturalnych, oznaczających
czasy wypiekania poszczególnych ciast na taśmie. Każdy czas wypiekania nie przekracza 100.

Wyjście

Dla każdego przypadku należy obliczyć i wyświetlić w jednej linii liczbę całkowitą, najkrótszy
możliwy czas wypiekania podanej kolejki.

Przykładowe dane

Weiście:
2
2 3
2 10 10
2 3
7 5 2 Wyjście: 12
9
 

Dodane przez:Aleksander Denisiuk
Data dodania:2013-02-05
Limit czasu wykonania programu:0.100s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM32-GCC ASM64 MAWK BC C-CLANG NCSHARP CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JS-MONKEY JULIA KTLN NIM OBJC OBJC-CLANG OCT PICO PROLOG PYPY3 R RACKET RUST SCM qobi CHICKEN SQLITE SWIFT UNLAMBDA VB.NET

ukryj komentarze
2023-04-20 17:55:56 Julia Ostrowska
w drugiej linii jest M liczb czy K ? " W drugiej linii jest M liczb naturalnych, oznaczających
czasy wypiekania poszczególnych ciast na taśmie"
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.