Google Code Jam 2014 Qualification Round B問題 - Cookie Clicker Alpha

Source

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$ 枚貯まるまでの時間は,クッキー農場を買う数に対して凸関数なので,クッキー農場を買い足したほうが遅くなれば,その時に計算を打ち切れば良い.

C++によるスパゲッティなソースコード

#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: 2017年11月18日11時30分51秒
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)

ログイン: