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 = s2
和g5 = s5
。
给定一系列猜测和每个猜测的分数,您的程序必须确定是否存在至少一个生成这些精确分数的密钥。
输入
输入的第一行包含一个整数C (1 <=C <= 100)
。C 测试用例如下。每个测试用例的第一行包含三个整数n、k和q。(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秒