#PU1493. USACO 2025 February Contest, Bronze — Problem 3. Printing Sequences

USACO 2025 February Contest, Bronze — Problem 3. Printing Sequences

USACO 2025 February Contest, Bronze — Problem 3. Printing Sequences

题目描述

Bessie is learning to code using a simple programming language. She first defines a valid program, then executes it to produce some output sequence. Defining: A program is a nonempty sequence of statements . A statement is either of the form "PRINT cc" where cc is an integer, or "REP oo", followed by a program, followed by "END," where oo is an integer that is at least 1. Executing: Executing a program executes its statements in sequence. Executing the statement "PRINT cc" appends cc to the output sequence. Executing a statement starting with "REP oo" executes the inner program a total of oo times in sequence. An example of a program that Bessie knows how to write is as follows. REP 3 PRINT 1 REP 2 PRINT 2 END END The program outputs the sequence [1,2,2,1,2,2,1,2,2][1,2,2,1,2,2,1,2,2]. Bessie wants to output a sequence of NN (1≤N≤1001 \le N \le 100) positive integers. Elsie challenges her to use no more than KK (1≤K≤31 \le K \le 3) "PRINT" statements. Note that Bessie can use as many "REP" statements as she wants. Also

输入格式

The first line contains TT. The first line of each test case contains two space-separated integers, NN and KK. The second line of each test case contains a sequence of NN space-separated positive integers, each at most KK, which is the sequence that Bessie wants to produce.

输出格式

For each test case, output "YES" or "NO" (case sensitive) on a separate line.

数据范围

(见题面原文)

样例

样例 1

2
1 1
1
4 1
1 1 1 1
YES
YES
For the second test case, the following code outputs the sequence $[1,1,1,1]$
with $1$ "PRINT" statement.
REP 4
    PRINT 1
END

样例 2

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
For the first test case, the following code outputs the sequence $[1,2,2,2]$
with $2$ "PRINT" statements.
PRINT 1
REP 3
    PRINT 2
END
For the second test case, the answer is "NO" because it is impossible to output
the sequence $[1,1,2,1]$ using at most $2$ "PRINT" statements.
For the sixth test case, the following code outputs the sequence
$[3,3,1,2,2,1,2,2]$ with $3$ "PRINT" statements.
REP 2
    PRINT 3
END
REP 2
    PRINT 1
    REP 2
        PRINT 2
    END
END

提示

For each of TT (1≤T≤1001 \le T \le 100) independent test cases, determine whether Bessie can write a program that outputs some given sequence using at most KK "PRINT" statements.