Erste Runde 2013

Resultate der Ersten Runde

Die folgenden Teilnehmer haben sich für die zweite Runde qualifiziert:

Rang Teilehmer Punkte (max: 60)
1. Timo Bräm 47.5
2. Johannes Kapfhammer 44.5
3. Florian Schroeder 42.5
3. Peter Müller 42.5
5. Timon Stampfli 42
6. Benjamin Schmid 41
7. Fabian Lyck 40.5
8. Cédric Neukom 38.5
9. Lukas Roth 33.5
10. Pascal Sommer 31.5
10. Sander Staal 31.5
12. Stephan Leuch 30.5
13. Cedric Münger 29
13. Lorenz Brun 29
13. Thomas Käser 29
16. Viviane Kehl 24
17. Raphael Appenzeller 20
18. Jean-Marie Bise 19
19. Filip Vucelic 17.5
20. Ruben Jungius 14
21. Andrina Denzler 13
21. Florian Wernli 13
23. Cyrill Künzi 12
23. Luc Haller 12
25. Elias Boschung 11.5
26. Michael Aerni 10
27. Marcel Würsten
28. Philipp Muggli
29. Patrick Eigensatz

Für die erste Runde der SOI 2013 haben wir 6 knifflige Aufgaben entworfen. Es gibt verschiedene Arten von Aufgaben. Drei der Aufgaben sind praktisch: Du sollst zu diesen Aufgaben ein komplettes Programm entwickeln, welches die Aufgabe löst, und den Quelltext einschicken. Bei den zwei theoretischen Aufgaben liegt das Augenmerk auf den mathematischen Aspekten, die mit logischen Überlegungen analysiert werden um anschliessend einen Lösungsansatz in Worte zu fassen. Die letzte Aufgabe ist die Kreativaufgabe, wo es darum geht ein Programm zu entwickeln, welches interaktiv gegen die Programme der anderen Teilnehmer antritt. Die Aufgabe ist so gewählt, dass sie nicht optimal gelöst werden kann. Allerdings gibt bereits ein einfaches Programm Punkte.

Die Aufgabenstellungen gibt es hier auf der Webseite.

Aufgabe Typus
Uhren praktisch
Zwei Tische praktisch
Fingersatz praktisch
Code-Analyse theoretisch
Bankomat theoretisch
Wer wird Milliardär? kreativ

Einsendungen und Bewertung

Am besten verwendest du das Upload-Formular, das bei den jeweiligen Aufgaben verlinkt ist, um deine Lösungen einzuschicken. Als Einsendung sollst du entweder die Datei mit der Lösung direkt abgeben, oder falls sie aus mehreren Dateien besteht, als Archiv einsenden.

Wichtig: Stelle sicher, dass im Profil deine Rolle auf 'Participant' gesetzt ist, so dass du einsenden kannst.

Falls du Probleme beim Einsenden hast, kannst du deine Lösungen auch direkt per e-mail an round1@soi.ch senden (schreibe in diesem Fall umbedingt deinen vollen Namen und SOI-Loginname). Wichtig: Wir werden in diesem Fall deine Einsendung bestätigen. Solltest du also keine Bestätigung erhalten, versuche erneut einzusenden.

Alle Aufgaben haben für die Bewertung dasselbe Gewicht.

Praktische Aufgaben

Als Einsendung sollst du den Quelltext abgeben.

Sende bitte keine kompilierten Programme, sondern lediglich den Programmcode. Wir werden kompilierte Programme nicht ausführen. Versuche dich nach Möglichkeit auf nur eine Quelltextdatei zu beschränken um Übersicht und Kompilieren nicht zusätzlich zu komplizieren. Deine Quelltextdatei sollte einige Kopfzeilen enthalten mit den folgenden Informationen: Gelöste Aufgabe, Programmiersprache, Username.

Beispiel in C++:

/*
  Task: sample
  Lang: C++
  User: chuck
*/
Anweisungen
  • Gib keinen Text aus, der nicht in der Aufgabenstellung verlangt wird. Wenn du Dinge ausgibst wie «Bitte jetzt W und H eingeben: », wirst du Punkte verlieren!
  • Anstatt die ganze Eingabe von Hand einzugeben, kannst du deinem Programm eine Eingabedatei zum Einlesen geben. Gib in einem Terminal meinprogramm < meineeingabedatei.txt ein. Dein Programm wird sich so verhalten, als ob du alle Werte in der Datei meineeingabedatei.txt von Hand eingegeben hättest. Bemerkung: Datei-Umleitung mit «<» funktioniert auf jedem Linux-ähnlichen System, aber auf Mac und Windows. Das Windows-Terminal heisst «Command Promt» oder «Eingabeaufforderung».
  • Verwende long long int korrekt, wenn es nötig ist:
      int w,h;
      scanf("%d %d", &w, &h);
      long long int area = w * (long long int)h;
      printf("%lld", area);
  • Teste dein Programm, bevor du es einschickst (auch mit grossen Test-Dateien, erstelle auch deine eigenen Test-Dateien).
  • Falls du irgendwelche Fragen hast, oder falls du die obenstehenden Erklärungen nicht verstehst, zögere nicht, Fragen im Forum zu stellen. Falls dir etwas nicht klar ist, bist du damit bestimmt nicht allein!
Bewertung

Ein Programm, das alle unsere Testfälle innerhalb der Zeitlimite (einige Sekunden) korrekt löst, erhält die maximale Punktzahl. Diese Testfälle sind nicht öffentlich und du kannst dein Programm vorher nicht auf ihnen ausprobieren.

Bei der Zeitbeschränkung geht es um die asymptotische Laufzeitkomplexität deines Programms. Das heisst, du solltest die Laufzeit von Monaten auf Sekunden optimieren, nicht aber von 5s auf 3s. Des Weiteren bist du frei, wie viel Speicher du beanspruchst, solange es in einem vertretbaren Rahmen bleibt (so ca. 100MB).

Falls dein Programm schnell und korrekt ist, bekommst du die maximale Punktzahl. Für ein korrektes aber langsames Programm verteilen wir Teilpunkte (je nachdem wie langsam dein Programm ist) Ein schnelles aber (teilweise) falsches Programm wird (fast) keine Punkte erzielen.

Theoretische Aufgaben

Wir haben eine kleine Hilfestellung zusammengestellt, solltest du dich fragen, wie eine perfekte Lösung einer theoretischen Aufgabe aussieht. Schick uns deine Lösung auf jeden Fall auch wenn sie sich nicht genau an diese Richtlinie hält, du kannst auch dann noch viele Punkte erreichen.

Du kannst die Lösungen als Plaintext, PDF, Postscript, OpenOffice-Dokument, Word-Dokument oder als gescanntes Bild senden.

Bewertung

Deine Lösung wird zur Bewertung auf Korrektheit und Vollständigkeit überprüft. Für die volle Punktzahl sind Quelltext (das kann auch Pseudocode sein) und eine Beschreibung der optimalen Lösung, ein «Korrektheitsbeweis» sowie eine Abschätzung der Zeit- und Speicherkomplexität nötig. Weitere Informationen zu diesen Punkten findest du in den oben verlinkten HowTo Dateien.

Kreativaufgabe

Als Einsendung sollst du den Quelltext abgeben.

Bewertung

Punkte werden im Kreativaufgaben-Turnier am SOI-Tag anhand der Rangliste verteilt. (Der SOI-Tag findet am 12. Januar 2013 statt)