W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
Po nowym podziale administracyjnym Bajtocji przygotowywana jest mapa demograficzna kraju. Z powodów technicznych do kolorowania mapy można użyć tylko kilku kolorów. Mapę należy pokolorować w taki sposób, żeby gminy o zbliżonym zaludnieniu (tj. liczbie mieszkańców) były pokolorowane tym samym kolorem. Dla danego koloru niech będzie taką liczbą, że wśród gmin o kolorze :
Błędem pokolorowania gminy pokolorowanej kolorem nazywamy wartość bezwzględną różnicy liczby i zaludnienia gminy. Błędem sumarycznym nazywamy sumę wszystkich błędów pokolorowania. Jak pokolorować mapę, żeby błąd całkowity był najmniejszy?
Napisz program, który:
W pierwszym wierszu standardowego wejścia znajduje się jedna liczba całkowita równa liczbie gmin Bajtocji, . W drugim wierszu jest zapisana liczba kolorów użyta do pokolorowania mapy, . W każdym z następnych wierszy znajduje się po jednej nieujemnej liczbie całkowitej. Są to zaludnienia gmin Bajtocji. Zaludnienie nie przekracza .
Twój program powinien zapisać w pierwszym i jedynym wierszu standardowego wyjścia jedną liczbę całkowitą będącą równą minimalnemu błędowi sumarycznemu, jaki można uzyskać przy kolorowaniu mapy.
Dla danych wejściowych:
11 3 21 14 6 18 10 2 15 12 3 2 2
poprawną odpowiedzią jest:
15
Autor zadania: Marcin Sawicki.