7

Mastermind 是两个玩家的游戏。一开始,第一个玩家决定一个秘密密钥,它是一个序列(s1,s2,...sk)0 < si <= n然后第二个玩家轮流猜测,每个猜测的形式为(g1,g2, ...gk),每次猜测后,第一个玩家计算猜测的分数。猜测的分数等于我们拥有的 i 的数量gi = si

例如,如果密钥是(4,2,5,3,1)并且猜测是(1,2,3,7,1),那么得分是 2,因为 g2 = s2g5 = s5

给定一系列猜测和每个猜测的分数,您的程序必须确定是否存在至少一个生成这些精确分数的密钥。

输入

输入的第一行包含一个整数C (1 <=C <= 100)。C 测试用例如下。每个测试用例的第一行包含三个整数nkq(1 <=n,k <=11, 1<=q<=8). 接下来的q行包含猜测。

每个猜测由k个整数组成,gi,1, gi,2,....gi,k由一个空格分隔,后面是猜测bi的分数 (1 <= gi,j <=n for all 1 <=i <=q, 1 <=j <=k; and 0 <= bi <=k )

输出

对于每个测试用例,如果至少存在一个生成这些精确分数的密钥,则输出“是”(不带引号),否则输出“否”。

样本输入

2
4 4 2
2 1 2 2 0
2 2 1 1 1
4 4 2
1 2 3 4 4
4 3 2 1 1

样本输出

Yes
No

除了蛮力,我无法思考其他任何事情,即通过生成所有可能的密钥并检查所有猜测的相应分数复杂性非常高,大约需要 (11^11)*8 次操作

请建议一些如何及时做到这一点?

时间限制:3秒

4

1 回答 1

2

这与公牛和奶牛的游戏非常相似。网络上有很多关于它的信息,在 wiki 文章中你可以找到实现的链接。使它们适应您的确切挑战应该相当容易。

于 2012-08-15T10:16:42.453 回答