좌표 평면에 자연수 좌표를 갖는 점 하나로 구성된 집합 S가 주어진다.

S에 속하는 점으로부터 아래의 세 가지 생성규칙 중 하나를 적용하여 새로운 점을 만들고, 그 점을 집합 S에 추가한다.

이 과정을 반복적으로 수행하면, 매번 새로운 점을 집합 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에 추가한다.

예를 들어, S=\{(3,5)\}일 때, 규칙 1을 점 (3,5)에 적용하여 만들어진 점 (4,6)을 S에 추가하면, S=\{(3,5),(4,6)\}이 된다.

다시 점 (4,6)에 규칙 1을 적용하면, S=\{(3,5),(4,6),(5,7)\}이 된다. 다음에 점 (4,6)에 규칙 2를 적용하면 S=\{(3,5),(4,6),(5,7),(2,3)\}이 된다.

또 두 점 (3,5)와 (5,7)에 규칙 3을 적용하면, S=\{(3,5),(4,6),(5,7),(2,3),(3,7)\}이 된다.

문제는 집합 S를 구성하는 점 (a,b)가 주어질 때,

이 집합에 위의 세 가지 규칙을 임의의 순서로 반복 적용하여 새로운 점 (p,q)가 S에 추가될 수 있는지를 판명하는 것이다.

점 timer 1초 memory 64MB

점 1초 64MB