kmjp's blog

競技プログラミング参加記です

Google Code Jam 2017 Round 1B : A. Steed 2 : Cruise Control

1Aよりは簡単だったみたいね。
https://code.google.com/codejam/contest/8294486/dashboard

問題

距離Dの間をバスで進みたい。
途中、いくつかの馬がいくつかの場所におり、それぞれ決まった速度で前方に移動している。
なお、馬が別の馬に追いついた場合、両者は以後遅い方の同じ速度で移動する。

バスを一定速度で動かすとき、到着地までに他の馬に追いつかないようにするには最大でどの速度で移動すればよいか。

解法

ゴールに一番遅く馬と同着でつくようにすればよい。

int D,N;

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	
	cin>>D>>N;
	double ma=0;
	FOR(i,N) {
		cin>>x>>y;
		ma=max(ma,(D-x)*1.0/y);
	}
	
	_P("Case #%d: %.12lf\n",_loop,D/ma);
}

まとめ

これはあっさり。