SRM 490 DIV1 Easy - Starport

SRM 490 DIV1 Easy - Starport

18:34

問題


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;
}

};

Share this

Google Facebook Twitter More

Related Posts