원문 PDF 의 글을 화면용으로 옮겼습니다. 내용이 다르면 원문이 맞습니다. (검수일 2026-11-20)
곡예
원제: 곡예
문제
개의 칸이 일렬로 나열된 평균대 위에서 두 곡예사 Alice와 Bob이 공연을 진행하려고 한다. 평균대의 칸에는 왼쪽부터 오른쪽으로 번부터 번까지의 번호가 붙어 있다.
공연을 진행하며 두 곡예사는 매 순간 정확히 하나의 칸 위에 서 있어야 한다. 또한 안전을 위해 공연 중 모든 순간에 대해 Alice가 서 있는 칸의 번호가 Bob이 서 있는 칸의 번호보다 작아야 한다. 즉, Alice는 항상 Bob보다 왼쪽 칸에 서 있어야 하며, 두 곡예사는 같은 칸에 서 있을 수 없다.
평균대에는 개의 점프대가 설치되어 있다. 번 점프대는 번 칸에 설치되어 있으며, 번 칸에 서 있는 곡예사가 이 점프대를 이용하면 번 칸에 정확히 착지한다.
한 칸에 여러 개의 점프대가 설치되어 있을 수도 있으며, 두 곡예사 모두 모든 점프대를 횟수 제한 없이 이용할 수 있다.
공연은 번 이상의 행동을 차례로 수행하는 것으로 이루어진다. 한 번의 행동에서는 두 곡예사 중 정확히 한 명이 다음 두 가지 중 하나를 수행한다.
- 걷기: Alice는 자신이 서 있는 칸에서 오른쪽으로 한 칸 이동할 수 있고, Bob은 자신이 서 있는 칸에서 왼쪽으로 한 칸 이동할 수 있다. Alice가 왼쪽으로는 걸을 수 없으며, Bob도 오른쪽으로 걸을 수 없다.
- 점프: 자신이 서 있는 칸에 설치된 점프대 중 하나를 골라 점프한다. 즉, 어떤 정수 에 대해 번 칸에 서 있는 곡예사는 번 점프대를 이용해 번 칸으로 착지할 수 있다.
행동을 수행한 직후에도 Alice는 Bob보다 왼쪽 칸에 서 있어야 하며, 조건을 위반하게 되는 행동은 수행할 수 없다.
두 곡예사는 개의 공연 계획을 가지고 있다. 번째 공연 계획은 과 을 만족하는 네 정수 , , , 로 나타낼 수 있다. 만약 적절한 행동들을 통해 Alice가 번 칸, Bob이 번 칸에 서 있는 상태로 공연을 시작하여, Alice가 번 칸, Bob이 번 칸에 서 있는 상태로 공연을 마치는 것이 가능하다면, 번째 공연 계획은 유효하다.
개의 공연 계획에 대해서 각 계획이 유효한지 판정하라.
제약 조건
- 주어지는 모든 수는 정수이다.
- 정수 에 대하여, 과 를 만족한다.
- 정수 에 대하여, 과 을 만족한다.
부분문제
- (8점)
- (14점) 정수 에 대하여
- (13점)
- (13점)
- (52점) 추가 제약 조건 없음.
입력 형식
첫 줄에 두 정수 과 이 공백으로 구분되어 차례대로 주어진다.
그다음 개의 줄에 걸쳐, 개의 점프대에 대한 정보가 주어진다. 이 중 번째 줄에는 번째 점프대를 나타내는 두 정수 와 가 공백으로 구분되어 차례대로 주어진다.
그다음 줄에 공연 계획의 개수를 나타내는 정수 가 주어진다.
그다음 개의 줄에 걸쳐, 개의 공연 계획에 대한 정보가 주어진다. 이 중 번째 줄에는 번째 공연 계획을 나타내는 네 정수 , , , 가 공백으로 구분되어 차례대로 주어진다.
출력 형식
첫 줄부터 개의 줄에 걸쳐, 답을 출력한다. 이 중 번째 줄에는 번째 공연 계획에 대한 답을 출력한다. 만약 Alice가 번 칸, Bob이 번 칸에 서 있는 상태로 공연을 시작하여, Alice가 번 칸, Bob이 번 칸에 서 있는 상태로 공연을 마칠 수 있으면 YES를, 그렇지 않으면 NO를 출력한다.
예제
예제 1
6 2 3 5 4 2 4 2 4 3 4 2 3 2 5 2 3 4 5 3 4 1 2
YES YES YES NO
두 번째 공연 계획에서 Alice는 번 칸, Bob은 번 칸에서 공연을 시작한다. Bob이 번 칸의 점프대를 이용해 번 칸으로 이동하면 Alice가 번 칸, Bob이 번 칸에 서 있게 되어 목표에 도달한다.
네 번째 공연 계획에서 Alice가 번 칸, Bob이 번 칸에 서 있을 때는 어떤 행동도 할 수 없다.
- Alice가 오른쪽으로 걸으면 두 곡예사가 모두 번 칸에 서게 되어 조건을 위반한다.
- Bob이 왼쪽으로 걸으면 두 곡예사가 모두 번 칸에 서게 되어 조건을 위반한다.
- Bob이 번 칸의 점프대를 이용해 번 칸에 착지하면, Bob이 번 칸에 서 있는 Alice보다 왼쪽에 서게 되어 조건을 위반한다.
따라서, Alice가 번 칸, Bob이 번 칸에 서게 되는 목표 상태에 도달할 수 없다.
예제 2
10 3 5 10 6 8 7 4 5 5 6 4 10 5 6 3 9 1 10 2 9 6 8 4 9 9 10 1 10
YES NO YES YES NO