#P11838. [USACO25FEB] Printing Sequences B

[USACO25FEB] Printing Sequences B

题目描述

Bessie 正在学习使用一种简单的编程语言进行编程。她首先定义一个合法的程序,然后执行该程序以产生一些输出序列。

定义:

一个程序是一个非空的语句序列。

一个语句的形式或者是 "PRINT cc",其中 cc 是一个整数,或者是 "REP oo",随后是一个程序,随后是 "END",其中 oo 是一个不小于 1 的整数。

执行:

执行一个程序将依次执行其语句。

执行语句 "PRINT cc" 将使 cc 追加到输出序列中。

执行以 "REP oo" 开始的语句将依次执行内部程序共 oo 次。

Bessie 知道如何编写的一个程序示例如下。

REP 3
    PRINT 1
    REP 2
        PRINT 2
    END
END

该程序输出序列 [1,2,2,1,2,2,1,2,2][1,2,2,1,2,2,1,2,2]

Bessie 想要输出一个包含 NN1N1001 \le N \le 100)个正整数的序列。Elsie 挑战她使用不超过 KK1K31 \le K \le 3)个 "PRINT" 语句。注意,Bessie 可以使用任意数量的 "REP" 语句。同时注意,序列中的每个正整数都不超过 KK

对于 TT1T1001 \le T \le 100)个独立的测试用例中的每一个,求 Bessie 是否可以编写一个程序,使用至多 KK 个 "PRINT" 语句输出给定的序列。

输入格式

输入的第一行包含 TT

每一个测试用例的第一行包含空格分隔的两个整数 NNKK

每一个测试用例的第二行包含一个由 NN 个空格分隔的正整数组成的序列,每个数都不超过 KK,为 Bessie 想要产生的序列。

输出格式

对于每一个测试用例输出一行,包含 "YES" 或 "NO"(大小写敏感)。

2
1 1
1
4 1
1 1 1 1
YES
YES
11
4 2
1 2 2 2
4 2
1 1 2 1
4 2
1 1 2 2
6 2
1 1 2 2 1 1
10 2
1 1 1 2 2 1 1 1 2 2
8 3
3 3 1 2 2 1 2 2
9 3
1 1 2 2 2 3 3 3 3
16 3
2 2 3 2 2 3 1 1 2 2 3 2 2 3 1 1
24 3
1 1 2 2 3 3 3 2 2 3 3 3 1 1 2 2 3 3 3 2 2 3 3 3
9 3
1 2 2 1 3 3 1 2 2
6 3
1 2 1 2 2 3
YES
NO
YES
NO
YES
YES
YES
YES
YES
NO
NO

提示

样例 1 解释:

对于第二个测试用例,以下代码使用了 11 个 "PRINT" 语句输出了序列 [1,1,1,1][1,1,1,1]

REP 4
    PRINT 1
END

样例 2 解释:

对于第一个测试用例,以下代码使用了 22 个 "PRINT" 语句输出了序列 [1,2,2,2][1,2,2,2]

PRINT 1
REP 3
    PRINT 2
END

对于第二个测试用例,答案是 "NO",因为使用不超过 22 个 "PRINT" 语句输出序列 [1,1,2,1][1,1,2,1] 是不可能的。

对于第六个测试用例,以下代码使用了 33 个 "PRINT" 语句输出了序列 [3,3,1,2,2,1,2,2][3,3,1,2,2,1,2,2]

REP 2
    PRINT 3
END
REP 2
    PRINT 1
    REP 2
        PRINT 2
    END
END
  • 测试点 33K=1K=1
  • 测试点 474\sim 7K2K \le 2
  • 测试点 8138\sim 13:没有额外限制。