TopCoder SRM 467 Div1 Easy LateProfessor
問題
Johnは時間0に教室に来て、以下のことを繰り返す。
- waitTimeだけ教授を待つ
- その間に教授が来なかったらwalkTimeだけ散歩に出かける。
教授はbestArrival以上worstArrival以下のランダムな実数の時間に教室に来る。
教授は、lateTime以上遅刻した生徒を教室に入れない。
Johnが教室に入れない確率を求めよ。
制約条件
waitTime, walkTime, bestArrival, worstArrival≦10^7
方針
遅刻とされる区間の長さを教授の来る区間の長さで割ったものが答え。
bestArrivalとworstArrivalが同一の場合はコーナーで、別に処理する必要がある。
境界を含むのか、そうでないのかが解りにくい。。。
ソースコード
int is(int a,int b,int c,int d){ return max(min(b,d)-max(a,c),0); } class LateProfessor { public: double getProbability(int wa, int wl, int l, int b, int w) { int T=wa+wl, p=(b+T-1)/T, q=w/T; if(b==w){ return wa<b%T&&b%T<=T-l?1:0; } double ans=max(0,wl-l)*(q-p); ans+=is(wa,wa+wl-l,b%T?b%T:T,T)+is(wa,wa+wl-l,0,w%T); return ans*1.0/(w-b); } };