TopCoder SRM 450 Div1 Medium StrongEconomy

問題

ターン制のゲームがある。
最初n個の工場とk人の職人がいて、毎ターンの最初にn*kのお金が入る。
priceのお金でターン終了時に工場を1つ建てるまたは職人を一人雇うことができる。
これはお金がある限り1ターンに何回でも行える。

targetのお金を稼ぐのにかかる最小ターン数を求めよ。

制約条件

n,k,price,target≦10^12

方針

シミュレーション。
1回ごとに、その状態でtargetまでのお金を稼ぐのにかかるターンを計算してそこからの最適解を求め、priceまでのお金を稼ぐのにかかるターンを計算して、
そこまでターンを進める。

priceのお金を稼いだら、工場と職人のうち、少ないほうを増やせばよい。
これを適当な回数（100万回くらい）繰り返せば最適解が求まる。

ソースコード

class StrongEconomy {
	public:
	long long earn(long long n, long long k, long long price, long long target) 
	{
		ll ans=1ll<<60, turn=0, money=0;
		rep(it,1000000){
			if(n*0.9*k>target){
				ans=min(ans,turn+1);
				break;
			}
			else{
				ll t=max(1ll,(target-money+n*k-1)/(n*k));
				ans=min(ans,turn+t);
			}
			ll t=(price-money+n*k-1)/(n*k);
			money+=t*n*k;
			ll d=money/price;
			if(abs(n-k)>d){
				if(n<k)n+=d;
				else k+=d;
			}
			else{
				int mod=(n+k+d)%2;
				n=(n+k+d)/2;
				k=n+mod;
			}
			money-=d*price;
			turn+=t;
		}
		return ans;
	}
};