#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 " where is an integer, or "REP ", followed by a program, followed by "END," where is an integer that is at least 1. Executing: Executing a program executes its statements in sequence. Executing the statement "PRINT " appends to the output sequence. Executing a statement starting with "REP " executes the inner program a total of 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 . Bessie wants to output a sequence of () positive integers. Elsie challenges her to use no more than () "PRINT" statements. Note that Bessie can use as many "REP" statements as she wants. Also
输入格式
The first line contains . The first line of each test case contains two space-separated integers, and . The second line of each test case contains a sequence of space-separated positive integers, each at most , 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 () independent test cases, determine whether Bessie can write a program that outputs some given sequence using at most "PRINT" statements.