Bundeswettbewerb Informatik: BWINF

Weedjo

Ich habe, weil ich noch totaler Anfänger bin das ganze in einer Konsole geschrieben, d.h. ich hab kein UI. Aber bei mir rechnet der die Aufgaben eigentlich blizzschnell aus, so hatte ich das Bsp nr1) mit den paar 100000 Monaten in weniger als ner Sekunde raus. Mit Plan, in welchem Monat man was kaufen bzw verkaufen muss. Bei meinem Programm besteht jedoch der Nachteil, dass man vorher eingeben muss wieviele unterschiedliche Gegenstände existieren und diese dann auch einzeln eintragen muss.

stalafin schrieb:

Ich frage nochmal:
Diejenigen, die eine derart schnelle Berechnung der Anzahl an benötigten Monaten zum Kaufen aller Gegenstände haben: Habt ihr auch eine Ausgabe der zu kaufenden Gegenstände pro Monat?

Ohne die Ausgabe natürlich. Mit Ausgabe dauert es deutlich länger. Aber interessant ist eigentlich nur die Berechnungszeit, da die Ausgabezeit so lang wird und auch bei jedem Programmdurchlauf extrem unterschiedlich ist, dass man mit Ausgabe die Qualität des Alogrithmus nicht messen kann. Wenn man die Zeit zur Ausgabe bewertet kommt es im Prinzip nur darauf an, wer das schnellere Konsolenprogramm hat und wer weniger Ausgabe pro Monat produziert. Meine Werte sind daher die Zeiten, die das Programm braucht, wenn man die ausführliche Ausgabe (mit Daten für jeden Monat) in eine Datei schreibt.

Hey Leute,

ich hab ein kleines Anliegen an euch.

Die Abgabe zum BWInf ist ja am Montag. Meint ihr, einer von euch könnte Montag Abend hier die Lösung zu einem der Aufgaben (am besten die 4) online stellen?

Es geht um folgendes:

Eine gute Freundin von mir hat in der Schule Informatik gewählt (warum müssen immer die DAU's informatik wählen?). Nun stellt deren Lehrer in jedem Halbjahr eine große Hausaufgabe, die sich 1x im Jahr mit dem BWInf überschneidet - sprich: die Schüler müssen eine der BWInf Aufgaben lösen.
Bisher habe ich dies jedes Jahr für sie übernommen.
Nun kam sie aber erst letzte Woche angedackelt und meinte, sie habe vergessen mir die Blätter zu geben - echt toll^^ - nur leider hatte ich erst 3 Monate Semesterferien, in denen ich schön hätte arbeiten können, aber jetzt stecke ich wieder voll im Semester und habe keine Zeit.

Nun die bitte an euch: Kann mir einer Montag Abend seine Lösung zu einer der Aufgaben zukommen lassen? Dann könnte sie diese am Dienstag abgeben (am Dienstag ist Abgabeschluss der Hausaufgabe)

Dad wäre echt nett von euch.

Gruß

Christian

ps: eMail: christian@felsenweg.de

Phoemuex

stalafin schrieb:

Ich frage nochmal:
Diejenigen, die eine derart schnelle Berechnung der Anzahl an benötigten Monaten zum Kaufen aller Gegenstände haben: Habt ihr auch eine Ausgabe der zu kaufenden Gegenstände pro Monat?

Natürlich MIT Ausgabe das wird bei dem einen Beispiel mit dem Budget von 1€ dann zwar fast eine 7-MB(!) plain-text Datei, aber es geht in knapp 20 Sekunden auf einem 2-GHz Rechner...

@s9ccbeck: Hört sich zwar nach einer komischen Ausrede an, aber am Montag um 23:59 sollte gehen

stalafin

Jutjut, ich habe doch noch ne schnieke Optimierung gefunden. (nachdem ich heute morgen den Rechner eingeschaltet hatte und er bis jetzt mit der dritten Aufgabe am werkeln war).
Jetzt ist er nach ner Minute an dem Punkt angelangt, an der das alte Prog nach 10 Stundem war. Man ist das grausam.

Beispiel 1 (1 Euro) schafft er jetzt in ~ 30 Sekunden. *froi*

Aber auf ne 7 MByte-txt-Datei komme ich nicht. Bei mir sinds 5,8 MByte.

@Phoemuex: ist keine Ausrede ^^ - Komme eh erst So spät heim; passt also - wenn du willst kann ich dir auch meine Real-Adresse geben, damit du ne absicherung hast (sofern du sie nicht an PayBack weiter gibst

131071 Monate in 0.891 Sekunden mit Ausgabe

hi,
hat von euch [schon] jemand die 2. Aufgabe (Robot Dressing) gelöst?

Ich komm auf 270 Möglichkeiten, was habt ihr so raus?

mfg Helge

ESS_CB

ehm, wenn man hier sich so umschaut kommt bei jedem bei Aufgabe1 Bsp 2 was um die 170 raus, ich komme aber auf 90, seht ihr nen Fehler in der Reihenfolge?

Die kürzeste gefundene Reihenfolge:
Kaufen: 94172E
Kaufen: 7362E
Verkaufen: 94172E Verkaufen: 7362E Kaufen: 100368E
Verkaufen: 100368E Kaufen: 102763E
Kaufen: 94172E
Kaufen: 7362E
Verkaufen: 94172E Verkaufen: 7362E Kaufen: 100368E
Kaufen: 88426E
Kaufen: 7362E
Verkaufen: 88426E Verkaufen: 7362E Kaufen: 97777E
Kaufen: 85540E
Kaufen: 7362E
Verkaufen: 85540E Verkaufen: 7362E Kaufen: 94172E
Verkaufen: 94172E Kaufen: 95027E
Kaufen: 85540E
Kaufen: 7362E
Verkaufen: 85540E Verkaufen: 7362E Kaufen: 94383E
Kaufen: 85540E
Kaufen: 7362E
Verkaufen: 85540E Verkaufen: 7362E Kaufen: 94172E
Kaufen: 73690E
Kaufen: 7362E
Verkaufen: 73690E Verkaufen: 7362E Kaufen: 90386E
Kaufen: 79067E
Kaufen: 7362E
Verkaufen: 79067E Verkaufen: 7362E Kaufen: 88426E
Kaufen: 70123E
Kaufen: 7362E
Verkaufen: 70123E Verkaufen: 7362E Kaufen: 85540E
Kaufen: 70123E
Kaufen: 7362E
Verkaufen: 70123E Verkaufen: 7362E Kaufen: 79067E
Kaufen: 65492E
Kaufen: 7362E
Verkaufen: 65492E Verkaufen: 7362E Kaufen: 73690E
Kaufen: 60736E
Kaufen: 7362E
Verkaufen: 60736E Verkaufen: 7362E Kaufen: 70123E
Verkaufen: 70123E Kaufen: 70782E
Kaufen: 60736E
Kaufen: 7362E
Verkaufen: 60736E Verkaufen: 7362E Kaufen: 70123E
Kaufen: 60736E
Kaufen: 7362E
Verkaufen: 60736E Verkaufen: 7362E Kaufen: 65492E
Kaufen: 43335E
Kaufen: 7362E
Verkaufen: 43335E Verkaufen: 7362E Kaufen: 52793E
Verkaufen: 52793E Kaufen: 61429E
Kaufen: 43335E
Kaufen: 7362E
Verkaufen: 43335E Verkaufen: 7362E Kaufen: 52793E
Verkaufen: 52793E Kaufen: 60736E
Kaufen: 43335E
Kaufen: 7362E
Verkaufen: 43335E Verkaufen: 7362E Kaufen: 52793E
Kaufen: 41915E
Kaufen: 7362E
Verkaufen: 41915E Verkaufen: 7362E Kaufen: 46421E
Kaufen: 26530E
Kaufen: 7362E
Verkaufen: 26530E Verkaufen: 7362E Kaufen: 35886E
Verkaufen: 35886E Kaufen: 43335E
Kaufen: 26530E
Kaufen: 7362E
Verkaufen: 26530E Verkaufen: 7362E Kaufen: 35886E
Verkaufen: 35886E Kaufen: 41915E
Kaufen: 26530E
Kaufen: 7362E
Verkaufen: 26530E Verkaufen: 7362E Kaufen: 35886E
Kaufen: 18926E
Kaufen: 7362E
Verkaufen: 18926E Verkaufen: 7362E Kaufen: 27862E
Kaufen: 18926E
Kaufen: 7362E
Verkaufen: 18926E Verkaufen: 7362E Kaufen: 25059E
Verkaufen: 25059E Kaufen: 26530E
Kaufen: 18926E
Kaufen: 7362E
Verkaufen: 18926E Verkaufen: 7362E Kaufen: 25059E
Kaufen: 7362E
Verkaufen: 7567E Verkaufen: 7362E Kaufen: 21649E
Kaufen: 7567E
Kaufen: 7362E
Verkaufen: 7567E Verkaufen: 7362E Kaufen: 18926E
Kaufen: 7362E
Verkaufen: 7362E Kaufen: 10211E
Kaufen: 8135E
Kaufen: 7567E
Kaufen: 7362E

Ich kann nämlich keinen entdekcen

Monatsbudget ist 10.000 nicht 100.000

ESS_CB

danke danke^^

ich glaub sonst hätte ich es nicht mehr hinbekommen den Bug zu fixen, übrigens, es war nur ein Buchstabe falsch (i statt k)

So, jetzt ist der Wettbewerb vorbei (jedenfalls heut nacht). Was habt ihr so gemacht, wie lang habt ihr gebraucht, wie viel Prozent habt der Arbeit habt ihr in der letzten Woche erledigt? Und wer hat heute erst abgegeben?
Ich hab Aufgabe 1 (10-15 h), 2 (10 h), 4 (10 h), 5 (10-15 h). Davon hab ich ungefähr 50 Prozent (die gesamte Dokumentation)in der letzten Woche gemacht :). Und ich habe folglich auch erst heute abgegeben. Irgendwie brauch ich immer bis zur letzten Sekunde

PS: Tobias Thierer hat in den letzten Jahren auf seiner Homepage (http://tobias-thierer.de/bwifiles.html) immer einen Platz angeboten, wo er Einsendungen gesammelt hat. Wenn er es diesmal auch wieder macht kann man da sein eigenes Zeugs hinschicken und auch anschauen, was die anderen so gemacht haben.

Laut Herrn Pohl verschiebt sich der EInsendeschluss des BWInf um einen Tag. Er schreibt in fido.ger.bwinf (Newsgruppe):

BWInf offiziell in fido.ger.bwinf schrieb:

Da ich zahlreiche per Mail gestellte Fragen einige Tage lang nicht beantworten konnte und heute Vormittag die Online-Anmeldung nicht funktionierte, werden wir in mit diesen Unannehmlichkeiten begründeten Ausnahmefällen auch Einsendungen akzeptieren, die den Poststempel des morgigen Tages (14.11.) tragen.

In Einzelfällen scheint die Online-Anmeldung schon einmal zu haken. Bitte benutzt dann das Papierformular und füllt es vollständig aus.

Online-Anmelder schreiben bitte ihre Einsendenummer außen auf den Umschlag.

Ich kann allerdings nicht für die Richtigkeit dieser Angaben garantieren. Theoretisch könnte jeder in die Newsgroup schreiben und behaupten, dass er Herr Pohl wäre.

Habe gestern abend noch meine Doku geschrieben (Aufgaben 1 und 4).

Mein Kumpel hat heute morgen noch bis um 7:00 Uhr seinen Mist (Aufgaben 3 und 5) fertiggestellt. Was ein Vogel! Der war heute dermaßen tot, dass war einfach nur herrlich.

Er hat für die die HTML-Aufgabe um die 1000 Zeilen Code fertiggestellt.

Naja...

Michael E.

Kann hier bitte mal einer mit ner Wahnsinnsgeschwindigkeit bei Aufgabe 1 seine(n) Lösung(sansatz) posten?

Hallo,

hier ist der betreffende Teil der Dokumentation:

Verwendete Beispieleingabedatei
3
1
2
7
4

Grundansatz
Es muss versucht werden, das gegebene Budget in jedem Monat möglichst gut auszunutzen. Wenn berechnet wird, welche Objekte in einem Monat gekauft/zurückgegeben werden sollen, wird erst einmal der Gesamtwert der Objekte bestimmt, die am Anfang des Monats im Besitz des Vereins sind (z.B.: Besitz der Gegenstände für 1€ und 2€ am Anfang des Monats führt zu einer Summe von 3€). Diese Summe ergibt zusammen mit dem monatlichen Budget die Geldmenge, die in diesem Monat ausgegeben werden kann (im Beispiel: 3€ vom Vormonat+3€ Budget=6€). Für diese Geldmenge wird jetzt berechnet, wie sie am besten für eine neue Sammlung von Gegenständen ausgegeben werden kann (so, dass möglichst wenig Geld übrig bleibt). Die Menge der alten Gegenstände wird nun mit der neu berechneten Menge von Gegenständen verglichen. Wenn ein Gegenstand vorher im Besitz des Vereins war und in der neuen Menge nicht enthalten ist muss er zurückgegeben werden. Wenn ein Gegenstand nur in der neuen Menge enthalten ist muss er gekauft werden. Wenn ein Gegenstand in beiden Mengen/in keiner Menge enthalten ist passiert nichts. Diese Informationen werden ausgegeben.
Das wird so viele Monate gemacht, bis alle Gegenstände gekauft sind. Am Ende wird noch eine Zusammenfassung ausgegeben.

Methoden, eine Geldmenge möglichst gut auf die Gegenstände zu verteilen:
Die einfachste Methode, eine Geldmenge möglichst effizient auf eine Menge von Gegenständen zu verteilen, ist, für jede mögliche Kombination von Gegenständen zu berechnen, wie viel Geld übrig bleibt, nachdem man diese Gegenstände gekauft hat. Wenn weniger als 0 Euro übrig bleiben kann man diese Kombination mit der gegebenen Geldmenge nicht kaufen. Wenn kein Geld übrig bleibt ist die Kombination ideal. Sonst wird die Kombination gewählt, bei der am wenigsten Geld übrig bleibt. Das Ausprobieren kann man mit Rekursion relativ einfach machen. Man fängt beim teuersten Gegenstand (im Beispiel: 7) an und startet mit ihm die Rekusion.
In der Rekursion wird immer ein Gegenstand als gekauft eingetragen, dann die Rekursion für den nächsten Gegenstand aufgerufen. Dann wird der Gegenstand als nicht gekauft eingetragen und die Rekursion wieder für den nächsten Gegenstand aufgerufen. Wenn die Rekursion beim billigsten Gegenstand angekommen ist (inzwischen ist eine Liste entstanden, die alle Objekte beeinhaltet, die während der Rekursion gekauft wurden) wird nachgeschaut, ob die Menge der Gegenstände, die im Laufe der Rekursion gekauft wurden, besser ist als die bisher beste Menge (ob weniger Geld übrig bleibt).
Für das Beispiel mögliche Kombinationen: [1, 2, 4, 7]; [1, 2, 7]; [1, 4, 7]; [2, 4, 7]; [1, 2]; [1, 4]; [1, 7]; [2, 4]; [2, 7]; [4, 7]; [1]; [2]; [4]; [7]; [].
Wenn man 6 Euro ausgeben kann ist die beste Kombination [2, 4], da dann alles Geld ausgegeben wird.
Diese Methode ist allerdings sehr langsam. Deshalb habe ich drei Verbesserungen:
Erste Verbesserung: Der Kauf des Gegenstands wird nicht simuliert, wenn nicht genug Geld übrig ist, um ihn zu kaufen. Dazu muss bei jedem rekursiven Aufruf die Information mitgegeben werden, wie viel Geld nach den vorherigen Käufen noch übrig ist.
Zweite Verbesserung: Wenn eine optimale Kombination gefunden wurde (kein Geld übrig), wird diese Kombination gespeichert und die Rekursion abgebrochen.
Dritte Verbesserung: Es geht ja bei der Rekursion darum, Möglichkeiten zu finden, mehr Geld auszugeben, als bisher maximal ausgegeben wurde. Deshalb kann die Rekursion abgebrochen werden, wenn die Summe der Preise der Objekte, die billiger als das gerade bearbeitete Objekt sind, zusammen mit dem Preis des aktuellen Objekts weniger oder gleich viel ergibt als der bisher höchste erreichte Gesamtpreis. (Beispiel: Der bisherige Bestwert ist 6€. Bisher wurde in der Rekursion noch nichts gekauft. Jetzt ist das Objekt mit dem Wert 2€ dran. Das Objekt mit 2€ und das Objekt mit 1€ sind zusammen (3€) nicht so viel wert, wie der bisherige Bestwert(6€). Deshalb kann die Rekursion bei dem Objekt für 2€ schon abgebrochen werden. Die weitere Rekursion würde keine höheren Werte als 3€ bringen).
Es wäre natürlich schlecht, wenn man die Preise aller billigeren Objekte bei jedem rekursiven Aufruf neu berechnen müsste, deshalb werden sie schon vorher von der Funktion addierePreise berechnet und dann im addierte_preise-Attribut von KaufObjekt eingetragen.

asotbb

Hi!
Wie ist des denn so, wann bekommt man denn seine Ergebnisse, Punktzahl, oder bekommt man eine genaue Auflistung, was falsch war etc.?
Aja und hat jemand schon ne Bestätigung, dass seine Absendung bei denen eingegangen ist oder nicht? Ich hab sogar die Online-Anmeldung genutzt, aber no keine Mail erhalten?

mfg
blut-lecker

Jester

Michael E. schrieb:

Kann hier bitte mal einer mit ner Wahnsinnsgeschwindigkeit bei Aufgabe 1 seine(n) Lösung(sansatz) posten?

Ich hab zwar nicht implementiert, hätte aber was ähnliches gemacht, wie da s. was hier http://en.wikipedia.org/wiki/Knapsack_problem als Pseudo-Polynomialzeitalgorithmus angegeben ist. Also Wert aller Gegenstände zusammenzählen und dann ein Feld der Größe Anzahl Gegenstände * Gesamtwert aller Gegenstände ausgefüllt. Anschließend läßt sich in jedem Schritt in O(Anzahl Gegenstände) bestimmen, was optimalerweise gekauft werden muß. Das dürfte ziemlich flott sein.

@Jester: Erstaunlich, das ist genau unser Problem. Wenn man das kennt ist die erste Aufgabe gar kein Problem mehr.
@blut-lecker: Ich hab auch Online-Anmeldung und hab meine Einsendenummer ganz fett auf die Rückseite des Umschlags geschrieben, habe allerdings auch noch keine Mail erhalten.
Laut Statistik des letzten Jahres waren es beim letzten Mal allerdings ~450 Teilnehmer. Wenn es diesmal ähnlich viele sind müssen die ziemlich viele Päckchen bearbeiten.
Letztes Jahr wurde mir die Empfangsbestätigung trotzdem an dem Tag zugeschickt, an dem die Einsendung angekommen ist (also sind sie dieses Jahr später dran). Die Ergebnisse kamen 40 Tage nach dem Einsendeschluss (allerdings nur per E-Mail). Die Urkunden kamen wegen irgendwelcher Probleme im Januar. Da gibt auch es einen Bogen mit Kästchen dazu, wo der Korrektor immer angekreuzt hat, was du falsch gelöst hast. Allerdings ist der nicht sehr detailliert. Ich hab mal meinen vom letzten Jahr hochgeladen: http://img329.imageshack.us/img329/3987/bwinfergebnis224zn7.jpg (die Durchgestrichenen habe ich nicht gemacht.) Deine Unterlagen bekommst du übrigens nicht zurück.

ESS_CB

du kannst in der OnlineAnmeldung auf Bearbeitungsstatus gehen, da steht dann "bereits angekommen" mehr habe ich allerdings auch nicht erhalten.