Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2110-827d685f
この記事にトラックバックする(FC2ブログユーザー)

Beta Round #73 DIV1 A問題/DIV2 C問題 - Trains (この記事を編集する[管理者用])

Source

Codeforces Beta Round #73 DIV1 A問題 (500pt)
Codeforces Beta Round #73 DIV2 C問題 (1500pt)
Problem description

問題概要

a秒ごとに来る列車と,b秒ごとに来る列車がある.
時間0では同時にくる.
自分は,ランダムなときに駅について,先に来た方に乗る.
次の列車が同時に到着したら,レアな方に乗る.(aとbの大きい方に対応する列車に乗る)
乗る確率が高い列車はどちらか,もしくは,等しいかを判定する問題.
aとbは1以上10^6以下の整数で,等しくない.

解法

シミュレーションする.
時間gcd(a,b)までシミュレーションすれば後は繰り返しなので,そこまですればいい.
シミュレーションは次の電車が来る時間を計算して,その時間まで飛ばす感じ.
次の電車が来る数は高々a+b回なのでO(a+b)時間となる.

C言語のスパゲッティなコード
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define ll long long

ll GCD(ll a,ll b){ll r; while(a){r=b; b=a; a=r%a;} return b;}
ll LCM(ll a,ll b){return a/GCD(a,b)*b; }

int main(){
  int i,j,k,l,m,n;
  ll a, b;
  ll a_time, b_time, end_time;
  ll a_next, b_next;
  ll now_time;

  while(scanf("%d%d",&i,&j)==2){
    a=i; b=j;

    now_time = 0;
    a_time = b_time = 0;
    end_time = LCM(a,b);

    while(now_time < end_time){
      a_next = now_time / a * a + a;
      b_next = now_time / b * b + b;

      if(a_next == b_next){
        if(a > b) b_next++;
        else      a_next++;
      }

      if(a_next < b_next){
        a_time += a_next - now_time;
        now_time = a_next;
      } else {
        b_time += b_next - now_time;
        now_time = b_next;
      }
    }

    if(a_time==b_time){ puts("Equal"); continue; }
    if(a_time > b_time) puts("Dasha"); else puts("Masha");
  }

  return 0;
}

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2110-827d685f
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。