Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision | ||
ffprog:ffprogjava2016:soiaufgben [2016/09/30 10:21] 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 |
==== CableCar ==== | ==== CableCar ==== | ||
Aufgabentext: | Aufgabentext: | ||
Line 91: | Line 91: | ||
* $O(n)$ Lösung: http:// | * $O(n)$ Lösung: http:// | ||
+ | |||
+ | === Aufgabe 1 === | ||
+ | * {{ : | ||
+ | |||
+ | === Aufgabe 2 === | ||
+ | |||
+ | * {{ : | ||
+ | |||
+ | === 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< | ||
+ | lines.add(String.format(" | ||
+ | Random r = new Random(seed); | ||
+ | for (int c=0; c<cases; c++) { | ||
+ | int n = r.nextInt(maxN-4)+5; | ||
+ | lines.add(String.format(" | ||
+ | List< | ||
+ | Collections.sort(bounds); | ||
+ | int minH = r.nextInt(maxH/ | ||
+ | System.out.println(" | ||
+ | int heights[][] = new int[2][n]; | ||
+ | for (int i=0; i<n; i++) { | ||
+ | int x = (i> | ||
+ | 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), | ||
+ | System.out.println(" | ||
+ | } | ||
+ | </ | ||
+ | Aufruf mit | ||
+ | <code java> | ||
+ | generate(" | ||
+ | </ | ||
+ | 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 | ||
+ | </ |