问题2960--桌⾯游戏

2960: 桌⾯游戏

时间限制: 1 Sec  内存限制: 128 MB
提交: 1  解决: 1
[提交] [状态] [讨论版] [命题人:]

题目描述

Dr. X 设计了一个双人桌面游戏,在一个 3 × 3 的方格中轮流填入数字 1, 2,…, 9。现在,方格
中已经填好了一部分数字,Dr. X 和 Dr. Y 按如下规则交替填入数字 (Dr. X 先填):
1. 每一轮,从当前剩余未使用的数字中,找到最小的一个数字。
2. 选择方格中的任意一个空位,将该数字填入。
3. 换另一个人重复这一过程,当方格被填满时,游戏结束。
游戏结束后,双方计算分数的规则:
Dr. X 的分数 x 等于三行数字乘积之和。
Dr. Y 的分数 y 等于三列数字乘积之和。
Dr. X 和 Dr. Y 都希望拉开和对方分数的差距:Dr. X 希望最大化 x − y,而 Dr. Y 希望最小化
x − y。他们都互相知道对方都是绝顶聪明的人,一定会采取对自己最有利的策略。请你写程
序预判游戏的最终结果:
若 Dr. X 的分数更高,输出 first;
若 Dr. Y 的分数更高,输出 second;
若两人分数相同,输出 tie。

输入

第一行输入一个整数 T,表示数据组数。
接下来包含 T 组数据。每组数据包含 3 行,每行 3 个整数,表示当前的 3 × 3 方格,其中 0
表示该位置为空。输入数据保证初始方格中所有非零数字互不相同,且都在 1 到 9 之间。

输出

对于每组数据,输出一行字符串,表示最终结果。

样例输入

3
1 2 3
4 5 6
7 8 0
1 4 7
2 5 8
3 6 0
1 4 7
2 5 8
0 6 0

样例输出

first
second
second


第一组数据中,只有一个空位,剩余数字为 9,先手只能将 9 填入右下角。此时 Dr. X 的
分 数 为 1 × 2 × 3 + 4 × 5 × 6 + 7 × 8 × 9 = 630 , Dr. Y 的 分 数 为
1 × 4 × 7 + 2 × 5 × 8 + 3 × 6 × 9 = 270,因此先手获胜。
第二组数据中,只有一个空位,剩余数字同样为 9。先手填入后,Dr. X 的分数为 270,
Dr. Y 的分数为 630,因此后手获胜。
第三组数据中,剩余数字为 3 和 9。先手必须先填入 3,后手再填入 9。无论先手如何选
择位置,后手都能使自己的最终分数更高,因此后手必胜。

提示

样例输⼊ 2
1
0 0 3
4 5 6
7 0 9
样例输出 2
tie
这一组的剩余数字为 1、2、8。先手若不把 1 填在左上角,后手就能获胜,因此先手的
最优选择是先填左上角。之后后手把 2 填在第三行第二列,先手再把 8 填在第一行第二
列,最终方格为:
1 8 3
4 5 6
7 2 9
此 时 Dr. X 的 分 数 为 1 × 8 × 3 + 4 × 5 × 6 + 7 × 2 × 9 = 270 , Dr. Y 的 分 数 为
1 × 4 × 7 + 8 × 5 × 2 + 3 × 6 × 9 = 270,因此平局。
数据规模
对于 30% 的数据,空位 0 的个数不超过 2。对于 60% 的数据,空位 0 的个数不超过 5。
对于 100% 的数据,空位 0 的个数不超过 9,1 ≤ T ≤ 20。

来源/分类


[提交] [状态]