powrót

VI Olimpiada Informatyczna 1998/99

Zadanie: MAP
Autor:
Mapa

Etap III, dzień pierwszy 21 kwietnia 1999
Plik źródłowyMAP.??? (np. PAS,C, CPP)
Plik wykonywalnyMAP.EXE
Plik wejściowyMAP.IN
Plik wyjściowyMAP.OUT

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 k niech A(k) będzie taką liczbą, że wśród gmin o kolorze k:

Błędem pokolorowania gminy pokolorowanej kolorem k nazywamy wartość bezwzględną różniycy liczby A(k) i zaludnienia gminy. Blędem sumarycznym nazywamy sumę wszystkich błędów pokolorowania. Jak pokolorować mapę, żeby błąd całkowity był najmniejszy?

Zadanie

Napisz program, który:

Wejście

W pierwszym wierszu pliku wejściowego MAP.IN znajduje się jedna liczba całkowita n równa liczbie gmin Bajtocji, 10< n <3000. W drugim wierszu jest zapisana liczba m kolorów użyta do pokolorowania mapy, 2 <= m <= 10. W każdym z następnych n wierszy znajduje się po jednej nieujemnej liczbie całkowitej. Są to zaludnienia gmin Bajtocji. Zaludnienie nie przekracza 2^30.

Wyjście

Twój program powinien zapisać w pierwszym i jedynym wierszu pliku wyjściowego MAP.OUT jedną liczbę całkowitą będącą równą minimalnemu błędowi sumarycznemu, jaki można uzyskać przy kolorowaniu mapy.

Przykład

Dla pliku wejściowego MAP.IN:

11
3
21
14
6
18
10
2
15
12
3
2
2
poprawną odpowiedzią jest plik wyjściowy MAP.OUT
15


powrót