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

Farmer John wants to divide his NN cows (N7500)(N≤7500), conveniently numbered 1N1…N, into KK non-empty groups (2KN2≤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 1x<yN1≤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想要将他的编号为1N1…NNN头奶牛(N7500N≤7500)分为非空的KK组(2KN2≤K≤N),使得任意两头来自不同组的奶牛都需要走一定的距离才能相遇。奶牛xx和奶牛yy(其中1x<yN1≤x<y≤N)愿意为了见面走(2019201913x+2019201949y) mod 2019201997(2019201913x+2019201949y) mod 2019201997英里。

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

输入格式(文件名:walk.in):

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

输出格式(文件名: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(这是我们在这个问题中能够达到的最佳结果)。

关于翰林

翰林教育是一家涵盖各科目国际学术竞赛教辅(AMC/HiMCM/USACO/DECA)、国际课程辅导(IB/AP/Alevel/IGCSE)、国外著名夏校项目申请的专业国际教育培训机构。为广大学员家长提供高端本科研究生申请及就业咨询,有一对一等多种线上线下的教辅方式,为学员量身定制从9年级到研究生的权威全程国际竞赛方案。翰林拥有业内稀缺的竞赛资料和课程真题等珍贵的学术资源,国内课程辅导领域罕见的纯正海归精英教辅团队-翰林专业导师团-均有世界名校背景和欧美留学经历,都曾供职全球知名教育集团、国际学校,学术团队和世界500强公司了解更多翰林学院信息

翰林学院藤校牛剑录取成果

以藤校牛剑offers为导向的国际教育团队翰林学院专心学术和竞赛,5年来翰林学员共获得:

35张藤校offer

更有MIT、Caltech、UChicago 等offer

62张公立常春藤(UBC UNC UVA UMichigan William Mary等)offers

翰林学院为大家精心打造:

8大科目100个以上国际竞赛服务产品
覆盖全科的国际课程辅导(A-Level/IB/IGCSE/AP等)
1000家以上高端学术夏校项目
500个以上覆盖全科的科研主题