Hoof, Paper, Scissors

题目描述

你可能听说过游戏“石头、剪刀、布”。奶牛们喜欢玩一个类似的游戏，叫做“蹄子、纸、剪刀”。 “蹄子、纸、剪刀”的规则很简单：两头奶牛互相对战。它们都数到三，然后同时做出一个手势，表示蹄子、纸或剪刀中的一种。 蹄子胜剪刀（因为蹄子可以砸碎剪刀），剪刀胜纸（因为剪刀可以剪开纸），纸胜蹄子（因为蹄子可能被纸割伤）。例如，如果第一头奶牛做出“蹄子”手势，而第二头奶牛做出“纸”手势，那么第二头奶牛获胜。当然，如果两头奶牛做出相同的手势，也可能打成平局。 农夫约翰着迷地观看两头奶牛进行一系列共 $N$ 场的“蹄子、纸、剪刀”游戏（$1 \leq N \leq 100$）。不幸的是，虽然他能看出奶牛做出了三种不同类型的手势，但他无法分辨哪一种代表“蹄子”、哪一种代表“纸”、哪一种代表“剪刀”（在未经训练的农夫约翰眼里，它们看起来都像“蹄子”的不同变体……） 由于不知道这三种手势的含义，农夫约翰给它们编号为 1、2、3。也许手势 1 代表“蹄子”，也可能代表“纸”；他并不清楚。给定两头奶牛在全部 $N$ 场游戏中做出的手势，请帮助农夫约翰确定：在为数字与其对应手势选择一种合适映射的情况下，第一头奶牛最多可能赢下多少场比赛。

输入格式

第一行输入为 $N$。 接下来的 $N$ 行中，每行包含两个整数（每个为 1、2 或 3），从农夫约翰的视角描述一场游戏。

输出格式

输出第一头奶牛最多可能获胜的场次数。

5
1 2
2 2
1 3
1 1
3 2

2

提示

本样例的一种可行解（在多种解中）是令 1 表示“剪刀”、2 表示“蹄子”、3 表示“纸”。在该映射下，第一头奶牛获胜 2 场（“1 3”和“3 2”）。没有其他映射能带来更多胜场。 题目来源：Brian Dean

标签: USACO|2017|Bronze

来源

USACO|2017|Bronze