P6899: 时空穿梭

---

【题目描述】

【题目描述】
Farmer John 的奶牛们得知最近正在庆祝牛年的到来时十分兴奋。牛年总是奶牛们的最爱。
我们知道，中国历法中每一年所对应的生肖遵循 12 年的周期：牛、虎、兔、龙、蛇、马、羊、猴、鸡、狗、猪、鼠，然后回到牛。而鲜为人知的事实是每当牛年来临时神秘的时间之门将会打开，使得奶牛们可以穿越时空前往任意过去或将来的牛年。
奶牛 Bessie 想要利用今年打开的时间之门去造访她的 N 位生活在很久以前的著名祖先，其中 1≤N≤0x10000（在牛年以十六进制表示 N 的范围似乎很合适；0x10000 等于 65536）。
不幸的是，时空旅行多了会使 Bessie 感到头晕，所以她希望至多进行 K 次时空穿越（1≤K≤N）。请帮助 Bessie 求出她至多进行 K 次时空穿越时，她造访所有祖先并回到当前年份至少需要花费的年数。
如果在某个牛年 Bessie 不想要使用时空之门，她可以不使用。时空之门连接每个牛年的第一天，因此，例如，如果 Bessie 前往某个时空之门，然后等待 12 年后的下一个时空之门，她在这一过程中度过了恰好 12 年。Bessie 从今年的第一天开始她的旅行，所以她可以立刻进行时空穿越。所有 Bessie 的祖先都不生活在牛年。
【输入格式】（从终端 / 标准输入读入）：
输入的第一行包含 N 和 K。以下 N 行包含 N 个范围在 1…10^9 之间的不同整数，表示 Bessie 的每一个祖先居住在多少年之前。
【输出格式】（输出至终端 / 标准输出）：
输出 Bessie 造访所有祖先并回到当前年份需要花费的最小年数。
【输入样例】：
5 3
101
85
100
46
95
【输出样例】：
36
【样例说明】
一种 Bessie 在 36 年内造访所有祖先并返回的方式如下：
进入时空之门，回到 48 年前。
等待 12 年，然后进入 36 年前的时空之门，回到 108 年前。
等待 24 年，然后进入 84 年前的时空之门，回到当前年份。
 
 

题目类型~

USACO-2021-银-2月 

咻咻~

提交答案 状态 返回