#1052. 「USACO 2012 Open Silver」Running Laps

内存限制
512 MiB
时间限制
2000 ms
文件输入输出
running.in ≫ running.out
题目类型
传统
评测方式
文本比较
上传者 admin
题目来源 usaco

显示标签

题目描述

农夫约翰让他的 n (1 <= n <= 100,000) 头牛在长度为 c 的跑道上进行跑 l 圈的比赛,所有牛从同一起点,以不同的速度开始跑。直到当跑得最快的那一头牛跑完 l 圈时,所有牛才同时停下。

约翰发现在跑圈过程中发生了几次“超越事件”。其定义是:在比赛结束前某时刻,奶牛 x 已经超越了奶牛 y 整整一圈,则称做一次“超越事件”。(注: 至少一圈 ,超越了1/2圈,或者超越了1/4圈等等都不算。且对于同一对奶牛(x,y)不会重复计算次数。)

约翰想知道比赛过程中发生了多少次“超越事件”。

(注:可能原文章表达有误或某些其他原因,各种翻译方式过来的题意都有问题,给人误导很大,这里是根据题目数据和样例解释写的正确的题意,而不是原文)

输入格式 running.in

第一行:三个整数:n,l,c(1 <= l,c <= 25,000)

第二行到第 n+1 行:每行一个整数 vi ,表示奶牛i的速度(1 <= vi <= 1,000,000)

输出格式 running.out

第一行:一个整数,表示总共发生的“超越事件”的次数

样例

输入 #1

4 2 100 
20 
100 
70 
1

输出 #1

4