Differences

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

--- ffprog:ffprogjava2016:soiaufgben [2016/09/11 22:14]
Ivo Blöchliger [CableCar]
+++ ffprog:ffprogjava2016:soiaufgben [2016/10/11 13:17] (current)
Ivo Blöchliger [SOI - Aufgaben]
@@ Line 1: / Line 1: @@
-===== SOI - Aufgaben =====
+===== SOI - Aufgaben 2016 =====
 ==== CableCar ====
 Aufgabentext: https://soi.ch/contests/2016/round1/cablecar/
@@ Line 37: / Line 37: @@
 === Teilaufgabe 3 ===
+**Achtung:** Die Input-Datei war fehlerhaft, bitte laden Sie sich die neue Instanz-Datei herunter!
   * {{ :ffprog:ffprogjava2016:cable3-1000-100000.txt |}} {{ :ffprog:ffprogjava2016:cable3-1000-100000-output.txt |}}
+<hidden Lösungsvorschlag in Java>
+<code java>
+    public static void aufgabe3() throws IOException {
+        Path datei = Paths.get("cable3-1000-100000.txt");
+        // Speicher für die Ausgabe
+        ArrayList<String> lines = new ArrayList<>();
+        try (Scanner scanner = new Scanner(Files.newInputStream(datei))) {
+            int anzahlFaelle = scanner.nextInt();
+            for (int fall=0; fall<anzahlFaelle; fall++) {
+                int maximum = 2;
+                int m = scanner.nextInt();
+                System.out.println(m);
+                int erster = scanner.nextInt();
+                int letzter = scanner.nextInt();
+                int d = letzter-erster; // Differenz zwischen Masten 0 und 1
+                int anzahl = 2;
+                for (int j=2; j<m; j++) {
+                    int aktueller = scanner.nextInt();
+                    //System.out.println(aktueller);
+                    if (aktueller-letzter!=d) { // Mit letztem Masten vergleichen
+                        d = aktueller-letzter;
+                        anzahl = 2;
+                    } else {
+                        anzahl++;
+                        if (anzahl > maximum) {
+                            maximum = anzahl;
+                        }
+                    }
+                    letzter = aktueller;  // Aktueller Mast wird letzter Mast
+                }
+                lines.add(String.format("Case #%d: %d", fall+1, maximum));
+            }
+        }
+        // Einzeiler, das eine Liste von Strings in eine Datei schreibt.
+        Files.write(Paths.get("output.txt"), lines);
+    }
+</code>
+</hidden>
 === Teilaufgabe 4 ===
   * {{ :ffprog:ffprogjava2016:cable4.txt |}} {{ :ffprog:ffprogjava2016:cable4-output.txt |}}
-Der "naive" Brute-Force Algorithmus in Ruby braucht (auf meiner 5-jährigen Kiste) etwa 3min 12s. Die Komplexität ist $O(n^3)$.
+Der "naive" Brute-Force Algorithmus in Ruby braucht (auf meiner 5-jährigen Kiste) etwa 3min 12s. Die Komplexität ist $O(n^3)$. Die entsprechende Java-Implementation braucht dafür 7 Sekunden (auf der gleichen Kiste).
-Ein "dynamische Programmierung"-Algorithmus (ebenfalls Ruby) braucht dafür etwa 9s. Die Komplexität ist $O(n^2 \log(n))$, wobei das $\log(n)$ von Lookups herrührt.
+Ein "dynamische Programmierung"-Algorithmus (ebenfalls Ruby) braucht dafür etwa 9s. Die Komplexität ist $O(n^2 \log(n))$, wobei das $\log(n)$ von Lookups herrührt. In Java habe ich den Algorithmus nicht implementiert.
+==== Tunnel ====
+Aufgabentext: https://soi.ch/contests/2016/round1/gotthard/
+  * $O(n)$ Lösung: http://www.zrzahid.com/sliding-window-minmax/
+=== Aufgabe 1 ===
+  * {{ :ffprog:ffprogjava2016:tunnel1-100-1000-1000000.txt |}} {{ :ffprog:ffprogjava2016:tunnel1-100-1000-1000000-output.txt |}}
+=== Aufgabe 2 ===
+  * {{ :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>