파일 업로드

RC카 경주

profile
실행 시간 제한메모리 제한
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 입니다.

🖨️ 출력

전체 경주 시간동안 교차 사건의 총 횟수를 출력해주세요.


💻 예제 입력 1
4 2 100
20
100
70
1
🖨️ 예제 출력 1
4

출처: USACO 2012 US Open, Silver Division Problem 3. Running Laps