시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 28 | 5 | 5 | 26.316% |
창영이는 꿈 속에서 문제를 푼다. 오늘 창영이는 좌표평면을 걸어다니는 꿈을 꾸었다. 창영이는 현재 시작점 (0,0)에 있고, 도착점 (A,B)로 이동하려고 한다. 또한, 창영이는 정수 좌표 위에만 서있고, 크기는 매우 작아서 무시할 수 있다.
한 번 이동할 때, 현재 점에서 인접한 4개의 점(위, 아래, 왼쪽 오른쪽)으로 이동할 수 있다. 예를 들어, (x,y)에서 위로 이동하는 것은 (x, y+1)로 이동하는 것이고, 왼쪽으로 이동하는 것은 (x-1, y)로 이동하는 것이다.
창영이가 (x,y)에 있다면, 끝 점과의 거리를 다음과 같이 구할 수 있다.
d((x, y), (A, B)) = abs(x-A) + abs(y-B)
창영이는 시작점에서 도착점으로 이동하던 중에 꿈에서 깼고, 꿈에서 이동한 방법을 모두 적어놓았다.
이제 이동한 방법에서 연속된 일부를 지워 다음과 같은 2가지 조건을 만족하게 하려고 한다.
1. 도착점과 창영이가 마지막으로 도착한 점 사이의 거리는 최소가 되어야 한다.
2. 창영이는 원 점과 도착점을 꼭짓점으로하는 축에 평행한 직사각형을 벗어나면 안 된다.
창영이가 꿈에서 이동한 방법이 주어졌을 때, 연속된 일부를 지워서 문제의 2개 조건을 만족하게 하는 프로그램을 작성하시오.
첫째 줄에 도착점의 좌표 A와 B가 주어진다. (1 ≤ A, B ≤ 4000)
둘째 줄에는 창영이가 이동한 방법의 수 N이 주어진다. (1 ≤ N ≤ 8000)
셋째 줄에는 창영이가 이동한 방법이 순서대로 주어진다. 오른쪽은 R, 왼쪽은 L, 위는 U, 아래는 D이다.
적어도 하나를 지워야 문제의 조건을 만족하는 입력만 주어진다.
첫째 줄에 K와 L을 공백으로 구분하여 출력한다. (1 ≤ K ≤ L ≤ N) K와 L은 입력으로 주어진 이동 방법 중 K번째부터 L번째까지를 지워야 한다는 뜻이다.
2 3 5 RURRR
3 4
Olympiad > Croatian Highschool Competitions in Informatics > 2003 > Croatian Olympiad in Informatics 1번