Foren » 30. BwInf

Aufgabe 3 - Runde 2

    • 3 Beiträge
    1. Januar 2012 18:35:22 CET

    Bei Teilaufgabe 2 heisst es, es soll der "bestmoegliche Platz" einer Mannschaft berechnet werden.

    "bestmoeglich" ist dabei etwas doppeldeutig. Zum Beispiel:

     

    Fall 1)

    Rang 1: A (10 Punkte, 20 Tore)

    Rang 2: B,C,D (jeweils 5 Punkte und 8 Tore)

    Rang 3: E (3 Punkte, 6 Tore)

    Rang 4: F (2 Punkte, 3 Tore)

     

    Fall 2)

    Rang 1: J (10 Punkte, 20 Tore)

    Rang 2: K (8 Punkte, 12 Tore)

    Rang 3: L (7 Punkte, 10 Tore)

    Rang 4: M (6 Punkte, 8 Tore)

    Rang 5: N (4 Punkte, 5 Tore)

    Rang 6: O (2 Punkte, 3 Tore)

     

    Obwohl sich Mannschaft "M" in Fall 2) im Vergleich zu den anderen Mannschaften besser platziert hat als

    Mannschaft "E" in Fall 1), hat Mannschaft "E" dennoch einen hoeheren Rang ergattert.

    Meine Frage: Welche von den beiden Mannschaften hat jetzt den "bestmoeglicheren" Platz?

    • 13 Beiträge
    2. Januar 2012 11:15:56 CET

    Ich habe mich damit auch beschäftigt und bin zu diesem Schluss gekommen:

     

    1) Es macht keinen Sinn (finde ich), wenn eine Mannschaft dadurch besser abschneidet, dass Mannschaften, die besser sind, untereinander genau gleich gut sind.

     

    2) In der Aufgabenstellung wird von Plätzen (also Rängen) gesprochen.

     

    Wenn 1) und 2) berücksichtigt werden, ergibt sich eine mir einleuchtende Rangverteilung:

     

    Fall 1) (siehe oben)

    Rang 1: A (10 Punkte, 20 Tore)

    Rang 2: B,C,D (jeweils 5 Punkte und 8 Tore)

    Rang 5: E (3 Punkte, 6 Tore)

    Rang 6: F (2 Punkte, 3 Tore)

     

    Wenn meine Einschätzung falsch ist, würde ich mich über eine Berichtigung von professioneller Seite freuen.


    Dieser Beitrag wurde am 2. Januar 2012 11:17:34 CET von Johannes Leuschner bearbeitet
    • 3 Beiträge
    4. Januar 2012 15:51:42 CET
    Die Regelung, wie Johanes sie vorschlaegt, finde ich auch am sinnvollsten. Ich schaetze mal es ist auch hier wie immer beim BWINF:
    wenn man seine Entscheidung ausreichend gut begruendet, sind beide Interpretationen der Aufgabenstellung okay.
    • 13 Beiträge
    4. Januar 2012 16:43:21 CET

    Ich hab noch eine andere Frage zu dieser Aufgabe:

    In der Aufgabe wird von einer Liste mit dazu nötigen Spielergebnissen gesprochen. Allerdings bleibt für mich unklar, wie diese aussehen soll, denn es gibt häufig viele verschiedene Möglichkeiten, wie eine Mannschaft den noch besten zu erreichenden Platz erreichen kann.

    Man könnte nun zum Beispiel die Liste auswählen, bei der die Mannschaft am wenigsten von den Ergebnissen anderer Mannschaften abhängig ist, oder die, bei der sie selbst am wenigsten Siege benötigt, aber dafür sehe ich in der Aufgabenstellung keine Anhaltspunkte.

    Meine Frage: Genügt es, eine der vielen Listen auszugeben?


    Dieser Beitrag wurde am 4. Januar 2012 16:44:11 CET von Johannes Leuschner bearbeitet
    • 230 Beiträge
    4. Januar 2012 19:59:42 CET
    Johannes Leuschner said:
    Meine Frage: Genügt es, eine der vielen Listen auszugeben?

    Das sollte meiner Meinung nach jeder selber für sich beantworten und dann entsprechend umsetzen.

    • 12 Beiträge
    12. Januar 2012 17:23:51 CET
    Wann werden die Beispiel-Eingaben endlich online gehen?
    • Moderator
    • 391 Beiträge
    12. Januar 2012 17:56:01 CET
    Sorry, dass es mit den Beispiel-Eingaben so lange dauert. Wir arbeiten gerade - eigentlich immer - an mehreren Fronten. In der nächsten Woche sollte es klappen. Wir werden auf jeden Fall in der Community ankündigen, wenn es soweit ist.
    • 19 Beiträge
    14. Januar 2012 11:18:26 CET
    Neue Frage:
    Muss man garantieren können, dass das Programm, immer und in jedem Fall, den wirklich besten also optimalen Tabellenplatz berechnet?
    • 45 Beiträge
    14. Januar 2012 12:33:55 CET
    Das ist natürlich das Ziel. Ich habe mich noch nicht mit der Aufgabe beschäftigt und kann nicht sagen, ob das so einfach möglich ist oder nicht. Wenn du es nicht garantieren kannst solltest du das auf jeden Fall bergünden und auf keinen Fall irgendetwas Falsches behaupten.
    • 13 Beiträge
    14. Januar 2012 15:40:49 CET
    Es gibt ja immer einen Platz der der bestmögliche ist, insofern ist das gefordert und theoretisch eindeutig lösbar. Sollte dein Programm es in bestimmten Situationen nicht garantieren können, sollte das, wie PaulJJ sagt, angemerkt werden.
    • Moderator
    • 391 Beiträge
    1. Februar 2012 12:31:38 CET
    Die in der Aufgabenstellung versprochenen Beispieldaten sind jetzt online: http://www.bundeswettbewerb-informatik.de/index.php?id=650
    • 19 Beiträge
    5. Februar 2012 12:37:55 CET
    Wolfgang Pohl said:
    Die in der Aufgabenstellung versprochenen Beispieldaten sind jetzt online: http://www.bundeswettbewerb-informatik.de/index.php?id=650

    Hallo,

    mir ist aufgefallen, dass die Beispieldaten (mindestens im offiziellen Format) fehlerhaft sind.

    Auszug aus beispiel2.txt:

     

    Harvestehude:Berlin:Hamburg - 1:1:2
    Harvestehude:Berlin:Muenchen - 3:4:5
    Harvestehude Essen Hamburg 9 12 11
    Harvestehude Essen Muenchen 7 10 10
    Harvestehude:Hamburg:Muenchen - 9:9:9
    Berlin:Essen:Hamburg - 0:1:3

     

    Die beiden Fettmarkierten Spiele sind im "einfachen Format"  angegeben nicht im offiziellen. Das kann böse böse Programmabstürze zur Folge haben :D. Ich dachte es muss ja nicht jeder selber suchen, daher poste ich das mal hier.

    Bei den anderen Dateien scheint auf den ersten Blick alles in Ordnung zu sein


    Dieser Beitrag wurde am 5. Februar 2012 12:38:51 CET von Lucas Elbert bearbeitet
    • 10 Beiträge
    13. Februar 2012 09:27:59 CET

    @fele ton: also bei meiner beispiel2.txt ist alles in ordnung...

     

    aber in beispiel6.txt gibt es doppelte einträge:

    Zeile 12 und 15:

    Muenchen:Lichterfelde:Muelheim - 0:1:7

    Lichterfelde:Muenchen:Muelheim - 0:0:4

     

    Zeile 23 und 29:

    Muenchen:Muelheim:Berlin - 0:2:1

    Muenchen:Berlin:Muelheim - 8:8:9

     

    ist das beabsichtig? eigentlich soll es ja nur n über 3 (Binomialkoeffizient) Spiele geben...


    Dieser Beitrag wurde am 13. Februar 2012 11:08:57 CET von DeepBlue bearbeitet
    • 9 Beiträge
    13. Februar 2012 14:46:34 CET

    @DeepBlue Wie du bereits gesagt hast, kann das nicht sein, weil du ja am Ende durch 3! teilst. Damit ist festgelegt, dass die Reihenfolge also keine Rolle spielt (bspw.  ist (A,B,C) identisch mit (C,B,A).


    Dieser Beitrag wurde am 13. Februar 2012 14:48:10 CET von JanG bearbeitet
    • 1 Beiträge
    13. Februar 2012 15:10:35 CET
    Ich habe gerade auch festgestellt, dass diese beiden Spiele doppelt aufgeführt werden.

    @ Programmer: Ich verstehe deine Antwort nicht ganz. Klar sind die Spiele identisch, das Problem ist ja, dass es in der Datei zwei verschiedene Ergebnisse gibt, obwohl es ja nur eins geben dürfte...

    Welches der Ergebnisse gilt denn jetzt? Oder ist das wirklich (aus irgendeinem seltsamen Grund) beabsichtigt?
    • 9 Beiträge
    14. Februar 2012 13:16:40 CET
    Meike Grewing said:
    Klar sind die Spiele identisch, das Problem ist ja, dass es in der Datei zwei verschiedene Ergebnisse gibt, obwohl es ja nur eins geben dürfte
    Dann sind wir ja alle einer Meinung.
    Meike Grewing said: Welches der Ergebnisse gilt denn jetzt? Oder ist das wirklich (aus irgendeinem seltsamen Grund) beabsichtigt?
    Es kann nicht beabsichtigt sein, weil es der Aufgabenstellung  (n über 3) widersprechen würde. Das heißt im Klartext: Die Daten sind fehlerhaft und müssten eigentlich von offizieller Seite korrigiert werden.

    Dieser Beitrag wurde am 14. Februar 2012 13:20:02 CET von JanG bearbeitet
    • 13 Beiträge
    15. Februar 2012 15:41:14 CET
    Unabhängig davon, ob es beabsichtigt ist, kann man sein Programm ja so anpassen, dass derartige Eingaben, die dem System widersprechen, erkannt und entsprechend behandelt werden (Es ist auch sinnvoll solche Programmabstürze zu verhindern, die durch Fehler des Benutzers verursacht werden).
    • 19 Beiträge
    19. Februar 2012 13:54:45 CET

    Ich würde gerne noch eine offizielle Ansage hören, ob die Fehler noch behoben werden, da wir ja sonst nur raten können, welches Ergebnis benutzt werden soll.

     

    Außerdem frage ich mich noch ob erwartet wird, dass das Programm auf fehlerhafte Eingaben entsprechend reagieren soll. Das ist ja alles andere als eine große Gedankenleistung, daher hab ich bisher nicht eingeplant darauf noch Zeit zu "verschwenden"...


    Dieser Beitrag wurde am 19. Februar 2012 13:55:02 CET von Lucas Elbert bearbeitet
    • 45 Beiträge
    19. Februar 2012 14:07:49 CET
    fele ton said:

    Außerdem frage ich mich noch ob erwartet wird, dass das Programm auf fehlerhafte Eingaben entsprechend reagieren soll. Das ist ja alles andere als eine große Gedankenleistung, daher hab ich bisher nicht eingeplant darauf noch Zeit zu "verschwenden"...

    Ich denke nicht, dass das erwartet wird. Wenn du beim MCI-Sonderpreis teilnehmen möchtest, wäre das aber vielleicht ein paar Überlegungen wert.


    Dieser Beitrag wurde am 19. Februar 2012 14:08:03 CET von PaulJJ bearbeitet
    • 10 Beiträge
    23. Februar 2012 15:10:45 CET
    Also hab mich jetzt mal bei der Geschäftsstelle schlau gemacht! Es sind wirklich Dopplungsfehler drin. Herr Pohl hat mir am Telefon gesagt, dass die nächste Tage eine bereinigte Version zu Verfügung steht. Es betrifft ja ausschließlich nur Beispiel 6. Er wird hier auch nochmal in ein paar Tagen hier etwas hineinschreiben.
    • Moderator
    • 391 Beiträge
    23. Februar 2012 17:23:34 CET
    Tobi1992 said:
    Herr Pohl hat mir am Telefon gesagt, dass die nächste Tage eine bereinigte Version zu Verfügung steht.

    Und schon ist es soweit. Die Dopplungen in beispiel6.txt bzw. example6.txt wurden entfernt (genauer gesagt: die - nach alter Zählung - Zeilen 15 und 29).

    • 5 Beiträge
    6. März 2012 18:22:45 CET

    5
    Berlin
    Muenchen
    Mannheim
    Essen
    Hamburg
    Muenchen

     

    In allen Beispieldateien kommt das 2. Team am Ende der Auflistung nochmal vor.  Die in der 1. Zeile gegebene Anzahl an Teams jedoch entspricht der tatsaechlichen.  Ergo ist die Zahl oben immer eins zu hoch und man wundert sich, woher das Phantomteam in den Datenstrukturen kommt...


    • 19 Beiträge
    6. März 2012 19:16:44 CET
    Nata said:

    5
    Berlin
    Muenchen
    Mannheim
    Essen
    Hamburg
    Muenchen

     

    In allen Beispieldateien kommt das 2. Team am Ende der Auflistung nochmal vor.  Die in der 1. Zeile gegebene Anzahl an Teams jedoch entspricht der tatsaechlichen.  Ergo ist die Zahl oben immer eins zu hoch und man wundert sich, woher das Phantomteam in den Datenstrukturen kommt...

     


     

    Antwort:

     

    In beiden Formaten steht in der ersten Zeile jeder Eingabedatei die Zahl N der Mannschaften. Die folgenden N Zeilen enthalten je den Namen einer Mannschaft. In der nächsten Zeile steht dann die "bestimmte Mannschaft", für die der bestmögliche noch erreichbare Platz berechnet werden soll. Anschließend folgen die bisherigen Spielergebnisse.

    • 5 Beiträge
    6. März 2012 20:21:46 CET
    Ups. Formatspezifikationen zuende lesen haette etwas fuer sich.