Die Qualifikationsrunde in Python lösen

Eingabe

Die Eingabe entspricht so ziemlich dem Standardgerüst, dem die meisten Aufgaben folgen:

Auf der ersten Zeile steht die Zahl $T$, die Anzahl Seilbahnen, die Stofl bauen möchte. Für jede dieser Seilbahnen folgt dann eine Beschreibung der Masten, die folgendermassen aufgebaut ist: Auf der ersten Zeile steht eine Zahl $N$, die Anzahl der Masten und auf der zweiten Zeile stehen $N$ ganze Zahlen, die Höhen $h_i$ der Masten.

Formal entspricht das folgendem Muster:

T
N
h1 h2 h3 ... hN
N
h1 h2 ... hN
N
h1 h2 h3 h4 ... hN
...

Oder konkret am Beispiel:

3
3
3 5 7
4
20 15 10 5
8
1 2 3 4 5 6 7 9

Die einfachste Möglichkeit, um etwas in Python zu lesen, ist input(). Die Funktion liest eine Zeile auf der Standardeingabe und gibt eine Zeichenkette (String) zurück. In der Eingabe oben hätte der erste Aufruf von input() den Rückgabewert "3", der zweite wieder "3", dann "3 5 7", dann "4", dann "20 15 10 5", usw.

Mit Zeichenketten können wir aber wenig anfangen. Schliesslich wollen wir mit Zahlen arbeiten. In Python geht das mit dem Konstruktor von int. Dieser nimmt eine Zeichenkette entgegen und wandelt sie in einen int um. So ist int("3") gleich 3, genau das, was wir wollen.

Damit haben wir schon einen ersten Teil:

T = int(input())
for testcase in range(T):
    N = int(input())
    h = input()  # ???
    answer = "TODO"
    print(f"Case #{testcase}: {answer}")

(Mehr zu der Zeile mit dem print später, es geht zunächst primär um die Eingabe.)

Lassen wir dieses Programm mit obiger Eingabe laufen, erhalten wir:

Case #0: TODO
Case #1: TODO
Case #2: TODO

Das sieht schonmal ganz gut aus.

Die nächste Schwierigkeit ist es, N Zahlen einzulesen, die noch dazu alle auf einer Zeile sind. Da hilft uns die split()-Funktion, welche an Leerzeichen auftrennt. "20 15 10 5".split() gibt ['20', '15', '10', '5'] zurück. Wir sind schon fast da! Die Elemente sind aber noch Zeichenketten, keine Zahlen. Wir müssen noch irgendwie int darauf anwenden.

Da gibt es mehrere Möglichkeiten. Die erste ist mit einer Schleife:

h = []
for x in input().split():
    h.append(int(x))

Hier gehen wir über jedes Element in input().split(). In jedem Durchgang wandeln wir es in einen int um und fügen es der Liste h an.

Falls du List-Comprehensions kennst, geht es damit kürzer:

h = [int(x) for x in input().split()]

Im Grunde passiert hier das gleiche, nur ist die Schleife versteckt in der Definition der Liste.

Es geht aber noch ein ganz wenig kürzer:

h = list(map(int, input().split()))

map(func, list) wendet die Funktion func auf jedes Element an, ist also im Grund genommen [func(x) for x in list]. map gibt aber keine Liste zurück, sondern einen Iterator. Das kann nützlich sein, wenn man nicht alle Elemente benötigt oder nur einmal darüber geht. Wir wollen aber eine Liste, deshalb wandeln wir es in eine Liste um.

Damit wären wir fertig:

T = int(input())
for testcase in range(T):
    N = int(input())
    h = list(map(int, input().split()))
    answer = "TODO""
    print(f"Case #{testcase}: {answer}")

Ausgabe

Die Ausgabe schreibt man am einfachsten mit der Funktion print. print erwartet aber eine Zeichenkette, wir wollen aber "Case #i: answer" schreiben, wobei i der Testfall und answer die Lösung ist.

Es gibt 4 Arten in Python, Zeichenketten zu formatieren:

• Manuell:

  print("Case #" + str(testcase) + ": " + answer)
  

• Mit dem Interpolationsoperator %:

  print("Case #%d: %s" % (testcase, answer))
  

• Mit .format:

  print("Case #{}: {}".format(testcase, answer))
  

• Mit Literal String Interpolation (ab Python 3.6):

  print(f"Case #{testcase}: {answer}")
  

Wir empfehlen die letzte Variante, da sie für Variablen am übersichtlichsten ist. Ist dein Python-Interpreter nicht neu genug, kann es sein, dass er einen Fehler ausspuckt. In diesem Fall empfehlen wir, auf .format zurückzugreifen.

Editor + Konsole

Die einfachste Kombination ist es, die Funktionen von oben in einem Editor (Emacs, Vim, Sublime, Notepad++) zu schreiben und in der Konsole auszuführen. In vielen Editoren geht das sogar direkt im Editor (als Compile-Command).

Dazu erstellst du am besten pro Aufgabe einen Ordner, schreibst den Code und legst darin die Testdaten ab (sample.in).

Ausführen geht per Konsole:

$ python cablecar-sub2.py <sample.in
Case #0: yes
Case #1: yes
Case #2: no
$ python cablecar-sub2.py <cablecar-sub1.in >cablecar-sub1.out

Je nach System musst du python3 schreiben. Du kannst deine Python-Version wiefolgt herausfinden:

$ python --version
Python 3.6.5

Steht in der Ausgabe “Python 2.7.15” (oder irgendetwas mit 2.X), musst du explizit python3 schreiben.

PyCharm und andere IDEs

Falls es deine IDE nicht unterstützt, die Eingabe umzuleiten, empfehlen wir dir, die Datei von Python aus zu lesen.

Dazu muss du folgende Änderungen vornehmen:

def main():
    # Eingabe/Ausgabe umlenken
    sys.stdin = open("sample.in", "r")
    sys.stdout = open("sample.out", "w")

    # der Rest gleich wie bisher
    for i in range(int(input())):
        print(f"Case #{i}: {display(solve(*parse()))}")

Möchtest du die Ausgabe sehen, kannst du sys.stdout = open("sample.out", "w") einfach auskommentieren.

Jupyter Notebook

Ein Jupyter-Notebook hat den Vorteil, dass man die Funktion direkt testen kann.

In [..]:  solve(3, [3,5,7])
Out[..]:  True
In [..]:  solve(4, [20, 15, 10, 5])
Out[..]:  True
In [..]:  solve(8, [1, 2, 3, 4, 5, 6, 7, 9])
Out[..]:  False

Das macht es einfach, auch grosse Eingaben zu testen:

In [..]:  solve(10000, [42]*10000)
Out[..]:  True

Das Ausführen an den Testdaten wird dafür etwas komplizierter. Zum Testen kann man natürlich main() aufrufen und die Eingabe manuell schreiben. Mit der Zeit wird das aber mühsam, deshalb wollen die Eingabe und Ausgabe umleiten. Würden wir das aber wie im Abschnitt über PyCharm und andere IDEs machen, wäre nachher input() und print(...) “kaputt” und man müsste den Jupyter-Kernel neustarten.

Stattdessen können wir eine Funktion run schreiben:

import sys
def run(infile, outfile):
    global input, print
    old_input = input  # save original input function
    old_print = print  # save original print function
    try:
        with open(infile, "r") as inp, open(outfile, "w") as outp:
            input = inp.readline                       # now input reads from a inp
            def print(*args, **kwargs):                # define a special print
                old_print(*args, **kwargs, file=outp)  # write to output file
                old_print(*args, **kwargs)             # and also show it in jupyter
            main()
    finally:
        input = old_input  # restore input
        print = old_print  # restore print

Um es auszuführen, müssen wir noch die Dateipfade angeben:

run("sample.in", "sample.out")

Falls “sample.in” nicht im aktuellen Verzeichnis liegt, muss der ganze Pfad angegeben werden.