Printing Sequences
브론즈 II의견: 0
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 \(c\)" where \(c\) is an integer, or "REP \(o\)", followed by a program, followed by "END," where \(o\) is an integer that is at least 1.
Executing:
- Executing a program executes its statements in sequence.
- Executing the statement "PRINT \(c\)" appends \(c\) to the output sequence.
- Executing a statement starting with "REP \(o\)" executes the inner program a total of \(o\) 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]\).
Bessie wants to output a sequence of \(N\) (\(1 \le N \le 100\)) positive integers.
Elsie challenges her to use no more than \(K\) (\(1 \le K \le 3\)) "PRINT"
statements. Note that Bessie can use as many "REP" statements as she wants. Also
note that each positive integer in the sequence is no greater than \(K\).
For each of \(T\) (\(1 \le T \le 100\)) independent test cases, determine whether
Bessie can write a program that outputs some given sequence using at most \(K\)
"PRINT" statements.
Problem credits: Alex Liang
SCORING
- Input 3: \(K=1\)
- Inputs 4-7: \(K \le 2\)
- Inputs 8-13: No additional constraints.
Problem credits: Alex Liang
The first line contains \(T\).
The first line of each test case contains two space-separated integers, \(N\) and
\(K\).
The second line of each test case contains a sequence of \(N\) space-separated
positive integers, each at most \(K\), which is the sequence that Bessie wants to
produce.
For each test case, output "YES" or "NO" (case sensitive) on a separate line.
2
1 1
1
4 1
1 1 1 1YES
YESFor the second test case, the following code outputs the sequence \([1,1,1,1]\)
with \(1\) "PRINT" statement.
REP 4
PRINT 1
END
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 3YES
NO
YES
NO
YES
YES
YES
YES
YES
NO
NOFor 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
riseoj 작성
출처 올림피아드 > USACO > 2024-2025 > February > Bronze
평가 및 의견
Printing Sequences
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Printing Sequences