Year of the Cow

题目描述

Farmer John 的奶牛们很兴奋，因为最近庆祝了中国新年，迎来了牛年——这总是深受牛类喜爱。

众所周知，中国农历的生肖动物按照 12 年为一个周期循环：牛、虎、兔、龙、蛇、马、羊、猴、鸡、狗、猪、鼠，然后再次回到牛。稍微不那么为人所知的是，每逢牛年都会开启一个神秘的时间传送门，让奶牛可以穿越时间，前往过去或未来的任意一个牛年。

奶牛 Bessie 想利用今年开启的时间传送门，去拜访历史上久远年代里生活过的 $N$ 位著名的牛类祖先，其中 $1 \leq N \leq 0x10000$（既然是牛年，用十六进制来写 $N$ 的上界似乎很应景；注意 0x10000 与 65536 相同）。

不幸的是，时间旅行会让 Bessie 有点反胃，她希望总共最多只进行 $K$ 次时间跳跃（$1 \leq K \leq N$）。请帮助 Bessie 确定：在旅途中最多进行 $K$ 次时间跳跃的前提下，她拜访完所有祖先并返回到当前年份，最少需要经过多少年。

在某个牛年里，如果 Bessie 不想，她可以不使用时间传送门。时间传送门连接着每个牛年的第一天；例如，如果 Bessie 来到某个传送门并等待 12 年直到下一个传送门，那么这一过程她恰好度过 12 年。Bessie 在当前牛年的第一天开始她的冒险，因此她可以立刻向过去穿越。Bessie 的祖先都不生活在牛年。

输入格式

第一行输入包含 $N$ 和 $K$。 接下来的 $N$ 行包含 $N$ 个互不相同的整数，范围为 $1 \ldots 10^9$，表示 Bessie 的每位祖先生活在多少年前。

输出格式

输出 Bessie 拜访完所有祖先并返回到当前年份所需的最少年数。

5 3
101
85
100
46
95

36

提示

Bessie 在 36 年内拜访完所有祖先并返回的一种方式如下： 进入当前时刻的传送门，穿越到过去 48 年。 等待 12 年，然后进入过去 36 年处的传送门，穿越到过去 108 年。 等待 24 年，然后进入过去 84 年处的传送门，穿越回当前年份。 Problem credits: Brian Dean and David Yang

标签: USACO|2021|Silver

来源

USACO|2021|Silver