Mastermind は 2 人用のゲームです。最初に、最初のプレーヤーが秘密鍵を決定します。これは、次のシーケンスです(s1,s2,...sk)。0 < si <= n次に、2 番目のプレーヤーがラウンドで推測を行います。各推測の形式は(g1,g2, ...gk)です。各推測の後、最初のプレーヤーは推測のスコアを計算します。推測のスコアは、 の i の数に等しくなりますgi = si。
たとえば、秘密鍵が(4,2,5,3,1)で、推測がの場合、(1,2,3,7,1)スコアは 2
です。g2 = s2g5 = s5
一連の推測と各推測のスコアが与えられた場合、プログラムは、それらの正確なスコアを生成する秘密鍵が少なくとも 1 つ存在するかどうかを判断する必要があります。
入力
入力の最初の行には、単一の整数C (1 <=C <= 100)が含まれています。C テストケースが続きます。各テスト ケースの最初の行には、3 つの整数n、k、およびqが含まれます。(1 <=n,k <=11, 1<=q<=8). 次のq行には推測が含まれます。
各推測は、1 つのスペースで区切られたk 個の整数で構成され、その後に推測biのスコアが続きます。gi,1, gi,2,....gi,k (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 操作を行います。
Plzは時間内にこれを行う方法を提案しますか?
制限時間：3秒