레이팅 미적용경마에 싫증이 난 농부 존(Farmer John)은 스포츠로서의 소 경주의 가능성을 알아보기로 했다. 존은 N마리 (1 <= N <= 100,000)의 소들이 길이 C의 원형 트랙을 L바퀴 도는 경주를 준비했다. 소들은 모두 트랙의 같은 지점에서 출발하여 서로 다른 속도로 달리며, 가장 빠른 소가 총 거리 LC를 달리면 경주가 끝난다.
FJ는 한 소가 다른 소를 추월하는 일이 여러 번 일어나는 것을 보고, 경주 전체 동안 이런 "추월 사건"이 몇 번 일어나는지 궁금해한다. 더 구체적으로, 추월 사건은 소 쌍 (x,y)와 시각 t (경주 종료 시각 이하)로 정의되며, 시각 t에 소 x가 소 y를 앞질러 지나가는 것이다. 경주 전체 동안 일어나는 추월 사건의 총 횟수를 세는 것을 FJ에게 도와주자.
첫째 줄: 공백으로 구분된 세 정수 N, L, C. (1 <= L,C <= 25,000).
둘째 줄부터 1+N번째 줄까지: i+1번째 줄에 소 i의 속도가 주어지며, 이는 1..1,000,000 범위의 정수이다.
경주 전체 동안 일어나는 추월 사건의 총 횟수.
running.in · 출력을 쓸 파일 running.out4 2 100
20
100
70
14Input details: There are 4 cows running 2 laps on a circular track of length 100. The speeds of the cows are 20, 100, 70, and 1.
Output details: The race lasts 2 units of time. Within that time, there are 4 crossing events: cow 2 overtakes cows 1 and 4, and cow 3 overtakes cows 1 and 4.
riseoj 작성
출처 올림피아드 > USACO > 2011-2012 > US Open > Silver