Allgemeine Herangehensweise an Programming Contest Probleme

• Aufgabenstellung lesen (nee, wirklich!)
• Schwierigkeit einschätzen (1 - 10. 1 ist Easy, 10 ist verdammt schwer)
• Entscheiden, ob man die Aufgabe bearbeiten möchte.
  • Bei ja, sich auf dem Sign-Up-Sheet für die Aufgabe eintragen. Weiter mit dem nächsten Punkt.
  • Bei nein, nächste Aufgabe ansehen. Zurück zum Anfang.
• Eingabe-Daten in Pakete zerlegen, die man vollständig einlesen muss, bevor man weitermachen kann. Hier sollte man v.a. darauf achten nicht unnötig Daten zwischenzuspeichern, wenn man sie auch direkt on-the-fly in eine Lösung verwandeln hätte können.

Beispiel: Summe von n Zahlen. Eingabe kommt in Sets von n+1 Zahlen. Die erste Zahl ist n, dann folgen n+1 Zahlen, auszugeben ist die Summe.

Eingabe zerlegen:

• Sets
  • Zahl n
  • n Zahlen → Brauchen wir nicht zu speichern, können wir on-the-fly zur Lösung machen:

do { // Do Schleife bearbeitet Sets.
  int n = (int)in();
  if (n==0)
    exit();
  int sum = 0;
  for (int i = 0; i < n; i++){
    sum += (int)in(); // Es hätte keinen Sinn gemacht die Daten hier zu speichern.
  }
} while (true);

• Pakete bearbeiten
• Lösung ausgeben.

Comments