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
ffprog:ffprogjava2016:soiaufgben [2016/10/11 11:00] – [Tunnel] Ivo Blöchligerffprog:ffprogjava2016:soiaufgben [2016/10/11 11:17] (current) – [SOI - Aufgaben] Ivo Blöchliger
Line 1: Line 1:
 +===== SOI - Aufgaben 2016 =====
 +==== CableCar ====
 +Aufgabentext: https://soi.ch/contests/2016/round1/cablecar/
  
 +=== Teilaufgaben 1 & 2 ===
 +  * Cable-Car Instanzen und Lösungen. Aufgabe 1 {{ :ffprog:ffprogjava2016:cable-10-100.txt |}} {{ :ffprog:ffprogjava2016:cable-10-100-output.txt |}} {{ :ffprog:ffprogjava2016:cable-50-10000.txt |}} {{ :ffprog:ffprogjava2016:cable-50-10000-output.txt |}} {{ :ffprog:ffprogjava2016:cable-100-1000000.txt |}} {{ :ffprog:ffprogjava2016:cable-100-1000000-output.txt |}}
 +  * Cable-Car Aufgabe 2: {{ :ffprog:ffprogjava2016:cable2-100-1000-1000000.txt |}} {{ :ffprog:ffprogjava2016:cable2-100-1000-1000000-output.txt |}}
 +
 +== Lösungsvorschlag Cablecar Aufgaben 1 und 2 ==
 +<hidden Anzeigen>
 +<code java>
 +        Path datei = Paths.get("cable2-100-1000-1000000.txt");
 +        // Speicher für die Ausgabe
 +        ArrayList<String> lines = new ArrayList<>();
 +        try (Scanner scanner = new Scanner(Files.newInputStream(datei))) {
 +            int n = scanner.nextInt();
 +            for (int i=0; i<n; i++) {
 +                int m = scanner.nextInt();
 +                boolean ok = true;
 +                int a = scanner.nextInt();
 +                int b = scanner.nextInt();
 +                int d = b-a; // Differenz zwischen Masten 0 und 1
 +                for (int j=2; j<m; j++) {
 +                    int c = scanner.nextInt();
 +                    if (c-b!=d) { // Mit letztem Masten vergleichen
 +                        ok = false;
 +                    }
 +                    b = c;  // Aktueller Mast wird letzter Mast
 +                }
 +                lines.add(String.format("Case #%d: %s", i+1, ok ? "yes" : "no"));
 +            }
 +        }
 +        // Einzeiler, das eine Liste von Strings in eine Datei schreibt.
 +        Files.write(Paths.get("output.txt"), lines);
 +</code>
 +</hidden>
 +
 +=== 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)$. 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. 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>