ページが読み込まれませんか？ こちらをクリックすると直るかもしれません。
Placeholder

#10367

익스포고 20s 1024MB

問題

당신은 최고의 선물을 받았다: 익스포고(Expogo) 스틱이다. 그 위에 서서 점점 더 큰 점프를 할 수 있다.

당신은 무한한 2차원 뒷마당에서 점 (0, 0)에 서 있고, 정수 좌표를 가진 목표 점 (X, Y)에 가능한 한 적은 점프로 도달하려 한다. 점프 중에 목표 점 위를 지나가는 것만으로는 충분하지 않으며, 목표 점에 정확히 착지해야 한다.

익스포고 스틱으로 점프할 때마다, 당신은 북/남/동/서 중 하나의 방위(기본 방향)를 고른다. 익스포고 스틱으로 하는 i번째 점프는 선택한 방향으로 2(i-1)만큼 이동한다. 즉, 첫 번째 점프는 1만큼, 두 번째 점프는 2만큼, 세 번째 점프는 4만큼... 이런 식으로 계속된다.

목표 점 (X, Y)가 주어질 때, 그곳에 도달하는 것이 가능한지 판별하고, 가능하다면 가능한 한 적은 점프로 도달하는 방법을 제시하라.


入力

입력의 첫 줄에는 테스트 케이스 수 T가 주어진다. T개의 테스트 케이스가 이어진다. 각 테스트 케이스는 목표 점의 좌표를 나타내는 두 정수 X, Y가 주어진 한 줄로 이루어진다.


出力

각 테스트 케이스마다 Case #x: y 형식의 한 줄을 출력하라. 여기서 x는 (1부터 시작하는) 테스트 케이스 번호이고, 목표 점에 도달할 수 없다면 y는 IMPOSSIBLE이어야 한다. 그렇지 않다면 y는 한 글자 이상의 문자열이어야 하며, 각 문자는 북/남/동/서를 뜻하는 N, S, E, W 중 하나이다. 이는 순서대로 수행할 점프 방향을 나타낸다. 이 점프 수열은 마지막 점프가 끝났을 때 목표 점에 도달해야 하며, 길이가 가능한 한 짧아야 한다.


例題 

4
2 3
-2 -3
3 0
-1 1
Case #1: SEN
Case #2: NWS
Case #3: EE
Case #4: IMPOSSIBLE
샘플 케이스 #1에서는 (0, 0)에서 남쪽으로 (0, -1)로 점프한 뒤 동쪽으로 (2, -1), 그 다음 북쪽으로 (2, 3)으로 점프할 수 있다. 두 번 이하의 이동으로 더 효율적인 해가 없음을 알 수 있다. 목표 지점까지 최소 2 + 3 = 5만큼의 거리가 필요하지만 처음 두 번의 점프가 만들어 내는 거리는 합쳐 3뿐이기 때문이다. 샘플 케이스 #2는 샘플 케이스 #1을 두 축에 대해 반사한 것이므로, 답도 샘플 케이스 #1의 방향을 모두 반사하면 된다. 샘플 케이스 #3에서 EWE는 목표에 도달하더라도 유효한 답이 아니다. 더 적은 점프로 도달하는 방법이 있기 때문이다. 샘플 케이스 #4에서 목표에 도달할 수 없는 이유는 독자에게 맡긴다.

出典

GCJ 2020r1b A

ログインしないとコードを書けません。