import java.util.StringTokenizer; import java.io.BufferedReader; import java.io.BufferedOutputStream; import java.io.IOException; import java.io.InputStream; import java.io.InputStreamReader; import java.io.PrintWriter; import java.io.OutputStream; import java.util.Vector; import java.util.Queue; import java.util.ArrayDeque; import java.util.HashSet; import java.util.Arrays; public class vinyals { static final double EPS=1e-9; static final double INF=Double.POSITIVE_INFINITY; static double sq(double x) { return x*x; } // time <= 8\sqrt(4000) + \sum(red)/2 < 910 static final int TMAX = 910; static final int SWITCHMAX = TMAX/40+2; static int n; static double[] Ti,g0,gi; static int[][] green; static int[] ngreens; static int[][] red; static int[] nreds; static double normalize(int i, double t) { // return t \in [0, T_i) t+=EPS; t-=g0[i]; t%=Ti[i]; t+=Ti[i]; t%=Ti[i]; t-=EPS; return t; } static boolean isitgreen(int i, double t) { return normalize(i,t)-EPS pointers; void fromxstart(int igreen) { iend = crash(); if (iendtgreen) { feasible = false; return; } fromtstart(igreen, tgreen); } boolean canitgothere(double x) { return xstart < x + EPS && x - EPS < iend*1000; } double t(double x) { double dx=x-xstart; double dt=Math.sqrt(2*dx); return tstart+dt; } boolean canstartfrom(parabola p) { if (! p.canitgothere(xstart)) return false; double tp; if (xstart+EPS > p.iend*1000) tp = p.tend; else tp = p.t(xstart); return tp-EPS parabolas; static int numoriginal; static double best; static void bfs() { parabola[] parabolas_ = new parabola[parabolas.size()]; parabolas.toArray(parabolas_); best=INF; HashSet unseen = new HashSet(numoriginal); Vector seen = new Vector(); for (int i=1;i q = new ArrayDeque(); q.add(0); Integer v; while((v=q.poll())!=null) { parabola p = parabolas_[v]; if (p.iend==n) { best=Math.min(best,p.tend); } seen.removeAllElements(); for (Integer u : unseen) { if (parabolas_[u].canstartfrom(p)) { q.add(u); seen.add(u); } } unseen.removeAll(seen); q.addAll(p.pointers); } } public static void main(String[] argv) { Kattio io = new Kattio(System.in, System.out); n = io.getInt(); green = new int[n][SWITCHMAX]; ngreens = new int[n]; Arrays.fill(ngreens,0); red = new int[n][SWITCHMAX]; nreds = new int[n]; Arrays.fill(nreds,0); Ti = new double[n]; g0 = new double[n]; gi = new double[n]; green[0][0] = 0; ngreens[0]=1; for (int i=1;i(); for (int igreen=0;igreen(); parabolas.add(p); } } for (int ired=0;ired=tgreen) break; parabola p = new parabola(igreen,tgreen,ired,tred); if (p.feasible) { p.pointers = new Vector(); parabolas.add(p); } } } } } numoriginal = parabolas.size(); for (int igreen=0;igreen extraparabolas = new Vector(); for (int o = 0; o(); extraparabolas.add(q); } } } for (int o = 0; o(); extraparabolas.add(q); } } } parabolas.addAll(extraparabolas); } bfs(); io.println(best); io.close(); } } /** Simple yet moderately fast I/O routines. * * Example usage: * * Kattio io = new Kattio(System.in, System.out); * * while (io.hasMoreTokens()) { * int n = io.getInt(); * double d = io.getDouble(); * double ans = d*n; * * io.println("Answer: " + ans); * } * * io.close(); * * * Some notes: * * - When done, you should always do io.close() or io.flush() on the * Kattio-instance, otherwise, you may lose output. * * - The getInt(), getDouble(), and getLong() methods will throw an * exception if there is no more data in the input, so it is generally * a good idea to use hasMoreTokens() to check for end-of-file. * * @author: Kattis */ class Kattio extends PrintWriter { public Kattio(InputStream i) { super(new BufferedOutputStream(System.out)); r = new BufferedReader(new InputStreamReader(i)); } public Kattio(InputStream i, OutputStream o) { super(new BufferedOutputStream(o)); r = new BufferedReader(new InputStreamReader(i)); } public boolean hasMoreTokens() { return peekToken() != null; } public int getInt() { return Integer.parseInt(nextToken()); } public double getDouble() { return Double.parseDouble(nextToken()); } public long getLong() { return Long.parseLong(nextToken()); } public String getWord() { return nextToken(); } private BufferedReader r; private String line; private StringTokenizer st; private String token; private String peekToken() { if (token == null) try { while (st == null || !st.hasMoreTokens()) { line = r.readLine(); if (line == null) return null; st = new StringTokenizer(line); } token = st.nextToken(); } catch (IOException e) { } return token; } private String nextToken() { String ans = peekToken(); token = null; return ans; } }