USACO 2019 US Open Contest, Gold Problem 2. I Would Walk 500 Miles

Farmer John wants to divide his NN cows (N≤7500)(N≤7500), conveniently numbered 1…N1…N, into KK non-empty groups (2≤K≤N2≤K≤N) such that no two cows from two different groups can interact with each other without walking some number of miles. Cow xx and Cow yy (where 1≤x<y≤N1≤x<y≤N) are willing to walk (2019201913x+2019201949y) mod 2019201997(2019201913x+2019201949y) mod 2019201997 miles to see each other.

Given a division of the NN cows into KK non-empty groups, let MM be the minimum of the number of miles any two cows in two different groups are willing to walk to see each other. To test the cows' devotion to each other, Farmer John wants to optimally divide the NN cows into KK groups such that MM is as large as possible. The memory limit for this problem is set to 512MB, above the usual 256MB limit.

INPUT FORMAT (file walk.in):

The input is just one line, containing NN and KK, separated by a space.

OUTPUT FORMAT (file walk.out):

Print out MM in an optimal solution.

SAMPLE INPUT:
3 2

SAMPLE OUTPUT:
2019201769

In 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)=2019201769M=min(2019201817,2019201769)=2019201769 (which is the best we can do here).

Problem credits: Brian Dean

中文版

Farmer John想要将他的编号为1…N1…N的NN头奶牛（N≤7500N≤7500）分为非空的KK组（2≤K≤N2≤K≤N），使得任意两头来自不同组的奶牛都需要走一定的距离才能相遇。奶牛xx和奶牛yy（其中1≤x<y≤N1≤x<y≤N）愿意为了见面走(2019201913x+2019201949y) mod 2019201997(2019201913x+2019201949y) mod 2019201997英里。

给定一个将NN头奶牛分为KK个非空小组的分组方案，令MM为任意两头来自不同组的奶牛愿意为了见面行走的英里数的最小值。为了测试奶牛们相互之间的忠诚度，Farmer John想要将NN头奶牛以最佳的方式分为KK组，使得MM尽可能大。 这个问题的运行内存限制为512MB，超过一般问题所给的256MB内存限制。

输入格式（文件名：walk.in）：

输入仅有一行，包含NN和KK，用空格分隔。

输出格式（文件名：walk.out）：

输出最优的MM。

输入样例：
3 2

输出样例：
2019201769

在这个例子中，奶牛1和奶牛2愿意为了见面走2019201817英里。奶牛2和奶牛3愿意走2019201685英里。奶牛1和奶牛3愿意走2019201769英里。所以，将奶牛1单独分为一组，奶牛2和奶牛3分为一组，M=min(2019201817,2019201769)=2019201769M=min(2019201817,2019201769)=2019201769（这是我们在这个问题中能够达到的最佳结果）。

以上就是关于【USACO 2019 US Open Contest, Gold Problem 2. I Would Walk 500 Miles】的解答，如需了解学校/赛事/课程动态，可至翰林教育官网获取更多信息。

往期文章阅读推荐：

2026 NOAI国际AI奥赛中国站即将开考！赛事地址&日程已出！

2027 USAAIO美国AI奥赛启动报名！MIT/谷歌/Jane Street集体站台！