ffprog:ffprogjava2016:soiaufgben

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
Next revision
Previous revision
ffprog:ffprogjava2016:soiaufgben [2016/09/30 16:21]
Ivo Blöchliger [Tunnel]
ffprog:ffprogjava2016:soiaufgben [2016/10/11 13:17] (current)
Ivo Blöchliger [SOI - Aufgaben]
Line 1: Line 1:
-===== SOI - Aufgaben =====+===== SOI - Aufgaben 2016 =====
 ==== CableCar ==== ==== CableCar ====
 Aufgabentext: https://soi.ch/contests/2016/round1/cablecar/ Aufgabentext: https://soi.ch/contests/2016/round1/cablecar/
Line 99: Line 99:
   * {{ :ffprog:ffprogjava2016:tunnel2-100-1000-1000000.txt |}}  {{ :ffprog:ffprogjava2016:tunnel2-100-1000-1000000-output.txt |}}   * {{ :ffprog:ffprogjava2016:tunnel2-100-1000-1000000.txt |}}  {{ :ffprog:ffprogjava2016:tunnel2-100-1000-1000000-output.txt |}}
  
 +=== Aufgabe 3 ===
 +Anstatt einer Instanz-Datei (ca.0.5GB) gibt es hier einen Java-Code, der eine Instanz-Datei generiert:
 +<code java>
 +    public static void generate(String fileName, int cases, int maxN, int maxH, int seed) throws IOException {
 +        ArrayList<String> lines = new ArrayList<>();
 +        lines.add(String.format("%d",cases));
 +        Random r = new Random(seed);        
 +        for (int c=0; c<cases; c++) {
 +            int n = r.nextInt(maxN-4)+5;
 +            lines.add(String.format("%d",n));
 +            List<Integer> bounds = Arrays.asList(r.nextInt(n), r.nextInt(n));
 +            Collections.sort(bounds);          
 +            int minH = r.nextInt(maxH/2)+maxH/4;
 +            System.out.println("Tunnel open at height "+minH+" from "+bounds.get(0)+" to "+bounds.get(1)+" min length="+(bounds.get(1)-bounds.get(0)));
 +            int heights[][] = new int[2][n];
 +            for (int i=0; i<n; i++) {
 +                int x = (i>=bounds.get(0) && i<bounds.get(1)) ? minH : r.nextInt(maxH-1)+1;
 +                heights[1][i] = r.nextInt(x);
 +                heights[0][i] = r.nextInt(maxH-x)+x+1;
 +            }
 +            StringBuilder sb = new StringBuilder();
 +            for (int j=0; j<2; j++) {
 +                for (int i=0; i<n; i++) {
 +                    sb.append(heights[j][i]);
 +                    if (i<n-1) {
 +                        sb.append(" ");
 +                    }
 +                }
 +                lines.add(sb.toString());
 +                sb = new StringBuilder();
 +            }
 +        }
 +        Files.write(Paths.get(fileName), lines);
 +        System.out.println("Wrote file "+fileName);
 +    }
 +</code>
 +Aufruf mit
 +<code java>
 +        generate("tunnel3.txt", 50, 1000000, 100000000, 42);
 +</code>
 +Für diese Parameter sieht die Lösung wie folgt aus:
 +<code txt>
 +Case #1: 54553
 +Case #2: 118568
 +Case #3: 42236
 +Case #4: 95017
 +Case #5: 392495
 +Case #6: 23351
 +Case #7: 214369
 +Case #8: 207164
 +Case #9: 80147
 +Case #10: 101236
 +Case #11: 29947
 +Case #12: 272675
 +Case #13: 11311
 +Case #14: 568669
 +Case #15: 74155
 +Case #16: 36411
 +Case #17: 98517
 +Case #18: 118678
 +Case #19: 579076
 +Case #20: 364181
 +Case #21: 784906
 +Case #22: 10987
 +Case #23: 92835
 +Case #24: 208998
 +Case #25: 304626
 +Case #26: 130612
 +Case #27: 316250
 +Case #28: 88649
 +Case #29: 99034
 +Case #30: 256000
 +Case #31: 107054
 +Case #32: 178513
 +Case #33: 226822
 +Case #34: 64840
 +Case #35: 48131
 +Case #36: 4544
 +Case #37: 27783
 +Case #38: 66297
 +Case #39: 3345
 +Case #40: 44137
 +Case #41: 341521
 +Case #42: 226068
 +Case #43: 72879
 +Case #44: 383934
 +Case #45: 215890
 +Case #46: 58735
 +Case #47: 366097
 +Case #48: 263738
 +Case #49: 41854
 +Case #50: 6945
 +</code>
  • ffprog/ffprogjava2016/soiaufgben.1475245303.txt.gz
  • Last modified: 2016/09/30 16:21
  • by Ivo Blöchliger