Die Herausforderung

Dieses Semester geht es um die Steuerung eines genialen Stücks der Ingenieurskunst: den Construct-O-Mat. Mit dem richtigen Bauplan und den richtigen Rohstoffen kann er jedes denkbare Produkt herstellen. Ein Bauplan beschreibt, aus welchen Rohstoffen sich ein Produkt zusammensetzt, dabei können gegebenenfalls Nebenprodukte entstehen. Einige Produkte können wiederum als Rohstoffe für andere Produkte fungieren. Leider wird der Construct-O-Mat sehr heiß bei der Fertigung, sodass er nach einer bestimmten Menge an Hitze abkühlen muss.

Da sowohl Zeit als auch Ressourcen begrenzt sind ist die Aufgabe einen Produktionsplan zu finden, der Produkte von möglichst großen Wert produziert. Ein Produktionsplan ist eine Reihe von Bauplänen, die der Construct-O-Mat nacheinander abarbeitet.

Spielregeln

Zu Beginn jeder Runde erhalten die Programme drei Informationen:

Euer Programm darf jetzt beliebig viele Produktionspläne erstellen. Keiner der Produktionspläne darf zur Überhitzung des Construct-O-Mat führen. Sollte vor Ende der Fertigung das Kühlmittel alle werden, verbrennen mit dem Construct-O-Mat auch alle Produkte.

Es gelten natürlich die allgemeinen Richtlinien für Programmierwettbewerbe.

Ein-/Ausgabe Format

Euer Programm wird über die Standard Ein- und Ausgabe mit dem Spiel kommunizieren.

Eingabe

Als Eingabe erhält euer Programm vier Zeilen.

Wertliste
Die erste Zeile ist eine Liste mit dem Wert aller Produkte
Anfangsbestand
Die Zweite Zeile ist eine Liste aller Anfangs zur Verfügung stehenden Rohstoffe
Bauplanliste
Die dritte Zeile ist eine Liste von Bauplänen
Kühlmittel
In der vierten Zeile wird die verfügbare Menge an Kühlmittel angegeben

Produkte / Rohstoffe werden durch ihre Position in der Wertliste identifizert. Gezählt wird dabei ab \(0\). Der Anfangsbestand kann auch \(0\) betragen. In diesem Fall ist entsprechende Produkt dann anfangs nicht verfügbar.

Beispiel (Die Leerzeichen dienen der Übersicht)

[10, 12, 25]
[ 7,  3,  0]

Es gibt drei Produkte \(\text{Produkt}_0\) mit Wert \(10\), \(\text{Produkt}_1\) mit Wert \(12\) und \(\text{Produkt}_2\) mit Wert \(25\).

Zu Beginn stehen \(7 \times \text{Produkt}_0\), \(3 \times \text{Produkt}_1\) und \(0 \times \text{Produkt}_2\) zur Verfügung.

Ein Bauplan besteht aus 3 Elementen: einer Liste von benötigen Rohstoffen, eine Liste von enstehenden Produkten und dem benötigen Kühlmittel. Rohstoffe können mehrfach auftreten und werden dann enstrechend oft benötigt.

Beispiel (Die Leerzeichen dienen der Übersicht)

[10, 12, 25]
[ 7,  3,  0]
[([0,0],[1],1),([0,1],[2],5)]

Es gibt zwei Baupläne:

  • \(\text{Bauplan}_0\): \(1 \times \text{Produkt}_1 \leftarrow 2 \times \text{Rohstoff}_0\) für \(1\) Kühlmittel.
  • \(\text{Bauplan}_1\): \(1 \times \text{Produkt}_2 \leftarrow 1 \times \text{Rohstoff}_0 + 1 \times \text{Rohstoff}_1\) für \(5\) Kühlmittel.

Das verfügbare Kühlmittel ist eine ganze Zahl zwischen \(1\) und \(2^{15}-1\).

Vollständiges Beispiel (Die Leerzeichen dienen der Übersicht)

[10, 12, 25]
[ 7,  3,  0]
[([0,0],[1],1), ([0,1],[2],5)]
23

Drei Produkte:

  • \(7 \times \text{Produkt}_0\) mit Wert \(10\)
  • \(3 \times \text{Produkt}_1\) mit Wert \(12\)
  • \(0 \times \text{Produkt}_2\) mit Wert \(25\)

Zwei Baupläne:

  • \(\text{Bauplan}_0\): \(1 \times \text{Produkt}_1 \leftarrow 2 \times \text{Rohstoff}_0\) für \(1\) Kühlmittel.
  • \(\text{Bauplan}_1\): \(1 \times \text{Produkt}_2 \leftarrow 1 \times \text{Rohstoff}_0 + 1 \times \text{Rohstoff}_1\) für \(5\) Kühlmittel.

23 Einheiten Kühlmittel

Es ist zu beachten, dass während der Durchführung des Wettbewerbs die Standardeingabe von uns nicht geschlossen wird. Es sollte beim Einlesen der Daten also nicht auf ein EOF gewartet werden

Ausgabe

Die Ausgabe ist eine Liste von Bauplänen. Jeder Bauplan ist durch seine Position in der Liste eindeutig definiert.

Beispiel (Für die obige Eingabe)

[0,0,0,1]

\(3 \times \text{Bauplan}_0\) und \(1 \times \text{Bauplan}_1\)

[0,1,1,1,1]

\(1 \times \text{Bauplan}_0\) und \(4 \times \text{Bauplan}_1\)

Bewertung

Die Punktzahl ergibt sich aus dem Wert aller am Ende verfügbaren Produkte. “Ende” meint dabei je nach konkreter Situation das Ende des verfügbaren Kühlmittels oder das Ende der Produktionsanweisungen. Etwaige Zwischenstände während der Produktion spielen für die Bepunktung keine Rolle.

Beispiel (Für die obige Eingabe / Ausgaben)

Produktionsplan: [0,0,0,1]
Bestand Wert Summe
\(P_0\) \(P_1\) \(P_2\) \(W_0\) \(W_1\) \(W_2\)
Wert \(10\) \(12\) \(25\)
Initialbestand \(7\) \(3\) \(0\) \(70\) + \(36\) + \(0\) = \(106\)
1. \(\text{Bauplan}_0\) \(2 \times P_0 \rightarrow 1 \times P_1\) \(5\) \(4\) \(0\) \(50\) + \(48\) + \(0\) = \(98\)
2. \(\text{Bauplan}_0\) \(2 \times P_0 \rightarrow 1 \times P_1\) \(3\) \(5\) \(0\) \(30\) + \(60\) + \(0\) = \(90\)
3. \(\text{Bauplan}_0\) \(2 \times P_0 \rightarrow 1 \times P_1\) \(1\) \(6\) \(0\) \(10\) + \(72\) + \(0\) = \(82\)
4. \(\text{Bauplan}_1\) \(1 \times P_0 + 1 \times P_1 \rightarrow 1 \times P_2\) \(0\) \(5\) \(1\) \(0\) + \(60\) + \(25\) = \(85\)
Produktionsplan: [0,1,1,1,1]
Bestand Wert Summe
\(P_0\) \(P_1\) \(P_2\) \(W_0\) \(W_1\) \(W_2\)
Wert \(10\) \(12\) \(25\)
Initialbestand \(7\) \(3\) \(0\) \(70\) + \(36\) + \(0\) = \(106\)
1. \(\text{Bauplan}_0\) \(2 \times P_0 \rightarrow 1 \times P_1\) \(5\) \(4\) \(0\) \(50\) + \(48\) + \(0\) = \(98\)
2. \(\text{Bauplan}_1\) \(1 \times P_0 + 1 \times P_1 \rightarrow 1 \times P_2\) \(4\) \(3\) \(1\) \(40\) + \(36\) + \(25\) = \(101\)
3. \(\text{Bauplan}_1\) \(1 \times P_0 + 1 \times P_1 \rightarrow 1 \times P_2\) \(3\) \(2\) \(2\) \(30\) + \(24\) + \(50\) = \(104\)
4. \(\text{Bauplan}_1\) \(1 \times P_0 + 1 \times P_1 \rightarrow 1 \times P_2\) \(2\) \(1\) \(3\) \(20\) + \(12\) + \(75\) = \(107\)
5. \(\text{Bauplan}_1\) \(1 \times P_0 + 1 \times P_1 \rightarrow 1 \times P_2\) \(1\) \(0\) \(4\) \(10\) + \(0\) + \(100\) = \(110\)

Abfallprodukte

Eine Besonderheit bei der Bepunktung stellen Gegenstände mit negativen Werten dar. Die Werte dieser Gegenstände werden für jedes Produkt quadriert und dann drakonischerweise als Strafzahlung fällig. Gegeben sei dieses Mal als Beispiel das folgende Problem:

[ 5, 0,-5]
[ 0, 5, 0]
[([1],[0,2],1)]
5

Den geneigten Leser wird die manuelle Berechnung des optimalen Produktionsplans vermutlich nicht vor große Herausforderungen stellen … Zu Illustrationszwecken gehen wir aber mal von einem weniger optimalen Plan aus:

Produktionsplan: [0,0,0]
Bestand Wert Summe
\(P_0\) \(P_1\) \(P_2\) \(W_0\) \(W_1\) \(W_2\)
Wert \(5\) \(0\) \(-5\)
Initialbestand \(0\) \(5\) \(0\) \(0\) + \(0\) + \(0\) = \(0\)
1. \(\text{Bauplan}_0\) \(1 \times P_1 \rightarrow 1 \times P_0 + 1 \times P_2\) \(1\) \(4\) \(1\) \(5\) + \(0\) + \(-(5²)\) = \(-20\)
2. \(\text{Bauplan}_0\) \(1 \times P_1 \rightarrow 1 \times P_0 + 1 \times P_2\) \(2\) \(3\) \(2\) \(10\) + \(0\) + \(-(10²)\) = \(-90\)
3. \(\text{Bauplan}_0\) \(1 \times P_1 \rightarrow 1 \times P_0 + 1 \times P_2\) \(3\) \(2\) \(3\) \(15\) + \(0\) + \(-(15²)\) = \(-210\)
A strange game, the only winning move is not to play ...

Fehler

Sonstiges

Beispiele für Probleme

Im folgenden zeigen wir einige Konstellationen, die beim Shootout auf die ein oder andere Art und Weise auftreten könnten. Obendrein freuen wir uns natürlich auf Konstellationen, die wir nicht bedacht haben.

Produzierbare Rohstoffe

Einige Rohstoffe können möglicherweise mit nichts außer Kühlmitteleinsatz produziert werden.

[1,3]
[5,5]
[([],[0],1),([],[1],2)]
1414

Längere Produktionsketten

Das Produkt eines Bauplans kann selbstverständlich wieder als Rohstoff in einem anderen Bauplan eingehen.

[1,2,3]
[1,0,0]
[([0],[1],1),([1],[2],1)]
2

Runden mit ausschließlich produzierbaren Rohstoffen

Verlasst euch nicht darauf, dass in der Eingabe mindestens ein verfügbarer Rohstoff auftaucht, es könnten auch alle Anzahlen auf \(0\) stehen. In diesem Fall wird aber zumindest ein Rohstoff produzierbar sein.

Runden mit stark begrenzten Rohstoffen

Auch das Gegenteil ist aber möglicherweise der Fall: Die Anzahl der zur Verfügung stehenden Rohstoffe kann mit dem zur Verfügung stehenden Kühlmittel ohne Probleme vollständig verbraucht werden. Nachschub ist dabei nicht notwendigerweise gegebeben. In diesen Runden muss aus der begrenzten Menge das Beste gemacht werden.

Hilfsgüter, die bei der Produktion nicht verbraucht werden

Euch könnten Baupläne unterkommen, bei denen einige Rohstoffe in gleicher Menge ein- und ausgehen. Diese werden möglicherweise auch einen Wert von \(0\) haben. Ihr könnt euch diese Rohstoffe als Hilfsgüter vorstellen, die zwar einmalig produziert werden müssen, dann aber nie verschleißen.

[0, 5,20]
[1,10, 0]
[([0,1],[0,2],5)]
1337

Abfallprodukte

Bei einigen Bauplänen entstehen möglicherweise Abfallprodukte mit einem negativen Wert. Wenn ihr Glück habt können diese in einem weiteren Produktionsschritt zwar wieder entsorgt werden, eine Garantie besteht dafür aber nicht.

[ 0, 5,-10]
[10, 0,  0]
[([0],[1,2],1)]
3141

Unmögliche Baupläne

Einige Baupläne beziehen sich möglicherweise auf Rohstoffe, die nicht von Beginn an vorhanden waren und die sich auch nicht produzieren lassen. Diese Pläne können dann schlichtweg nicht sinnvoll verwendet werden.

[5,10]
[0, 0]
[([0],[1],1)]
2718

Zyklische Baupläne

Einige Baupläne verhalten sich in Bezug auf die Ein- und Ausgabe möglicherweise neutral. Sie kosten einfach nur Kühlmittel, ohne dass eine Wertschöpfung gegeben wäre.

[100]
[  1]
[([0],[0],1)]
42