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

#10370

과하게 들뜬 팬 20s 1024MB

問題

오늘 드디어 그날이다 — 오늘은 마침내 고양이 페퍼(Peppurr)와 함께 사진을 찍는 날이다!

페퍼가 당신의 도시를 투어한다는 소식이 막 발표되었다. 이 도시는 남북 방향으로 뻗는 무한히 많은(그리고 무한히 긴) 거리들과, 동서 방향으로 뻗는 무한히 많은(그리고 무한히 긴) 거리들로 이루어져 있다. 남북 거리와 동서 거리가 만나는 모든 점이 교차로(intersection)이다. 어떤 교차로에서든 북/동/남/서 네 방향 각각에서 가장 가까운 교차로는 정확히 한 블록 떨어져 있다.

당신은 페퍼의 투어가 이 거리들을 따라 어떤 경로로 진행되는지 정확히 알고 있다. 목표는 페퍼가 있는 시간에 맞춰 페퍼의 투어 경로 위의 어떤 교차로에 도착하는 것이며, 가능한 한 빨리 그렇게 하고 싶다. 그래야 페퍼와 사진을 찍을 수 있다!

페퍼의 투어는 당신이 현재 있는 교차로에서 동쪽으로 X블록, 북쪽으로 Y블록 떨어진 교차로에서 시작한다. 당신과 페퍼는 모두 한 블록을 걷는 데 정확히 1분이 걸리며, 매 분이 끝날 때마다 교차로에 있어야 한다. 둘 다 블록의 일부만 걷는 것은 불가능하다.

페퍼는 미리 정해진 경로대로 움직인다. 당신은 매 분마다 그 분 동안 가만히 있을지, 또는 네 방향(북/동/남/서) 중 하나로 한 블록 걸을지 선택할 수 있다. 당신과 페퍼는 둘 다 오직 거리 위로만 움직인다.

당신과 페퍼가 같은 시간에 같은 교차로에 있다면, 투어의 마지막 교차로에서라도 사진을 찍을 수 있다. 하지만 투어가 끝난 뒤에는 페퍼가 사진 촬영이 불가능하므로, 투어의 마지막 교차로에 투어가 끝난 뒤 1분이라도 늦게 도착하면 사진을 찍지 못한다.

페퍼와 사진을 찍는 것이 가능할까? 가능하다면, 가장 빠른 시각(몇 분 후)에 가능할까?


入力

입력의 첫 줄에는 테스트 케이스 수 T가 주어진다. T개의 테스트 케이스가 이어진다. 각 테스트 케이스는 두 정수 X, Y와 문자열 M이 주어진 한 줄로 이루어진다. 이는 페퍼의 투어 시작점이 당신으로부터 동쪽으로 정확히 X블록, 북쪽으로 정확히 Y블록 떨어져 있음을 의미한다. 문자열 M은 페퍼가 할 이동들의 순서이다. M의 i번째 문자는 N, E, S, W 중 하나이며, 각각 북/동/남/서를 뜻한다. 이는 투어의 i번째 분 동안 페퍼가 그 방향으로 한 블록 걷는다는 뜻이다.


出力

각 테스트 케이스마다 Case #x: y 형식의 한 줄을 출력하라. 여기서 x는 (1부터 시작하는) 테스트 케이스 번호이다. 페퍼와 사진을 찍는 방법이 없다면 y는 IMPOSSIBLE이다. 그렇지 않다면 y는 투어 시작 시점으로부터 몇 분 뒤에 사진을 찍을 수 있는지의 최소값이다.


例題 

5
4 4 SSSS
3 0 SNSS
2 10 NSNNSN
0 1 S
2 7 SSSSSSSS
Case #1: 4
Case #2: IMPOSSIBLE
Case #3: IMPOSSIBLE
Case #4: 1
Case #5: 5
샘플 케이스 #1에서는 동쪽으로 네 블록 이동하면 투어의 마지막 교차로에서 Peppurr와 사진을 찍을 수 있다. 샘플 케이스 #2에서는 투어가 당신의 동쪽으로 정확히 세 블록 떨어진 곳에서 시작한다. 어떻게 움직이든 Peppurr와 사진을 찍을 수 없다. 샘플 케이스 #3에서는 투어가 너무 북쪽에 있어서, 투어가 끝나기 전에 사진을 찍을 수 없다. 샘플 케이스 #4에서는 투어가 1분 후에 당신에게 오므로 움직일 필요조차 없다! Peppurr와 사진을 찍자! 사진은 교차로에서만 찍을 수 있으므로, 당신이 북쪽으로 움직이고 투어가 남쪽으로 움직여 교차로 밖에서 Peppurr와 스쳐 지나가더라도 0.5분 만에 사진을 찍을 수는 없다는 점에 유의하라. 샘플 케이스 #5에서는 북쪽으로 두 번, 그 다음 동쪽으로 두 번 이동할 수 있다. 그 후에는 그대로 있어도 다음 1분 안에 Peppurr와 사진을 찍을 수 있다. 5분 안에 사진을 찍을 수 있는 다른 경로도 있지만, 그보다 더 빨리 찍을 수 있는 경로는 없다. 다음 두 케이스는 테스트 세트 1과 2에는 나오지 않지만, 테스트 세트 3에는 나올 수 있다: 2 3 2 SSSW 4 0 NESW 이 두 케이스의 정답 출력은 다음과 같다: Case #1: 4 Case #2: 4 케이스 #1에서는 시작점에서 남쪽으로 한 칸, 동쪽으로 두 칸 떨어진 곳에서 Peppurr와 사진을 찍을 수 있다. 케이스 #2에서는 Peppurr가 작은 정사각형을 돌며 이동한다. 그 정사각형의 시작점으로 돌아오는 순간에 사진을 찍을 수 있다.

出典

GCJ 2020r1c A

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