NC15333. Formula One
描述
Formula One (also Formula 1 or F1) is the highest class of single-seater auto racing sanctioned by the F ́ed ́eration Internationale de l’Automobile (FIA) and owned by the Formula One Group.
Sherlock is an avid fan of this Championship. One day, he watched FORMULA 1 2018 HEINEKEN CHINESE GRAND PRIX on the spot. Because the most exciting thing for his nerves was overtaking, he wanted to count the total number of overtaking events in this prix.
But this problem is a little complex, we simplify it to the rectangular coordinate system. There is a circular runway with a center point of (0, 0) and a radius of R. Before the competition started, there are N cars that stop at (0, R). The time requirs for the ith car to finish a circle is Ai seconds. At the 0th second, all cars are started at the same time. In the process of driving, the speed of all cars remains unchanged, and at the Pth second, all cars stop at the same time.
Sherlock needs to count the total number of overtaking events in the 0th second to Pth second process. Since he is too busy, he needs to ask you to help him.
输入描述
The first line contains an integer T, where T is the number of test cases. T test cases follow.
For each test case, the first line contains three integers N, P and R, where N is the number of cars, P is the time that all cars stop, and R is the radius of the runway.The second line contains N integers A1, A2, ... , AN, where Ai is the required time to finish a circle of the i-th car.• 1 ≤ T ≤ 103.
• 2 ≤ N ≤ 102.• 1≤P,R≤108.• 1≤Ai ≤104.
输出描述
For each test case, print one line containing “Case #x: y”, where x is the test case number (starting from1) and y is the total number of overtaking events in the 0th second to Pth second process.
示例1
输入:
2 2 10 2 1 2 3 37 4 3 5 7
输出:
Case #1: 4 Case #2: 13
C++11(clang++ 3.9) 解法, 执行用时: 76ms, 内存消耗: 768K, 提交时间: 2018-04-01 22:34:36
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll A[110];
int main(){
int t;ll n,p,r,cas=1;
scanf("%d",&t);
while(t--){
scanf("%lld%lld%lld",&n,&p,&r);
for(int i=1;i<=n;i++) scanf("%lld",&A[i]);
sort(A+1,A+n+1);
ll ans=0;
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++){
ll tmp1=p*(A[j]-A[i]);
ll tmp2=A[i]*A[j];
if(tmp1==0) continue;
ans+=(tmp1/tmp2);
if(tmp1%tmp2==0) ans--;
}
printf("Case #%d: %lld\n",cas++,ans);
}
return 0;
}
C(clang 3.9) 解法, 执行用时: 130ms, 内存消耗: 376K, 提交时间: 2019-03-04 17:57:55
#include <stdio.h>
#include <math.h>
main(void)
{int t;
scanf("%d",&t);
for(int z=1;z<=t;z++)
{long long n,p,r;scanf("%lld%lld%lld",&n,&p,&r);
long long a[1000];
for(int i=1;i<=n;i++)
{scanf("%lld",&a[i]);}
long long sum=0;
for(int i=1;i<=n-1;i++)
for(int j=i+1;j<=n;j++)
{sum+=abs((p*a[i]-p*a[j])/(a[i]*a[j]));
if((p%a[i])*a[j]==(p%a[j])*a[i] && a[i]!=a[j]) sum--;
}
printf("Case #%d: %lld",z,sum);
if (z!=t) printf("\n");
}
}