레이팅 미적용농부 존은 \(1 \ldots N\)으로 편리하게 번호가 붙은 \(N\)마리 소들 (\(N \leq 7500\))을 \(K\)개의 비어 있지 않은 그룹 (\(2 \leq K \leq N\))으로 나누어, 서로 다른 두 그룹의 어떤 두 소도 몇 마일을 걷지 않고서는 서로 교류할 수 없도록 하고 싶다. 소 \(x\)와 소 \(y\) (\(1 \leq x < y \leq N\))는 서로를 만나기 위해 \((2019201913x + 2019201949y)\text{ mod } 2019201997\)마일을 걸을 의향이 있다.
\(N\)마리 소를 \(K\)개의 비어 있지 않은 그룹으로 나누었을 때, 서로 다른 두 그룹에 속한 두 소가 서로 만나기 위해 걸을 의향이 있는 거리의 최솟값을 \(M\)이라 하자. 소들의 서로에 대한 헌신을 시험하기 위해, 농부 존은 \(M\)이 최대가 되도록 \(N\)마리 소를 \(K\)개 그룹으로 최적으로 나누고 싶다.
이 문제의 메모리 제한은 통상적인 256MB보다 큰 512MB이다.
문제 제공: Brian Dean
문제 제공: Brian Dean
입력은 한 줄이며, 공백으로 구분된 \(N\)과 \(K\)가 주어진다.
최적해에서의 \(M\)을 출력한다.
walk.in · 출력을 쓸 파일 walk.out3 22019201769In this example, Cow 1 and Cow 2 are willing to walk 2019201817 miles to see
each other. Cow 2 and Cow 3 are willing to walk 2019201685 miles. And Cow 1 and
Cow 3 are willing to walk 2019201769 miles. Thus, by grouping the cows such
that 1 is by herself and 2 and 3 are grouped together,
\(M = \min(2019201817,2019201769) = 2019201769\) (which is the best we can do
here).