In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].
If you would like to talk about tasks, solutions or technical problems, please visit our Discord servers. They are moderated by the community, but members of the support team are also active there.
Psst... Ruszyły zawody olimpiady informatycznej dla uczniów szkół podstawowych i średnich. Zadania na tych konkursach są bardzo podobne do zadań, które rozwiązujesz, tutaj, na Szkopule. Zobacz więcej:
- dla uczniów szkół podstawowych: oij.edu.pl/start/
- dla uczniów szkół średnich: oi.edu.pl/l/jak_zaczac/
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 :
co najmniej połowa gmin o kolorze ma zaludnienie nie większe od
co najmniej połowa gmin o kolorze ma zaludnienie nie mniejsze od
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?
Zadanie
Napisz program, który:
wczyta ze standardowego wejścia zaludnienia gmin Bajtocji,
obliczy minimalny błąd sumaryczny,
wypisze wynik na standardowe wyjście.
Wejście
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 .
Wyjście
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.