점
시간 제한1초메모리 제한128 MB
이동, 짝수일 때 반으로 줄이기, 전이 규칙으로 생성되는 점 집합에서 주어진 점들이 도달 가능한지 판별하는 문제입니다.
문제
좌표 평면 위의 자연수 좌표를 갖는 점들의 집합 S가 있다. 처음에 S에는 점 (a, b) 하나만 들어 있다. 아래 세 가지 규칙 중 하나를 원하는 순서로 반복 적용하여 새로 만들어진 점을 S에 추가할 수 있다.
- 규칙 1:
(x, y)가S에 있으면(x + 1, y + 1)을S에 추가한다. - 규칙 2:
(x, y)가S에 있고x와y가 모두 짝수이면(x / 2, y / 2)를S에 추가한다. - 규칙 3:
(x, y)와(y, z)가 모두S에 있으면(x, z)를S에 추가한다.
처음 주어진 점 (a, b)에서 시작해 위 규칙들을 반복 적용했을 때, 각 질의 점 (p, q)를 S에 추가할 수 있는지 판정하라.
입력
첫째 줄에 처음 S에 들어 있는 점의 좌표인 두 자연수 a와 b가 공백으로 구분되어 주어진다.
다음 다섯 줄에는 각 줄마다 질의 점의 좌표인 두 자연수 p와 q가 공백으로 구분되어 주어진다.
입력되는 모든 좌표는 1 이상 100,000 이하의 자연수이다.
출력
다섯 개의 질의 점 각각에 대해, 세 규칙을 반복 적용하여 만들 수 있는지 출력한다.
만들 수 있으면 Y, 만들 수 없으면 N을 입력 순서대로 한 줄에 하나씩 출력한다.