Titelgrafik.

Inhalt

Ergebnisse des 5. OWINF

Dies sind die Ergebnisse des 5. OWINF vom 31.05.2008. Wir gratulieren allen Teilnehmern ganz herzlich zu Ihrem Erfolg.

 

Name abgabe rechner weltreise
Tamás Korodi
100
100
100
300
Dominik Reichl
100
95
100
295
Thomas Schöps
85
100
100
285
Hannes Jakschitsch
100
95
84
279
Philipp Weiß
75
100
100
275
Mathias Plichta
60
100
91
251
Sebastian Meßmer
50
75
81
206
Florian Barta
5
95
62
162
Sebastian Bayer
x
65
65
130
N.N.
x
70
39
109
N.N.
25
10
48
83
N.N.
20
x
59
79
N.N.
70
x
x
70
N.N.
x
x
68
68
N.N.
x
x
65
65
N.N.
45
15
0
60
N.N.
0
55
0
55
N.N.
x
15
0
15
N.N.
x
x
x
0
N.N.
x
x
x
0
N.N.
x
x
x
0
N.N.
x
x
x
0
N.N.
x
x
x
0
N.N.
x
x
x
0
N.N.
x
x
0
0
N.N.
x
0
0
0
N.N.
x
x
x
0
N.N.
x
x
x
0
N.N.
x
x
x
0
N.N.
x
x
x
0
N.N.
x
x
x
0
N.N.
x
x
x
0
N.N.
x
x
x
0
N.N.
x
x
x
0
N.N.
x
x
x
0
N.N.
x
x
x
0
N.N.
x
x
x
0
N.N.
x
x
x
0
N.N.
x
x
x
0
N.N.
x
x
x
0
 

Abgabe

Wie jedes Jahr ist es wieder so weit: Der Abgabetermin des BWInf naht und Elmo hat bis zuletzt an den Aufgaben gearbeitet. Um den richtigen Poststempel zu bekommen, muss er seine Einsendung aber noch möglichst schnell zur Post bringen. Weil Elmo in der BWInf-Newsgroup jedoch zu viel von seiner Lösung geschwärmt hat, versucht eine Gruppe von Konkurrenten, Elmo aufzuhalten. Dazu haben sich die Gegner in Gruppen aufgeteilt und an mehreren Kreuzungen postiert, die Elmo daher nicht passieren kann. Hilf Elmo, einen möglichst kurzen Weg zur nächsten Post zu finden. Die Länge ist dabei gleich der Anzahl der Straßen, aus denen der Weg besteht.

Elmos Stadt besitzt ein Straßennetz aus n Kreuzungen (2 ≤ n ≤ 50.000) und m Straßen (1 ≤ m ≤ 250.000). Die Kreuzungen sind von 1 bis n durchnummeriert. Elmo befindet sich zu Beginn an Kreuzung 1, die Post ist an Kreuzung n. Jede Straße verbindet zwei verschiedene Kreuzungen. Alle Straßen sind gleich lang und können von Elmo in beiden Richtungen benutzt werden. Zwischen zwei Kreuzungen gibt es höchstens eine Straße. Elmos Konkurrenten sind an l Kreuzungen (0 ≤ ln - 2) postiert, jedoch nie direkt bei Elmo oder der Post.

Dein Programm soll herausfinden, ob Elmo die Post erreichen kann. Wenn dies der Fall ist, muss auch die Länge des kürzesten Weges von Elmo zur Post berechnet werden.

Eingabe

Die erste Zeile der Eingabedatei abgabe.in besteht aus den drei Zahlen n, m und l.

Die folgenden m Zeilen beschreiben jeweils eine Straße. Eine Zeile besteht dabei aus zwei Zahlen, die für die beiden verbundenen Kreuzungen stehen.

Die anschließenden l Zeilen bestehen aus je einer Zahl, die eine blockierte Kreuzung bezeichnet.

Ausgabe

Die Ausgabedatei abgabe.out enthält genau eine Zeile. Wenn Elmo die Post nicht erreichen kann, besteht die Zeile aus dem Wort nein. Wenn es dagegen einen gültigen Weg gibt, steht in dieser Zeile eine positive, ganze Zahl, die der Länge des kürzesten Weges von Elmo zur Post entspricht.

Limits

Speicher: 32 MB
Laufzeit: 1 Sekunde
Programmiersprachen: C, C++, Pascal

Beispiele

abgabe.in abgabe.out
5 6 1 1 2 1 3 2 4 2 5 3 4 4 5 2 3
abgabe.in abgabe.out
5 6 2 1 2 1 3 2 4 2 5 3 4 4 5 2 4 nein
 ï»¿

Rechner

Auf Elmos Lieblingsfernsehsender kommen zu fortgeschrittener Stunde manchmal Quiz-Spiele, bei denen die Zuschauer durch sofortiges Anrufen und Nennen der Lösung unglaubliche Preise abstauben können. Am faszinierendsten findet Elmo das Spiel "Rechnen": dabei rast in Form einer Laufschrift eine in der Regel einfache aber lange mathematische Rechnung über den Bildschirm, deren Resultat die Lösung darstellt. "So schnell, wie man hier rechnen können soll kann ich höchstens tippen", denkt sich Elmo. Zahlreiche Versuche die mit einem Taschenrechner berechneten Ergebnisse gegen das Preisgeld einzutauschen scheitern! Elmo hatte vergessen, dass selbstverständlich Multiplikationen vor Strichrechnungen (Additionen und Subtraktionen) durchgeführt werden müssen. Ansonsten, so weiß Elmo, werden Rechnungen immer von links nach rechts berechnet. Hilf Elmo es diesmal richtig zu machen, um seine durch seltsam hohe Telefonkosten verursachten Schulden zu decken und ihm außerdem die Urlaubskasse für seine Weltreise zu füllen.

Da sich Elmo auch ab und zu vertippt, sollst du fehlerhafte Rechnungen erkennen. Dies sind Rechnungen, bei denen nicht immer genau ein Operator zwischen exakt zwei Zahlen steht.

Eingabe

Die Eingabedatei rechner.in enthält bis zu 300 Rechnungen, die jeweils in einer eigenen Zeile stehen. Abschließend befindet sich eine Zeile, in der sich lediglich eine Null ('0') statt einer Rechnung befindet. Jeder Rechnung besteht ausschließlich aus den Operatoren (Rechenzeichen) '+','-','*' sowie Operanden (Zahlen) 0 < N ≤ 1.000.000. Maximal treten pro Rechnung 1.000 Operatoren auf. Es kann davon ausgegangen werden, dass alle Zwischenergebnisse in ein vorzeichenbehaftetes 32 bit Integer passen.

Ausgabe

Deine Ausgabedatei rechner.out soll für jede Rechnung genau eine Zeile enthalten, in der sich das Resultat der Rechnung befindet. Fehlerhafte Rechnungen sollen statt des Ergebnisses FEHLER enthalten. Abschließend muss eine Zeile mit lediglich ENDE stehen.

Memory: 32 MB
Laufzeit: 1 Sekunde
Programmiersprachen: C, C++, Pascal

Beispiel 1

rechner.in rechner.out
100-2*33 194*34-4+48-23*10 23+73*-65 0 34 6410 FEHLER ENDE
 

Weltreise

Elmo geht auf Weltreise. Da es weltweit viele unterschiedliche Typen von Netzsteckern gibt, hat er sich einige Adapterstecker mitgenommen. Diese sind so konstruiert, dass man mehrere kombinieren kann; hat Elmo also beispielsweise einen Adapter, um Geräte mit einem deutschen Stecker in England zu verwenden und einen Adapter, um Geräte mit englischem Stecker in den USA zu verwenden, so kann er ein Gerät mit deutschen Stecker auch in den USA verwenden. Andererseits kann er diese beiden Adapter aber nicht kombinieren, um ein Gerät mit Stecker für die USA in Deutschland oder in England zu betreiben.

In Elmos Welt hat jedes Land einen anderen Typ von Netzstecker.

Hilf Elmo herauszufinden, ob er mit Hilfe seiner Adapter ein Gerät aus seinem Heimatland in einem fremden Land betreiben kann.

Eingabe

In der ersten Zeile der Eingabedatei weltreise.in steht genau eine ganze Zahl, die Anzahl C der Länder in Elmos Welt (2 ≤ C ≤ 50.000).

In der folgenden Zeile stehen genau zwei ganze Zahlen F und T (0 ≤ FC-1; 0 ≤ TC-1; FT). F steht hierbei für Elmos Heimatland, T steht für das Land in dem sich Elmo gerade befindet.

In der folgenden Zeile steht genau eine ganze Zahl N, die Anzahl der Adapterstecker, die Elmo im Gepäck hat (0 ≤ N ≤ 100.000).

Die folgenden N Zeilen enthalten jeweils genau zwei ganze Zahlen a und b (0 ≤ aC-1; 0 ≤ bC-1; ab), die durch ein Leerzeichen getrennt sind; je eine Zeile für jeden Adapterstecker, den Elmo im Gepäck hat. Die Zahlen a und b stehen für einen Adapterstecker, um ein Gerät aus Land a im Land b zu betreiben.

Ausgabe

Deine Ausgabedatei weltreise.out soll exakt eine Zeile mit einem Wort enthalten. ja, wenn Elmo das Gerät aus seinem Heimatland im Land T verwenden kann, nein sonst.

Limits

Memory: 16 MB
Laufzeit: 1 Sekunde
Programmiersprachen: C, C++, Pascal

Beispiel 1

weltreise.in weltreise.out
3 0 2 2 1 2 0 1 ja

Beispiel 2

weltreise.in weltreise.out
3 0 2 2 1 0 2 1 nein