kmjp's blog

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

Codeforces #320 Div1 A. A Problem about Polyline

本番だいぶグダグダな出来だと思ったけど、Bが結構落ちてレート変動ほぼなし。
http://codeforces.com/contest/578/problem/A

問題

ある正実数aについて、(0,0)-(x,x)-(2x,0)-(3x,x)-(4x,0)- を順に結んだジグザグの線を考える。
この線群が座標(a,b)を通るような最小のxを求めよ。

解法

b>aの場合は解無し。

それ以外の場合、(a,b)は右上上がりの線上にあるか、右下下がりの線上にあるかどちらかである。
なお、Editorialにあるとおり前者は最小にならないので後者だけ考える。
(a,b)が右下下がりの線上にあるなら、その線は(a+b,0)を通るはずである。

よって、xは(a+b)の整数分の1で、かつbより大きい値である。
なので \frac{a+b}{2*\lfloor (a+b)/2b \rfloor}が解。

ll A,B;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>A>>B;
	if(A<B) return _P("-1\n");
	
	ll AA=A+B;
	int a=AA/(2*B);
	_P("%.12lf\n",AA/(2.0*a));
}

まとめ

ここらへんはまだ簡単。