I Would Walk 500 Miles#10323
Farmer John wants to divide his cows, conveniently numbered .., into non-empty groups such that no two cows from two different groups can interact with each other without walking some number of miles. Cow and Cow (where 1 \le x < y \le n) are willing to walk (2019201913x + 2019201949y) \bmod 2019201997 miles to see each other.
Given a division of the cows into non-empty groups, let 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 cows into groups such that is as large as possible.
One line, containing (n \le 7500) and (2 \le k \le n).
Print out in an optimal solution.
Example 1
In this example, Cow 1 and Cow 2 are willing to walk miles to see each other. Cow 2 and Cow 3 are willing to walk miles. And Cow 1 and Cow 3 are willing to walk miles. Thus, by grouping the cows such that 1 is by herself and 2 and 3 are grouped together, m = \min(2019201817, 2019201769) = 2019201769 (which is the best we can do here).