| Zgłaszanie | Wszystkie zgłoszenia | Najlepsze | Lista |
DDZ2025_2 - Balony |
Zadanie 2: Balonowy Podział
W mieście Balonowo dorocznie organizowana jest wielka parada balonów. Organizatorzy chcą podzielić wszystkie balony na dokładnie 2 grupy, które będą unoszone osobno – tak, aby w każdej grupie łączna liczba kolorowych wstążek była jak najbardziej zrównoważona. Każdy balon ma pewną liczbę wstążek przymocowanych do siebie (reprezentowaną jako dodatnia liczba całkowita). Twoim zadaniem jest rozdzielić n balonów na 2 grupy tak, aby różnica sum wstążek między grupami była minimalna.
Innymi słowy, mając ciąg dodatnich liczb a₁, a₂, …, aₙ (liczba wstążek przy
kolejnych balonach), znajdź minimalny możliwy abs(S₁ – S₂), gdzie
S₁ to suma wstążek balonów w pierwszej grupie, a S₂ to suma
wstążek balonów w drugiej grupie.
Wejście
Pierwsza linia zawiera jedną liczbę całkowitą n (1 ≤ n ≤ 20 000) – liczbę
balonów. W drugiej linii znajduje się n dodatnich liczb całkowitych
ai (1 ≤ ai ≤ 10 000) – liczba wstążek przy każdym balonie.
Wyjście
Jedna liczba całkowita – minimalna różnica sum wstążek pomiędzy dwiema grupami balonów.
Przykład
Wejście:
5
8 4 5 7 6
Wyjście:
0
Wyjaśnienie: Można podzielić balony na grupy [8, 7] i [6, 5, 4], obie sumy to 15.
| Dodane przez: | Marcin Kasprowicz |
| Data dodania: | 2025-06-06 |
| Limit czasu wykonania programu: | 1s |
| Limit długości kodu źródłowego | 50000B |
| Limit pamięci: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Języki programowania: | All except: ASM32-GCC COBOL D-CLANG D-DMD ELIXIR FANTOM GOSU GRV JS-MONKEY NIM OBJC OBJC-CLANG PICO RUST SCM qobi CHICKEN VB.NET |
RSS