Google Code Jam 2014 Qualification Round B問題
Problem Statement
最初クッキーを $0$ 枚持っていて,毎秒 $2$ 枚(つまり,$0.5$ 秒に $1$ 枚)のペースでクッキーが手に入る.
クッキーを $C$ 枚支払うことで,クッキー農場を $1$ つ手に入れることができ,$1$ 秒辺り追加で $F$ 枚のクッキーが手に入る.
クッキー農場はいくらでも手に入れることができる.
最終的に,$X$ 枚のクッキーを手に入れるための最小時間を求める問題.
合計で,1秒辺りに $z$ 枚のクッキーが手に入る状況なら,$1/z$ 秒ごとに $1$ 枚のクッキーが手に入ると考える.
クッキー農場を買うなら,買えるだけのクッキーが貯まったらすぐ買うのが良い.
クッキー農場を1個ずつ買っていくのをシミュレーションする.
その際,買った時,これ以上買わなかった時に,$X$ 枚貯まるまでの時間をついでに計算していって,最小値を探す.
$X$ 枚貯まるまでの時間は,クッキー農場を買う数に対して凸関数なので,クッキー農場を買い足したほうが遅くなれば,その時に計算を打ち切れば良い.
#include<cstdio>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<algorithm>
#include<string>
#include<utility>
#include<iostream>
#include<cmath>
using namespace std;
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
int main(){
int T, cnt = 0;
double C, F, X;
int i, j, k;
double res, tmp, speed, elapsed;
scanf("%d",&T);
while(T--){
scanf("%lf%lf%lf",&C,&F,&X);
res = X / 2;
speed = 2;
elapsed = 0;
for(;;){
elapsed += C / speed;
speed += F;
tmp = X / speed + elapsed;
if(tmp > res) break;
res = tmp;
}
printf("Case #%d: %.9f\n",++cnt,res);
}
return 0;
}
Current time: 2024年03月28日23時15分15秒
Last modified: 2014年04月13日18時13分11秒 (by laycrs)
Tags: Competitive_Programming Google_Code_Jam GCJ_2014 GCJ_2014_Qualification_Round
トップページに戻る
Logged in as: unknown user (not login)