Show pageOld revisionsBacklinksBack to top This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong. ===== 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> ffprog/ffprogjava2016/soiaufgben.txt Last modified: 2016/10/11 13:17by Ivo Blöchliger