===== 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 ==
Path datei = Paths.get("cable2-100-1000-1000000.txt");
// Speicher für die Ausgabe
ArrayList lines = new ArrayList<>();
try (Scanner scanner = new Scanner(Files.newInputStream(datei))) {
int n = scanner.nextInt();
for (int i=0; i
=== 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 |}}
public static void aufgabe3() throws IOException {
Path datei = Paths.get("cable3-1000-100000.txt");
// Speicher für die Ausgabe
ArrayList lines = new ArrayList<>();
try (Scanner scanner = new Scanner(Files.newInputStream(datei))) {
int anzahlFaelle = scanner.nextInt();
for (int fall=0; fall 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 ===
* {{ :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:
public static void generate(String fileName, int cases, int maxN, int maxH, int seed) throws IOException {
ArrayList lines = new ArrayList<>();
lines.add(String.format("%d",cases));
Random r = new Random(seed);
for (int c=0; c 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=bounds.get(0) && i
Aufruf mit
generate("tunnel3.txt", 50, 1000000, 100000000, 42);
Für diese Parameter sieht die Lösung wie folgt aus:
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