TCO Round1A 500 TheFrog

2013-02-24

10:54 |

数直線上で常に +x だけジャンプして進めるカエルが 0 にいて、(L[i], R[i]) の穴に落ちずに D 以上のとこまで進みたい。x の最小値を求める。
1≦D≦30,000, 1≦L,Rの要素数≦50, 0≦L[i]≦D-1, L[i]+1≦R[i]≦D, 穴は重複しない

二分探索→だめ（サンプルにあってよかった）
最小の x ということは、必ず R[i] のどれかを通るはず
各 R[i] について、 R[i] まで R[i]歩で来る場合、R[i]-1歩で来る場合、... 2歩で来る場合、1 歩で来る場合それぞれについて穴に落ちずに行けるかを調査する
調査するとこを naive に書いて提出
50*30000*30000*50 になるからだめだ
穴に落ちないかどうかは穴の手前の地点を見つけてそこから一歩行った所が穴じゃなければいいというふうに書き換え。50*30000*50 になったので提出

wrong answer
double の誤差死

↓あとで整数比較に直した版(accepted in practice room)

class TheFrog {
	public:
	double getMinimum(int D, vector <int> L, vector <int> R) {
		double ans = D*2;
		REP(i, L.size()) { //50
			for(ll div=R[i];div>=1;div--) {//30000
				double mid=(double)R[i]/div; // mid は二分探索のなごり
				int ok=1;
				REP(j, L.size()) {
					// EPS つけたらこっちもOKだった
					//double p0 = floor(L[j]/mid+1e-9)*mid;
					//if(p0 + mid < R[j]-1e-9) {ok=0;break;}
					
					ll lp1 = (L[j]*div/R[i]+1) * R[i];
					if(lp1<R[j]*div) {ok=0;break;}
				}
				if(ok) {
					ans=min(ans, mid);
					break;
				}
			}
		}
		return ans;
	}
};