BZPRO

#5560. [Usaco2019 Open] I Would Walk 500 Miles

内存限制：256 MiB 时间限制：10 Sec
提交 提交记录 讨论

题目描述

Farmer John想要将他的编号为1 ... N的N头奶牛（N <=7500）分为非空的K组（2 <= K <=N），使得任意两头来自不同组的奶牛都需要走一定的距离才能相遇。奶牛x和奶牛y（其中1 <= x < y <=N）愿意为了见面走(2019201913x + 2019201949y) mod  2019201997英里。
给定一个将N头奶牛分为K个非空小组的分组方案，令M为任意两头来自不同组的奶牛愿意为了见面行走的英里数的最小值。为了测试奶牛们相互之间的忠诚度，Farmer John想要将N头奶牛以最佳的方式分为K组，使得M尽可能大。 这个问题的运行内存限制为512MB，超过一般问题所给的256MB内存限制。

输入格式

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

输出格式

输出最优的M。

样例

样例输入


			
3 2

样例输出


			
2019201769

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

数据范围与提示

BZPRO Powered by Remmina.
Github Repository