ffprog:ffprogjava2016:soiaufgben

This is an old revision of the document!


Teilaufgaben 1 & 2

Lösungsvorschlag Cablecar Aufgaben 1 und 2

Anzeigen

Anzeigen

        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);

Teilaufgabe 3

Achtung: Die Input-Datei war fehlerhaft, bitte laden Sie sich die neue Instanz-Datei herunter!

Lösungsvorschlag in Java

Lösungsvorschlag in 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);
    }

Teilaufgabe 4

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.

Aufgabe 1

Aufgabe 2

Aufgabe 3

Anstatt einer Instanz-Datei (ca. 1GB) gibt es hier einen Java-Code, der eine Instanz-Datei generiert:

    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);
    }

Aufruf mit

        generate("tunnel3.txt, 50, 1000000, 100000000, 42);

Für diese Parameter sieht die Lösung wie folgt aus:

 
  • ffprog/ffprogjava2016/soiaufgben.1476182026.txt.gz
  • Last modified: 2016/10/11 12:33
  • by Ivo Blöchliger