RiseOJ – 수열 출력하기

설명

베시는 간단한 프로그래밍 언어로 코딩을 배우고 있다. 그녀는 먼저 올바른 프로그램을 정의한 뒤, 이를 실행하여 어떤 출력 수열을 만든다.

정의:

프로그램은 비어 있지 않은 문장들의 나열이다.
문장은 "PRINT $$c$$ "( $$c$$ 는 정수) 형태이거나, "REP $$o$$ " 뒤에 프로그램이 오고 그 뒤에 "END"가 오는 형태이다. 여기서 $$o$$ 는 1 이상의 정수이다.

실행:

프로그램을 실행하면 그 문장들이 차례로 실행된다.
"PRINT $$c$$ " 문장을 실행하면 출력 수열에 $$c$$ 가 추가된다.
"REP $$o$$ "로 시작하는 문장을 실행하면 내부 프로그램이 총 $$o$$ 번 차례로 실행된다.

베시가 작성할 줄 아는 프로그램의 예는 다음과 같다.

REP 3
    PRINT 1
    REP 2
        PRINT 2
    END
END

이 프로그램은 수열 $$[1,2,2,1,2,2,1,2,2]$$ 를 출력한다.

베시는 양의 정수 $$N$$ 개( $1 \le N \le 100$ )로 이루어진 수열을 출력하고 싶다. 엘시는 베시에게 "PRINT" 문장을 $$K$$ 개( $1 \le K \le 3$ ) 이하로만 사용하라고 도전한다. 베시는 "REP" 문장은 원하는 만큼 사용할 수 있다는 점에 유의하라. 또한 수열의 각 양의 정수는 $$K$$ 를 넘지 않는다는 점에도 유의하라.

$$T$$ 개( $1 \le T \le 100$ )의 독립적인 테스트 케이스 각각에 대해, 베시가 "PRINT" 문장을 최대 $$K$$ 개 사용하여 주어진 수열을 출력하는 프로그램을 작성할 수 있는지 판별하시오.

Problem credits: Alex Liang

제약

배점

입력 3: $$K=1$$
입력 4-7: $K \le 2$
입력 8-13: 추가 제약이 없다.

Problem credits: Alex Liang

입력 형식

첫째 줄에 $$T$$ 가 주어진다.

각 테스트 케이스의 첫째 줄에 공백으로 구분된 두 정수 $$N$$ 과 $$K$$ 가 주어진다.

각 테스트 케이스의 둘째 줄에 베시가 만들고 싶은 수열인, 각각 $$K$$ 이하인 공백으로 구분된 양의 정수 $$N$$ 개가 주어진다.

출력 형식

각 테스트 케이스마다 "YES" 또는 "NO"(대소문자 구분)를 별도의 줄에 출력한다.

예제 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

문제 정보

riseoj 작성

출처 올림피아드 > USACO > 2024-2025 > February > Bronze

올림피아드 > USACO > 2024-2025 > February > Bronze

태그

JudgeUSACO

수열 출력하기

평가 및 의견

풀이 제출