Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

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

Source

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

問題概要

蛇口1からは温度t1の水が出て,単位時間あたり0以上x1以下の整数だけの量の水を出すことができる.
蛇口2からは温度t2の水が出て,単位時間あたり0以上x2以下の整数だけの量の水を出すことができる.
途中で水の量を変更できない.両方の蛇口から出た水は同じ場所に貯められる.
結果的に温度t0以上で可能な最も低い温度の水をいくらか得たい.
最も早く水を得るために,両方の蛇口から出す水の量を求める問題.
t1はt0以下で,t2はt0以上.
x1, x2は10^6以下.

解法

t1, t2がt0に等しい時はコーナーケースになるので特別に処理する.
後は,蛇口1から出す水の量を1以上の整数を全て試す.
あまり変なことをすると多分誤差で死亡するので気をつける.全部整数でやるとか.
自分がやった方法は,蛇口1から出す水の量y1と,蛇口2から出す水の量y2が決まった時,y1とy2がそれぞれx1,x2を超えない範囲で適当に整数倍する.
そもそも,y1とy2が互いに素じゃない場合は,その組み合わせは以前調べたはずで,飛ばす.
とすると,全く同じ温度になるケースは除外できるので,普通に比較していれば誤差死せずに通る.

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

#define ll long long
int GCD(int a,int b){int r; while(a){r=b; b=a; a=r%a;} return b;}

int main(){
  int i,j,k,l,m,n;
  int t1,t2,x1,x2,t0;
  double opt, tmp;
  int r1, r2;
  ll y1, y2, yy1, yy2;

  while(scanf("%d%d%d%d%d",&t1,&t2,&x1,&x2,&t0)==5){
    opt = 1e100;

    if(t1==t0 && t2==t0){
      printf("%d %d\n",x1,x2);
      continue;
    }
    if(t1==t0){
      printf("%d 0\n",x1);
      continue;
    }
    if(t2==t0){
      printf("0 %d\n",x2);
      continue;
    }
    
    y2 = 1;
    REP(y1,0,x1+1){
      while(t1*y1+t2*y2 < t0*(y1+y2)){
        y2++;
        if(y2 > x2) break;
      }
      if(y2 > x2) break;

      k = GCD(y1, y2);
      if(k>1) continue;

      tmp = (t1*y1+t2*y2) / (double)(y1+y2);
      if(opt > tmp){
        opt = tmp;

        k = 1000000000;
        if(y1 && k > x1 / y1) k = x1 / y1;
        if(y2 && k > x2 / y2) k = x2 / y2;

        r1 = y1 * k;
        r2 = y2 * k;
      }
    }

    printf("%d %d\n",r1,r2);
  }

  return 0;
}

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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