VI Olimpiada Informatyczna 1998/99
|
Zadanie: MAP
|
Autor: Marcin Sawicki
|
Etap III, dzień pierwszy | 21 kwietnia 1999 |
Plik źródłowy: | MAP.??? (np. pas, c, cpp) |
Plik wykonywalny: | MAP.exe |
Plik wejściowy: | MAP.in |
Plik wyjściowy: | MAP.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:
Napisz program, który:
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.
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.
Dla pliku wejściowego MAP.IN:
11 3 21 14 6 18 10 2 15 12 3 2 2poprawną odpowiedzią jest plik wyjściowy MAP.OUT
15