실행 시간 제한 | 메모리 제한 |
---|---|
1 초 | 128 MB |
진우는 자신의 N대의 RC카들 (1 <= N <= 100,000)을 C 길이의 원형 트랙에서 L 랩의 경주를 하게 합니다. 모든 차들은 트랙의 동일한 지점에서 출발하여 다른 속도로 달리며, 가장 빠른 차가 총 거리 LC를 달렸을 때 경주가 끝납니다.
진우는 경주 중에 한 대의 차가 다른 차를 추월하는 여러 사건을 발견하고, 이러한 "교차 이벤트"가 경주 동안 얼마나 많이 발생하는지 궁금해합니다.
즉, 교차 이벤트는 한 쌍의 차 (x,y)와 시간 t (경주 종료 시간 이하)로 정의되며, 시간 t에 차 x가 차 y 앞에서 교차합니다. 경주 동안 발생한 전체 교차 이벤트 수를 계산해 주세요.
1번째 줄 : N, L, C. (1 <= L,C <= 25,000).
2번째 줄..1+N번째 줄 : i+1번째 줄에는 i번째 차의 속도가 포함되어 있으며, 범위는 1..1,000,000 입니다.
전체 경주 시간동안 교차 사건의 총 횟수를 출력해주세요.
4 2 100 20 100 70 1
4
출처: USACO 2012 US Open, Silver Division Problem 3. Running Laps