점 > 문제은행

본문 바로가기


실전대비 Level4

1330 : 점

제한시간: 1000 ms    메모리제한: 64 MB
해결횟수: 40 회    시도횟수: 194 회   



좌표 평면에 자연수 좌표를 갖는 점 하나로 구성된 집합 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에 추가될 수 있는지를 판명하는 것이다.


첫째 줄에는 처음에 S에 속하는 (a,b)점의 좌표인 두 자연수 a와 b가 하나의 공백을 두고 순서대로 주어진다. 그리고 그 다음 다섯 줄에는 각 줄마다 한 개의 점 (p,q)의 두 자연수 p와 q가 하나의 공백을 두고 순서대로 주어진다. 입력되는 모든 점의 좌표는 1 이상 100,000 이하의 자연수이다.


출력 파일의 첫째 줄에는 입력 파일에 제시된 다섯 개의 점에 대하여 각 점이 세 개의 규칙을 반복 적용하여 만들어질 수 있는지의 여부를 출력한다. 가능하면 Y를 불가능하면 N을 한 줄에 하나씩 순서대로 출력한다.

[Copy]
3 5 
4 6 
2 3 
1 1 
2 5
4 7
[Copy]
Y 
Y 
N 
Y 
Y





HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.