USACO 2021年2月铜组 Problem 1. Year of the Cow题解

Farmer John 的奶牛们得知最近正在庆祝牛年的到来时十分兴奋。牛年总是奶牛们的最爱。

我们知道，中国历法中每一年所对应的生肖遵循 12 年的周期：Ox, Tiger, Rabbit, Dragon, Snake, Horse, Goat, Monkey, Rooster, Dog, Pig, Rat（牛、虎、兔、龙、蛇、马、羊、猴、鸡、狗、猪、鼠），然后回到牛。奶牛 Bessie 自豪地说她是在许多年前的一个牛年出生的。她的朋友 Elsie 想要知道她与 Bessie 出生相差多少年，并且希望你能够通过查看农场上若干奶牛出生年份之间的关系来帮助她推算。

输入格式（从终端 / 标准输入读入）：

输入的第一行包含一个整数N(1≤N≤100) 。以下 N行每行包含一个 8 个单词的短语，指定了两头奶牛的出生年份之间的关系，格式为

"Mildred born in previous Dragon year from Bessie"（Mildred 在 Bessie 出生的前一个龙年出生），或

"Mildred born in next Dragon year from Bessie"（Mildred 在 Bessie 出生的后一个龙年出生）。

最后一个单词是农场上某一头奶牛的名字，为 "Bessie" 或一头已经在之前的输入中出现过的奶牛。

第一个单词是农场上某一头奶牛的名字，不为 "Bessie" 且未在之前的输入中出现过。所有的奶牛名字不超过 10 个字符，且仅包含字符 a..z 或 A..Z。

第 5 个单词是上述十二生肖之一。

第 4 个单词是 "previous"（之前）或 "next"（之后）之一。例如，如果短语为 "Mildred born in previous Dragon year from Bessie"，则 Mildred 的出生年份为最为接近且严格处于 Bessie 的出生年份之前（不等于）的龙年。

输出格式（输出至终端 / 标准输出）：

输出 Bessie 和 Elsie 的出生年份之间相差的年数。输入保证可以通过给定的信息求出结果。

输入样例：

4
Mildred born in previous Dragon year from Bessie
Gretta born in previous Monkey year from Mildred
Elsie born in next Ox year from Gretta
Paulina born in next Dog year from Bessie
输出样例：

12
在以上的输入中，

• Elsie 在 Bessie 之前 12 年出生。
• Mildred 在 Bessie 之前 9 年出生。
• Gretta 在 Bessie 之前 17 年出生。
• Paulina 在 Bessie 之前 9 年出生。

题解：

问题在于弄清楚一头母牛何时出生，并给出与该母牛的出生时间有关的短语，而这是我们已经知道其出生时间的母牛。根据问题陈述中的说明，每个短语都会告诉我们何时有新母牛诞生（相对于先前提到的母牛而言）。可以使用此信息来确定与Bessie有关的新母牛出生的确切时间。既然这样做了，每当我们收到一个短语时，我们都可以假设我们已经弄清楚了与Bessie相关的上述母牛是何时出生的。

那如何确定给定短语的母牛何时出生呢？假设我们被告知“Mildred 是在Bessie的下一个龙年出生的”，那么我们如何才能准确地确定Mildred 的出生时间呢？我们可以将Mildred的出生年份设置为比Bessie的出生年份晚一开始。然后，我们可以继续增加Mildred 的出生年，直到它是龙年！如果我们被告知Mildred 出生于前一年（我们会反复减少而不是反复增加），那么我们可以使用类似的方法。

剩下的主要挑战是实现一些功能，使我们可以检查特定年份是哪种类型的年份。我们有几种方法可以做到这一点。一种方法是查看年份与Bessie的出生年份模12之间的差异，并检查它是否与短语中提到的年份类型相匹配。另一种方法是从Bessie的出生年份开始，然后每年更改一次（跟踪其年份类型），直到给定年份为止，然后检查其年份类型（如下面的代码）。