WPC-Aufgabe (Programmierwettbewerb)

Jester

Hallo!

Ich habe mich mal wieder hingesetzt und mir dieses Mal zwei Aufgaben einfallen lassen. Eine Pro- und eine Expert-Aufgabe. Welche nun leichter und welche schwerer ist, darf jeder selbst entscheiden. Bitte seid so fair und nehmt nur an einer der beiden Programmieraufgaben teil.

------------------------------------------------------------------
Zuerst die Expert-Aufgabe:

Der Weihnachtsmann muß die Geschenke ausliefern. Dabei sind die Geschenke alle unterschiedlich schwer, von sehr leicht bis sehr schwer. Da in der Vorbereitungszeit alles etwas hektisch war, hat er die Geschenke einfach in der Reihenfolge des Eintreffens nebeneinander in einer langen Reihe in der Garage aufgestellt, so daß das letzte Geschenk am Garagenausgang steht. Jetzt kurz vor der Abfahrt, beim Beladen stellt er fest, es wäre günstiger für ihn, die Geschenke aufsteigend nach Gewicht zu sortieren, so daß das Schwerste direkt beim Garagenausgang steht. (Garagenausgänge sind immer rechts!)
Der Weihnachtsmann ist ein traditioneller Mensch und daher der Meinung, daß zum Sortieren keine neumodischen Tricks, wie zum Beispiel Hineinschieben eines Pakets an irgendeiner Stelle in der Reihe, verwendet werden sollten. Traditionellerweise wird folgendermaßen sortiert: In jedem Schritt tauschen zwei Geschenke den Platz. Will er also ein Geschenk mit dem Gewicht a und eins mit dem Gewicht b vertauschen, so muß er insgesamt ein Gewicht von a+b bewegen
Nun möchte der Weihnachtsmann die Geschenke sortieren und dabei insgesamt möglichst wenig Gewicht schleppen. Um sich mental auf die Aufgabe vorzubereiten, reicht es ihm zunächst zu wissen, wieviel Gewicht er insgesamt bewegen muß, um die Geschenke zu sortieren.

Hilf dem Weihnachtsmann und schreibe ein Programm, das eine Liste von Geschenkgewichten entgegennimmt und ausgibt, wieviele Gewichtseinheiten er mindestens schleppen muß, um die Geschenke in die korrekte Reihenfolge zu bringen. :xmas1:

Nochmal technisch:

Schreibe eine Funktion

typedef unsigned long long u64;
u64 wpc_expert(std::vector<unsigned int> const& weights);

Die Eingabe ist eine Liste von Zahlen. Die Zahlen soll durch Vertauschen von je zwei (nicht unbedingt benachbarten) Zahlen aufsteigend sortiert werden, dabei verursacht das Vertauschen zweier zahlen a,b die Kosten a+b. Die Rückgabe sollen die minimalen Kosten zum Sortieren der Zahlenfolge sein (maximales Minimum, es soll also wirklich möglich sein, mit diesen Kosten zu sortieren).

Wichtig: Es darf angenommen werden, daß alle Pakete unterschiedlich schwer sind!
Außerdem hat jedes Paket ein Gewicht echt größer als 0.

------------------------------------------------------------------
Nun die Pro-Aufgabe:

Gegeben ist folgender Code:

struct Point
{
  Point(double xc, double yc) : x(xc), y(yc) {}
  double x, y;
};

class Line
{
public:
  Line(Point const& startPoint, Point const& endPoint) : start(startPoint), end(endPoint)
  {}

  Point const& getStart() const { return start; }
  Point const& getEnd()   const { return end;   }

private:
  Point start, end;
};

Schreibe nun eine Funktion, die eine Liste von Strecken(Line) entgegennimmt und die Anzahl der Schnittpunkte ausgibt. Es kann angenommen werden, daß sich nie 3 oder mehr Strecken in einem einzigen Schnittpunkt treffen (eine Linie kann sich natürlich trotzdem mit mehreren anderen schneiden, nur nicht im selben Punkt). Außerdem wird die Mehrzahl der Strecken eher kurz sein.

Die Deklaration sieht folgendermaßen aus:

size_t wpc_pro(std::vector<Line> const& lines);

------------------------------------------------------------------

Und diesmal noch ein kleiner Kreativ-Wettbewerb:

Wer findet eine weihnachtliche Aufgabenstellung für die zweite Aufgabe?
Vorschläge bis zum 2. Weihnachtsfeiertag, 19:00 per Mail an mich.
Die lustigsten werde ich extra prämieren.

Die Lösungen zur Programmieraufgabe können bis Ende dieses Jahres eingereicht werden.
Ab 1.1. 0:00 wird nichts mehr entgegengenommen.

Bewertungskriterium ist bei beiden Programmieraugaben neben der Korrektheit vor allem die Geschwindigkeit auf Eingaben mittlerer Größe (also keine Spielzeigeingaben mit Größe 50, aber auch nicht riesige Eingaben von zig Millionen).

Einsendungen an Ignaz.Rutter@gmx.net mit wpc als Betreff.
Fragen einfach hier im Forum stellen. Bitte denkt daran, daß ihr nur an einer der beiden Aufgaben teilnehmen dürft.

Die Kreativ-Aufgabe läuft natürlich außer Konkurrenz. :xmas1:

Ich hoffe auf eine rege Teilnahme und wünsche allen, die sich damit beschäftigen viel Spaß dabei.

In diesem Sinne: Frohe Weihnachten :xmas1: :xmas2:
Jester

C++ Forumbot

Dieser Thread wurde von Moderator/in Jester aus dem Forum Neuigkeiten aus der realen Welt in das Forum Rund um die Programmierung verschoben.

Im Zweifelsfall bitte auch folgende Hinweise beachten:
C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?

Dieses Posting wurde automatisch erzeugt.

Jester schrieb:

Die Rückgabe sollen die minimalen Kosten zum Sortieren der Zahlenfolge sein (maximales Minimum, es soll also wirklich möglich sein, mit diesen Kosten zu sortieren).

Wie überprüfst du ob es möglich ist? Willst du die Sortierreihenfolge haben?

Mach mal das ganze Bla-Bla aus der Aufgabenstellung raus.

Jester

Ganz einfach, ich finde die minimalen Kosten, mit denen es möglich ist zu sortieren. Die vergleiche ich dann mit der Ausgabe von euren Lösungen. Wie ihr auf die Zahl gekommen seid ist mir eigentlich recht egal. Vielleicht gibt's ja ne Lösung, sogar ohne sortieren und so auskommt, keine Ahnung, ehrlich. Ich laß mich überraschen.

Jester

abstrakt schrieb:

Mach mal das ganze Bla-Bla aus der Aufgabenstellung raus.

Wenn Du's nicht schaffst das zu überlesen wirst Du es vermutlich auch nicht schaffen die Aufgabe zu lösen. :p

TomasRiker

Ist es erlaubt, für die Linien z.B. SSE oder 3DNow! zu verwenden?
Womit wird kompiliert?
Auf was für einem Rechner wird kompiliert?

Michael E.

Jester: Hast du schon eine Referenzimplementierung zur ersten Aufgabe? Wenn ja: Kannst du sie bitte zur Verfügung stellen?

groovemaster

Super Sache Jester, dem WPC neues Futter zu geben. Die Aufgabe klingt jedenfalls interessant.
:xmas1: :xmas2:

Jester

Ich werde die Einsendungen wohl mit dem vc8 kompilieren und testen. Die Einsendungen sollten standard-konform sein. Wir können natürlich wenn ihr wollt noch ne Sonderkategorie mit allen möglichen Tricks und Hacks aufmachen. Die Hauptauswertung möchte ich aber lieber auf standard-konformem Code machen.

MfG Jester

Jester

Michael E. schrieb:

Jester: Hast du schon eine Referenzimplementierung zur ersten Aufgabe? Wenn ja: Kannst du sie bitte zur Verfügung stellen?

Ich hab sie noch nicht implementiert. Aber ich werde sie auch auf keinen Fall zur Verfügung stellen. Die Aufgabe ist so gedacht, daß man was dran zu rätseln hat.

Wer weniger rätseln, sondern sich nur auf's implementieren beschränken will, ist möglicherweise bei der zweiten Aufgabe besser aufgehoben.

Sind alle Pakete unterschiedlich schwer oder gibt es gleich schwere?

Könnte man nicht

u64 wpc_expert(std::vector<unsigned int> const& weights);

statt

u64 wpc_expert(std::vector<unsigned int> const& gewichte);

schreiben.
Damit es nicht so denglisch ist.

Jester

In dem Code-Fetzen ist kein einziges deutsches Wort. Durch ändern des Variablennamens machst Du's also erst denglisch. Da aber der Name der Variablen nicht maßgeblich für die Signatur der Funktion ist kannst Du sie meinetwegen auch umbenennen.

edit:

sorry, hab's genau falsch rum verstanden. Hab die Aufgabenstellung entsprechend abgeändert.

Jester

Rund um die Programmierun schrieb:

Sind alle Pakete unterschiedlich schwer oder gibt es gleich schwere?

Hm, wenn alle unterschiedlich schwer sind, dann isses leichter, gell? Also gut, weil Weihnachten ist und weil die Aufgabe auch so noch einiges zu tun bietet würde ich sagen: Die Pakete sind alle unterschiedlich schwer.

Jester schrieb:

Bewertungskriterium ist bei beiden Programmieraugaben neben der Korrektheit vor allem die Geschwindigkeit auf Eingaben mittlerer Größe

Was genau bedeutet dieser Satz? Es ist doch schon so, dass Programme, die das falsche Ergebnis liefern, disqualifiziert werden oder zumindest eine erhebliche Strafe erhalten, oder?

Jester schrieb:

...Nochmal technisch:

Schreibe eine Funktion

[cpp]
typedef unsigned long long u64;
u64 wpc_expert(std::vector<unsigned int> const& gewichte);
[/cpp]
...

Jester schrieb:

In dem Code-Fetzen ist kein einziges deutsches Wort. Durch ändern des Variablennamens machst Du's also erst denglisch. Da aber der Name der Variablen nicht maßgeblich für die Signatur der Funktion ist kannst Du sie meinetwegen auch umbenennen.

Sicher???

Michael E.

Jester schrieb:

Michael E. schrieb:

Jester: Hast du schon eine Referenzimplementierung zur ersten Aufgabe? Wenn ja: Kannst du sie bitte zur Verfügung stellen?

Ich hab sie noch nicht implementiert. Aber ich werde sie auch auf keinen Fall zur Verfügung stellen. Die Aufgabe ist so gedacht, daß man was dran zu rätseln hat.

Ich mein ja auch nicht, dass du den Quellcode veröffentlichen sollst, sondern nur eine Möglichkeit geben solltest, zu überprüfen, ob man keine Kombinationen übersehen hat. Was nützen mir meine großartigsten Algorithmen, wenn ich simple Sachen übersehen habe?

@Michael E.:
Lass uns einfach Kosten-Werte austauschen, dann haben wir schon mal ne ziemliche Sicherheit.