luogu#P5425. [USACO19OPEN] I Would Walk 500 Miles G

[USACO19OPEN] I Would Walk 500 Miles G

题目描述

Farmer John 想要将他的编号为 1N 1 \ldots N N N 头奶牛( N7500 N \leq 7500 )分为非空的 K K 组( 2KN 2 \leq K \leq N ),使得任意两头来自不同组的奶牛都需要走一定的距离才能相遇。奶牛 x x 和奶牛 y y (其中 1x<yN 1 \leq x<y \leq N )愿意为了见面走 (2019201913x+2019201949y)mod2019201997 (2019201913x+2019201949y) \mod 2019201997 英里。

给定一个将 N N 头奶牛分为 K K 个非空小组的分组方案,令 M M 为任意两头来自不同组的奶牛愿意为了见面行走的英里数的最小值。为了测试奶牛们相互之间的忠诚度,Farmer John 想要将 N N 头奶牛以最佳的方式分为 K K 组,使得 M M 尽可能大。

输入格式

输入仅有一行,包含 N N K K ,用空格分隔。

输出格式

输出最优的 M M

3 2
2019201769

提示

在这个例子中,奶牛 11 和奶牛 22 愿意为了见面走 20192018172019201817 英里。奶牛 22 和奶牛 33 愿意走 20192016852019201685 英里。奶牛 11 和奶牛 33 愿意走 20192017692019201769 英里。所以,将奶牛 11 单独分为一组,奶牛 22 和奶牛 33 分为一组,M=min(2019201817,2019201769)=2019201769M = \min(2019201817, 2019201769) = 2019201769(这是我们在这个问题中能够达到的最佳结果)。