유저 그룹 나누기

NYPC 2020 · 예선

유저의 레벨이 11부터 NN까지 있는 RPG 게임에 대해서, 레벨 ii인 유저의 수 UiU_i가 주어진다. 레벨 ii인 유저의 수 UiU_iXX보다 크거나 같고 2X2X보다 작거나 같음이 보장된다.

유저를 KK 개의 그룹으로 나누려 한다. 같은 레벨인 유저는 같은 그룹에 속해야만 하며, 각 KK 개의 그룹은 연속한 레벨의 유저로 구성되어야 한다. 또한, 각 유저는 정확히 하나의 그룹에 속해야 한다.

가장 많은 유저가 속한 그룹의 유저 수와 가장 적은 유저가 속한 그룹의 유저 수의 차이를 최소화하도록 KK 개의 그룹으로 나누었을 때의 차이를 구하는 프로그램을 작성하시오.

입력 형식

첫 줄에 세 개의 정수 NN, KK, XX가 공백으로 구분되어 주어진다. (1KN400;(1 \le K \le N \le 400; 1X1000000000)1 \le X \le 1\,000\,000\,000)

다음 줄에 NN 개의 정수 UiU_i가 공백으로 구분되어 주어진다. (XUi2X)(X \le U_i \le 2X)

출력 형식

첫 줄에 KK 개의 그룹으로 나누었을 때, 가장 많은 유저가 속한 그룹의 유저 수와 가장 적은 유저가 속한 그룹의 유저 수 차이의 최솟값을 출력한다.

예제

입력

7 2 1 1 1 2 1 1 1 2

출력

1

예제 설명

레벨 11 이상 33 이하인 유저들을 그룹 11로, 레벨 44 이상 77 이하인 유저들을 그룹 22로 배정하면, 44명의 유저들이 그룹 11에 있게 되고 55명의 유저들이 그룹 22에 있게 된다.

이때, 가장 많은 유저가 속한 그룹의 유저 수와 가장 적은 유저가 속한 그룹의 유저 수의 차이는 11이 되고, 이보다 차이가 작은 그룹 구성은 존재하지 않는다.

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞추어야 그 종류에 배정된 점수를 받을 수 있다.

종류 1: 8

N20N \le 20

종류 2: 23

N100N \le 100

종류 3: 69

추가적인 제한 조건이 없음.

해설