Codeforces Round #45 C. The Race

Codeforces 実装問題

問題概要

燃料1リットルで10Km走る車が、ガソリンスタンドが100Kmおきにある道を以下のように走る。

  • そのスタンドで給油しなければ次のスタンドに着けないならαリットル給油する
  • そうでないならそのスタンドには立ち寄らない

αは10以上の実数で、与えられない。
最初に立ち寄るn個のスタンドの番号が与えられるとき、
次に立ちよるスタンドの番号が一意に定まるならuniqueの文字列およびその番号を出力し、そうでないならnot uniqueを出力せよ。

解法

立ち寄るスタンドの配列をd[i]とする。
d[i]番目のスタンドに立ち寄る⇔(i+1)*α/10の整数部分がd[i]
であるため、
スタンドの情報からありうるαの区間を絞り込んでいける。


そこからn+1個目のスタンドが一意に定まるか（すなわち、αが最大値を取ったときのn+1個目のスタンドと、αが最小値を取ったときのスタンドが一致するか）を見ればよい。

ソースコード

void run()
{
	int n,d[1000];
	cin>>n; rep(i,n)cin>>d[i];
	
	double l=-inf,u=inf;
	rep(i,n)
	{
		l=max(l,d[i]/(i+1.0));
		u=min(u,(d[i]+1)/(i+1.0));
	}
	int a=(int)(l*(n+1)),b=(int)(u*(n+1)-EPS);
	if(a==b)printf("unique\n%d\n",a);
	else puts("not unique");
}