시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 140 | 53 | 40 | 34.783% |
스톡홀롬 지하철은 여러 개의 노선으로 이루어져 있다. 이 문제는 노선이 하나 있고, 자주 발생하는 문제인 신호 장애에 대해서 다룬다.
지하철 노선은 양 끝점을 연결하는 평행한 두 레일로 생각할 수 있다. 위쪽 레일에서 열차는 오른쪽에서 왼쪽으로 이동하며, 아래쪽 레일에서는 왼쪽에서 오른쪽으로 이동한다. 열차가 끝 점에 도착했을 때는, 반대편 레일로 이동한 다음, 방향을 바꿔서 다시 진행한다. 이렇게 방향을 바꾸고 반대편 레일로 이동하는데 걸리는 시간은 없다.
평소에 교통 흐름은 연속적이고, 열차는 항상 일정한 속도로 이동한다. (1분에 1칸) 열차는 균등하게 분포되어 있다. 따라서, 레일의 한 점을 지나가는 열차는 주기적이다. 열차가 역에 정차하고, 승객을 태우는데 걸리는 시간은 무시한다.
신호 장애가 발생했을 때, 열차는 레일 위에 랜덤하게 분포된다. 이 경우에 지하철 관제 센터에서는 열차를 재빠르게 균등하게 분포해야 한다. 각 열차의 현재 위치가 주어졌을 때, 얼마나 빠르게 균등하게 분포할 수 있는 지 구하는 프로그램을 작성하시오. 관제 센터에서는 열차를 잠시 멈추게 할 수도 있고, 방향을 반대로 바꿀 수도 있다. 방향을 바꾸는 경우에 열차는 반대편 라인으로 이동하게 된다.
위의 그림은 길이가 100인 레일을 나타낸다. 위쪽 그림에 열차는 5(오른쪽), 35(왼쪽), 46(왼쪽), 75(왼쪽), 85(오른쪽)에 있다. 열차를 균등하게 배치하는 한 가지 방법은 46에 있는 열차를 한 칸 움직이게 하고, 방향을 반대로 바꾸는 것이다. 하지만, 이 방법은 가장 빠른 방법은 아니다.
첫째 줄에 레일의 길이 m, 열차의 수 n이 주어진다. 다음 n개 줄에는 열차의 현재 위치가 주어진다. 열차의 위치 xi와 함께 방향이 주어지며, L인 경우는 왼쪽, R인 경우는 오른쪽으로 열차가 향하는 것이다.
열차를 균등하게 배치하는데 필요한 가장 빠른 시간을 출력한다. 소수점 오차는 10-6까지 허용한다.
100 5 5 R 35 L 46 L 75 L 85 R
0.5
100 8 9 L 15 R 41 L 33 L 81 R 33 R 100 L 97 R
15.500000