// Solution to Speed Skills // If this actually works I'll be amazed! // import java.util.*; class Car { // all cars except Anna's public int carnum; // number of the car public int l; // initial location of car public int s; // speed of car public Car(int c, int l, int s) { carnum = c; this.l = l; this.s = s; } } public class G { public static Scanner in; public static int casenum; public static double l; // we will need to deal with fractional locations public static int s,d,n; public static int[] ll; public static int[] ss; public static HashSet behind, ahead, passing; public static double t; public static final double EPS = 1E-8; public static void main(String[] args) { in = new Scanner(System.in); casenum = 0; while (true) { l = in.nextInt(); s = in.nextInt(); d = in.nextInt(); n = in.nextInt(); if (l == 0 && s == 0 && d == 0 && n == 0) break; casenum++; ll = new int[n]; ss = new int[n]; for (int i = 0; i < n; i++) { ll[i] = in.nextInt(); ss[i] = in.nextInt(); } solve(); System.out.printf("Case %d: Anna reaches her destination at time %.4f" + " at a speed of %d\n",casenum,t,s); } } public static void solve() { // Initial set up--see if anyone is passing Anna at time t=0. This // is equivalent to finding all cars at Anna's starting loc or at most // one car length behind: // First, distribute cars into those behind, passing, and ahead of Anna: behind = new HashSet(); passing = new HashSet(); ahead = new HashSet(); for (int i = 0; i < n; i++) { Car c = new Car(i,ll[i],ss[i]); if (ll[i] < l-1) { behind.add(c); } else if (ll[i] > l) { ahead.add(c); } else { passing.add(c); } } // Adjust Anna's time for any cars passing her when gizmo is turned on: int count = 1; // number in average int news = s; // sum of values to be averaged for (Car c: passing) { count++; news += c.s; } int prevs = s; // When Anna's speed stops changing, we can skip ahead... s = news/count; //status("Init"); boolean lastpass = false; // needed to update Anna's final speed t = 0; // time of last event // Repeatedly compute time of next event and update Anna's speed // when the event occurs while(true) { // Find next event (new car involved in passing, or current passing ends) double deltat; deltat = 1E9; // time to next event int nextc = -1; // next car to pass/be passed, move ahead, or drop behind // For every time interval, if any car is passing Anna at a speed // different from Anna's, there is a possibility of a speed change // in the next time interval. if (!passing.isEmpty()) { for (Car c: passing) { if (c.s != s) { deltat = EPS; nextc = c.carnum; break; } } } // Now see which car interacts with Anna's car the soonest: for (Car c: behind) { if (c.s > s) { // c can overtake Anna at current speeds double temp = (c.l - (l-1) + c.s*t)*1.0/(s-c.s); if (temp < deltat) { deltat = temp; nextc = c.carnum; } } } for (Car c: ahead) { if (c.s < s) { // Anna can overtake c at current speeds double temp = (c.l - l + c.s*t)*1.0/(s-c.s); if (temp < deltat) { deltat = temp; nextc = c.carnum; } } } // Cars that are currently passing Anna could fall behind, move ahead, // or stay passing: for (Car c: passing) { // When does car fall behind? if (c.s < s) { // car is moving slower than Anna at current speeds double temp = (c.l - (l-1) + c.s*t)*1.0/(s-c.s); if (temp < deltat) { deltat = temp; nextc = c.carnum; if (equal(c.l+c.s*t,l-1) && prevs != s) // Anna's speed changed... deltat+=EPS; //...so better check next gizmo interval } } // When does car pull ahead? if (c.s > s) { double temp = (c.l - l + c.s*t)*1.0/(s-c.s); if (temp < deltat) { deltat = temp; nextc = c.carnum; if (equal(c.l+c.s*t,l) && prevs != s) // Anna's speed changed... deltat+=EPS; //...so better check next gizmo interval } } } // See if we're done: if (nextc == -1) { // no upcoming changes in passing... t += (d-l)*1.0/s; // ... next event is reaching destination //////////////////?????????????/////////////// ///// // No need to adjust Anna's speed at end since no more passing can occur ///// return; } // Round to next gizmo time: double nextt = Math.ceil(4*(t+deltat))/4; // Find Anna's position at gizmo time: l += (nextt - t)*s; // If this is >= destination, we're done: adjust time and return: if (l >= d) { t = nextt - (l-d)*1.0/s; if (l>d) return; // Otherwise, need to adjust her speed--finish time is a gizmo time: else lastpass = true; } // Now determine all changes in passing: count = 1; news = s; HashSet movebahead = new HashSet(); HashSet movebpass = new HashSet(); HashSet moveabehind = new HashSet(); HashSet moveapass = new HashSet(); HashSet movepbehind = new HashSet(); HashSet movepahead = new HashSet(); for (Car c: behind) { double newl = c.l+c.s*nextt; // c's new location at next event if (newl >= l-1 && newl <= l) { // c is passing Anna count++; news += c.s; movebpass.add(c); } else if (newl > l) { movebahead.add(c); } } for (Car c: ahead) { double newl = c.l+c.s*nextt; if (newl >= l-1 && newl <= l) { // Anna passes c count++; news += c.s; moveapass.add(c); } else if (newl < l-1) { moveabehind.add(c); } } for (Car c: passing) { double newl = c.l + c.s*nextt; if (newl >= l-1 && newl <= l) { count++; news += c.s; } else if (newl > l) { movepahead.add(c); } else { movepbehind.add(c); } } prevs = s; // remember old speed s = news/count; t = nextt; // update latest event time //status("Event"); // Special case--if a "passing" car is just about to pull ahead or // fall behind, move it ahead or behind for next event: for (Car c:passing) { double newl = c.l+c.s*nextt; if (equal(newl,l-1) && c.s < s) movepbehind.add(c); if (equal(newl,l) && c.s > s) movepahead.add(c); } if (lastpass) return; // we just had to update Anna's final speed, that's all update(moveapass,ahead,passing); update(moveabehind,ahead,behind); update(movebpass,behind,passing); update(movebahead,behind,ahead); update(movepbehind,passing,behind); update(movepahead,passing,ahead); } } public static void update(HashSet a, HashSet from, HashSet to) { for (Car c: a) { from.remove(c); to.add(c); } } public static void status(String msg) { System.out.print(msg); System.out.printf(": at time %f, Anna's loc/speed: %f, %d\n",t,l,s); for (Car c:ahead) { System.out.printf(" Car %d is ahead; loc/speed: %f, %d\n",c.carnum, (c.l+c.s*t),c.s); } for (Car c:behind) { System.out.printf(" Car %d is behind; loc/speed: %f, %d\n",c.carnum, (c.l+c.s*t),c.s); } for (Car c:passing) { System.out.printf(" Car %d is passing; loc/speed: %f, %d\n",c.carnum, (c.l+c.s*t),c.s); } } public static boolean equal(double a, double b) { return Math.abs(a-b) < EPS; } }