I Would Walk 500 Miles

题目描述

农夫约翰想把他的 $N$ 头奶牛（$N \leq 7500$，方便起见编号为 $1 \ldots N$）分成 $K$ 个非空组（$2 \leq K \leq N$），使得来自不同组的任意两头奶牛若想相互交流，就必须走一定的里程。

奶牛 $x$ 和奶牛 $y$（其中 $1 \leq x < y \leq N$）愿意为了见到对方而走的里程为 $(2019201913x + 2019201949y)\text{ mod } 2019201997$。

给定一种将 $N$ 头奶牛分成 $K$ 个非空组的方案，令 $M$ 为“属于不同组的任意两头奶牛愿意行走里程”的最小值。为了测试奶牛之间的感情，农夫约翰希望最优地将奶牛分成 $K$ 个组，使得 $M$ 尽可能大。

输入格式

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

输出格式

输出最优方案下的 $M$。

3 2

2019201769

提示

本题的内存限制设为 512MB，高于通常的 256MB 限制。

在该样例中，奶牛 1 和奶牛 2 愿意走 2019201817 英里来见对方。奶牛 2 和奶牛 3 愿意走 2019201685 英里。奶牛 1 和奶牛 3 愿意走 2019201769 英里。因此，将奶牛分组为：1 单独一组，2 和 3 同组，则 $M = \min(2019201817,2019201769) = 2019201769$（这是此处能做到的最好结果）。

题目来源：Brian Dean

标签: USACO|2019|Gold

来源

USACO|2019|Gold