fork download
copy 
  1. import java.io.OutputStream;
  2. import java.io.IOException;
  3. import java.io.InputStream;
  4. import java.io.OutputStream;
  5. import java.io.PrintWriter;
  6. import java.util.Arrays;
  7. import java.util.Iterator;
  8. import java.io.BufferedWriter;
  9. import java.util.InputMismatchException;
  10. import java.io.IOException;
  11. import java.io.Writer;
  12. import java.io.OutputStreamWriter;
  13. import java.util.Comparator;
  14. import java.util.NoSuchElementException;
  15. import java.io.InputStream;
  16. /**
  17.  * Built using CHelper plug-in
  18.  * Actual solution is at the top
  19.  */
  20. public class Main {
  21.     public static void main(String[] args) {
  22.         InputStream inputStream = System.in;
  23.         OutputStream outputStream = System.out;
  24.         InputReader in = new InputReader(inputStream);
  25.         OutputWriter out = new OutputWriter(outputStream);
  26.         C solver = new C();
  27.         int testCount = Integer.parseInt(in.next());
  28.         for (int i = 1; i <= testCount; i++)
  29.             solver.solve(i, in, out);
  30.         out.close();
  31.     }
  32.  
  33.     static class C {
  34.         int DIV = 10 * 1000 * 1000;
  35.         double[][] mem;
  36.         int[] prefixPre;
  37.  
  38.         double dp(int travelIndex, boolean prevFound, Integer[] perm, int[] saved, int[] x) {
  39.             if (travelIndex == perm.length) return 0;
  40.             if (mem[travelIndex][prevFound ? 1 : 0] > -1) return mem[travelIndex][prevFound ? 1 : 0];
  41.             int idx = perm[travelIndex];
  42.             double res = prevFound ? saved[idx] : 0;
  43.             if (prevFound) {
  44.                 res += dp(travelIndex + 1, true, perm, saved, x);
  45.             } else {
  46.                 int prefix = prefixPre[travelIndex];
  47.                 double probFind = (DIV - prefix == 0) ? 0 : ((double) x[idx] / (DIV - prefix));
  48.                 double savedIfFound = dp(travelIndex + 1, true, perm, saved, x);
  49.                 double savedIfNotFound = dp(travelIndex + 1, false, perm, saved, x);
  50.                 res += probFind * savedIfFound;
  51.                 res += (1 - probFind) * savedIfNotFound;
  52.             }
  53.             return mem[travelIndex][prevFound ? 1 : 0] = res;
  54.         }
  55.  
  56.         public void solve(int testNumber, InputReader in, OutputWriter out) {
  57.             int n = in.readInt();
  58.             mem = new double[n][2];
  59.             ArrayUtils.fill(mem, -2);
  60.             int[] a = new int[n], b = new int[n], x = new int[n];
  61.             IOUtils.readIntArrays(in, a, b, x);
  62.             int[] saved = new int[n];
  63.             for (int i = 0; i < saved.length; i++) saved[i] = a[i] - b[i];
  64.             Integer[] perm = new Integer[n];
  65.             for (int i = 0; i < perm.length; i++) perm[i] = i;
  66.             Arrays.sort(perm, new Comparator<Integer>() {
  67.                 public int compare(Integer o1, Integer o2) {
  68.                     double val1 = (double) saved[o1] / x[o1];
  69.                     double val2 = (double) saved[o2] / x[o2];
  70.                     return Double.compare(val1, val2);
  71.                 }
  72.             });
  73.             prefixPre = new int[n + 1];
  74.             for (int i = 1; i < prefixPre.length; i++) {
  75.                 prefixPre[i] = prefixPre[i - 1] + x[perm[i - 1]];
  76.             }
  77.             double savings = dp(0, false, perm, saved, x);
  78.             out.printLine(ArrayUtils.sumArray(a) - savings);
  79.         }
  80.     }
  81.     static class OutputWriter {
  82.         private final PrintWriter writer;
  83.  
  84.         public OutputWriter(OutputStream outputStream) {
  85.             writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
  86.         }
  87.  
  88.         public OutputWriter(Writer writer) {
  89.             this.writer = new PrintWriter(writer);
  90.         }
  91.  
  92.         public void print(Object... objects) {
  93.             for (int i = 0; i < objects.length; i++) {
  94.                 if (i != 0) {
  95.                     writer.print(' ');
  96.                 }
  97.                 writer.print(objects[i]);
  98.             }
  99.         }
  100.  
  101.         public void printLine(Object... objects) {
  102.             print(objects);
  103.             writer.println();
  104.         }
  105.  
  106.         public void close() {
  107.             writer.close();
  108.         }
  109.     }
  110.     static class InputReader {
  111.         private InputStream stream;
  112.         private byte[] buf = new byte[1024];
  113.         private int curChar;
  114.         private int numChars;
  115.         private InputReader.SpaceCharFilter filter;
  116.  
  117.         public InputReader(InputStream stream) {
  118.             this.stream = stream;
  119.         }
  120.  
  121.         public int read() {
  122.             if (numChars == -1) {
  123.                 throw new InputMismatchException();
  124.             }
  125.             if (curChar >= numChars) {
  126.                 curChar = 0;
  127.                 try {
  128.                     numChars = stream.read(buf);
  129.                 } catch (IOException e) {
  130.                     throw new InputMismatchException();
  131.                 }
  132.                 if (numChars <= 0) {
  133.                     return -1;
  134.                 }
  135.             }
  136.             return buf[curChar++];
  137.         }
  138.  
  139.         public int readInt() {
  140.             int c = read();
  141.             while (isSpaceChar(c)) {
  142.                 c = read();
  143.             }
  144.             int sgn = 1;
  145.             if (c == '-') {
  146.                 sgn = -1;
  147.                 c = read();
  148.             }
  149.             int res = 0;
  150.             do {
  151.                 if (c < '0' || c > '9') {
  152.                     throw new InputMismatchException();
  153.                 }
  154.                 res *= 10;
  155.                 res += c - '0';
  156.                 c = read();
  157.             } while (!isSpaceChar(c));
  158.             return res * sgn;
  159.         }
  160.  
  161.         public String readString() {
  162.             int c = read();
  163.             while (isSpaceChar(c)) {
  164.                 c = read();
  165.             }
  166.             StringBuilder res = new StringBuilder();
  167.             do {
  168.                 if (Character.isValidCodePoint(c)) {
  169.                     res.appendCodePoint(c);
  170.                 }
  171.                 c = read();
  172.             } while (!isSpaceChar(c));
  173.             return res.toString();
  174.         }
  175.  
  176.         public boolean isSpaceChar(int c) {
  177.             if (filter != null) {
  178.                 return filter.isSpaceChar(c);
  179.             }
  180.             return isWhitespace(c);
  181.         }
  182.  
  183.         public static boolean isWhitespace(int c) {
  184.             return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
  185.         }
  186.  
  187.         public String next() {
  188.             return readString();
  189.         }
  190.  
  191.         public interface SpaceCharFilter {
  192.             public boolean isSpaceChar(int ch);
  193.         }
  194.     }
  195.     static class ArrayUtils {
  196.         public static void fill(double[][] array, double value) {
  197.             for (double[] row : array) {
  198.                 Arrays.fill(row, value);
  199.             }
  200.         }
  201.  
  202.         public static long sumArray(int[] array) {
  203.             return new IntArray(array).sum();
  204.         }
  205.     }
  206.     static interface IntStream extends Iterable<Integer>, Comparable<IntStream> {
  207.         public IntIterator intIterator();
  208.         default public Iterator<Integer> iterator() {
  209.             return new Iterator<Integer>() {
  210.                 private IntIterator it = intIterator();
  211.  
  212.                 public boolean hasNext() {
  213.                     return it.isValid();
  214.                 }
  215.  
  216.                 public Integer next() {
  217.                     int result = it.value();
  218.                     it.advance();
  219.                     return result;
  220.                 }
  221.             };
  222.         }
  223.         default public int compareTo(IntStream c) {
  224.             IntIterator it = intIterator();
  225.             IntIterator jt = c.intIterator();
  226.             while (it.isValid() && jt.isValid()) {
  227.                 int i = it.value();
  228.                 int j = jt.value();
  229.                 if (i < j) {
  230.                     return -1;
  231.                 } else if (i > j) {
  232.                     return 1;
  233.                 }
  234.                 it.advance();
  235.                 jt.advance();
  236.             }
  237.             if (it.isValid()) {
  238.                 return 1;
  239.             }
  240.             if (jt.isValid()) {
  241.                 return -1;
  242.             }
  243.             return 0;
  244.         }
  245.         default public long sum() {
  246.             long result = 0;
  247.             for (IntIterator it = intIterator(); it.isValid(); it.advance()) {
  248.                 result += it.value();
  249.             }
  250.             return result;
  251.         }
  252.     }
  253.     static interface IntCollection extends IntStream {
  254.         public int size();
  255.     }
  256.     static class IOUtils {
  257.         public static void readIntArrays(InputReader in, int[]... arrays) {
  258.             for (int i = 0; i < arrays[0].length; i++) {
  259.                 for (int j = 0; j < arrays.length; j++) {
  260.                     arrays[j][i] = in.readInt();
  261.                 }
  262.             }
  263.         }
  264.     }
  265.     static abstract class IntAbstractStream implements IntStream {
  266.         public String toString() {
  267.             StringBuilder builder = new StringBuilder();
  268.             boolean first = true;
  269.             for (IntIterator it = intIterator(); it.isValid(); it.advance()) {
  270.                 if (first) {
  271.                     first = false;
  272.                 } else {
  273.                     builder.append(' ');
  274.                 }
  275.                 builder.append(it.value());
  276.             }
  277.             return builder.toString();
  278.         }
  279.  
  280.         public boolean equals(Object o) {
  281.             if (!(o instanceof IntStream)) {
  282.                 return false;
  283.             }
  284.             IntStream c = (IntStream) o;
  285.             IntIterator it = intIterator();
  286.             IntIterator jt = c.intIterator();
  287.             while (it.isValid() && jt.isValid()) {
  288.                 if (it.value() != jt.value()) {
  289.                     return false;
  290.                 }
  291.                 it.advance();
  292.                 jt.advance();
  293.             }
  294.             return !it.isValid() && !jt.isValid();
  295.         }
  296.  
  297.         public int hashCode() {
  298.             int result = 0;
  299.             for (IntIterator it = intIterator(); it.isValid(); it.advance()) {
  300.                 result *= 31;
  301.                 result += it.value();
  302.             }
  303.             return result;
  304.         }
  305.     }
  306.     static interface IntList extends IntReversableCollection {
  307.         public abstract int get(int index);
  308.         public abstract void removeAt(int index);
  309.         default public IntIterator intIterator() {
  310.             return new IntIterator() {
  311.                 private int at;
  312.                 private boolean removed;
  313.  
  314.                 public int value() {
  315.                     if (removed) {
  316.                         throw new IllegalStateException();
  317.                     }
  318.                     return get(at);
  319.                 }
  320.  
  321.                 public boolean advance() {
  322.                     at++;
  323.                     removed = false;
  324.                     return isValid();
  325.                 }
  326.  
  327.                 public boolean isValid() {
  328.                     return !removed && at < size();
  329.                 }
  330.  
  331.                 public void remove() {
  332.                     removeAt(at);
  333.                     at--;
  334.                     removed = true;
  335.                 }
  336.             };
  337.         }
  338.     }
  339.     static interface IntIterator {
  340.         public int value() throws NoSuchElementException;
  341.         public boolean advance();
  342.         public boolean isValid();
  343.     }
  344.     static interface IntReversableCollection extends IntCollection {
  345.     }
  346.     static class IntArray extends IntAbstractStream implements IntList {
  347.         private int[] data;
  348.  
  349.         public IntArray(int[] arr) {
  350.             data = arr;
  351.         }
  352.  
  353.         public int size() {
  354.             return data.length;
  355.         }
  356.  
  357.         public int get(int at) {
  358.             return data[at];
  359.         }
  360.  
  361.         public void removeAt(int index) {
  362.             throw new UnsupportedOperationException();
  363.         }
  364.     }
  365. }
  366.  
  367.  
Runtime error #stdin #stdout #stderr 0.06s 4386816KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
Exception in thread "main" java.util.InputMismatchException
	at Main$InputReader.read(Main.java:123)
	at Main$InputReader.readString(Main.java:164)
	at Main$InputReader.next(Main.java:188)
	at Main.main(Main.java:27)
https://ideone.com/LugDOd
language:
Java (HotSpot 12)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!