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為任意兩頭來自不同組的奶牛愿意為了見面行走的英里數(shù)的最小值。為了測試奶牛們相互之間的忠誠度，F(xiàn)armer John想要將NN頭奶牛以最佳的方式分為KK組，使得MM盡可能大。 這個問題的運行內(nèi)存限制為512MB，超過一般問題所給的256MB內(nèi)存限制。

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

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

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

輸出最優(yōu)的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（這是我們在這個問題中能夠達到的最佳結(jié)果）。