SRM 490 DIV1 Easy - Starport (復習○)
問題
http://community.topcoder.com/stat?c=problem_statement&pm=11227&rd=14243
Ｍ秒間隔でスペースシャトルが到着し、Ｎ秒間隔でテレポートが始まる。
スペースシャトルが到着したときにテレポート間隔とぴったりでなければ、次のテレポート時間まで待つ。
このとき、待ち時間の平均時間を求める。
解き方
数学的に解く問題。
サンプルを元に計算すると、
N=10 M=4 (gcd=2 lcm=20)
M:4 8 12 16 20 24 28 32 36 40 44
N: 10 20 30 40 50 60 70
１サイクルの待ち時間 T=6+2+8+4+0=20となる。
また、要素数はlcm/Mとなることがわかる。
また要素をgcdにて割ると、
M':2 4 6 8 10
N': 5 10
１サイクルの待ち時間はT=gcd*(3+1+4+2+0)
また、0,1,...N'-1のすべての要素が出現することがわかる。
つまり、合計待ち時間T、要素数Kと答えとなるT/Kは以下のように計算できる。
T=gcd*N'*(N'-1)/2
=gcd*(N/gcd)(N/gcd-1)/2
=N(N/gcd-1)/2
K=lcm/M=N/gcd
T/K= (N(N/gcd-1)/2) /(N/gcd)
= (N(N/gcd-1)*gcd) /(N*2)
= gcd*(N/gcd-1) /2
=(N-gcd)/2
コード
class Starport {
public:
int gcd(int a,int b){
if(a<b)swap(a,b);
if(a%b==0)return b;
return gcd(b,a%b);
}
double getExpectedTime(int N, int M) {
return (double)(N-gcd(N,M))/2.0;
}
};
public:
int gcd(int a,int b){
if(a<b)swap(a,b);
if(a%b==0)return b;
return gcd(b,a%b);
}
double getExpectedTime(int N, int M) {
return (double)(N-gcd(N,M))/2.0;
}
};
