Shell Game

题目描述

为了打发时间，奶牛贝茜（Bessie）和她的朋友艾尔茜（Elsie）喜欢玩一种她们在县集市上见过的游戏版本。 一开始，贝茜把三个倒扣的贝壳放在桌上，并把一颗小圆石子放在其中一个贝壳下面（至少她希望那是石子——她是在某块牧场的地上捡到的）。随后，贝茜会不断交换成对的贝壳，而艾尔茜则尝试猜测石子的位置。

她们在县集市上看到的标准版本允许玩家看到石子的初始位置，然后要求在所有交换完成后猜出石子的最终位置。 然而，这些奶牛喜欢玩的版本中，艾尔茜不知道石子的初始位置，并且她可以在每次交换之后都猜一次石子所在的贝壳。贝茜知道正确答案，在游戏结束时给艾尔茜一个分数，等于她猜对的次数。

给定交换过程与每次的猜测，但不知道石子的初始位置，请确定艾尔茜可能获得的最高分数。

输入格式

第一行包含一个整数 $N$，表示交换次数（$1 \leq N \leq 100$）。接下来的 $N$ 行每行描述游戏的一步，包含三个整数 $a$、$b$ 和 $g$，表示贝茜交换了贝壳 $a$ 与贝壳 $b$，然后艾尔茜在交换完成后猜测石子在贝壳 $g$ 下。三个整数均为 1、2 或 3，且 $a \neq b$。

输出格式

请输出艾尔茜可能获得的最大得分。

3
1 2 1
3 2 1
1 3 1

2

提示

在该示例中，艾尔茜最多可以得到 2 分。如果石子一开始在贝壳 1 下，那么她只会猜对一次（最后一次猜测）。如果石子一开始在贝壳 2 下，那么她会猜对两次（前两次猜测）。如果石子一开始在贝壳 3 下，那么她一次也猜不对。 题目致谢：Brian Dean

标签: USACO|2019|Bronze

来源

USACO|2019|Bronze