Es war einmal ein Kind namens Kino, das sehr gerne reiste und schon viele seltsame Orte besucht hatte. Eines Tages kam Kino an eine große Brücke und entdeckte darauf viele Cabrios. Leider war die Brücke so schmal, dass nebeneinander nur ein einziges Cabrio Platz hatte. Da die Autos auf der Brücke einander nicht auswichen, blockierten sich die aus beiden Richtungen kommenden Fahrzeuge gegenseitig.
Später baute der Erbauer eine neue Funktion in die Brücke ein: Ein Abschnitt der Brücke konnte um $180$ Grad gedreht werden, sodass sich die Fahrtrichtung der Cabrios auf diesem Abschnitt umkehrte, wie in der folgenden Abbildung:
Abbildung 1. Durch Drehen wird aus der Cabriofolge 321 die Folge 123.
Wie oben gezeigt, entsteht ein Stau, wenn die Cabrios $3,2,1$ auf der Brücke auf die Cabrios $4,5$ treffen. Drehen wir nun den Abschnitt mit $3,2,1$, ergibt sich auf der Brücke die Reihenfolge $1,2,3,4,5$, wobei alle Fahrzeuge dieselbe Fahrtrichtung haben und von der Brücke fahren können. Dies ist natürlich nur ein einfaches Beispiel. Auf der wirklichen Brücke ist die Situation viel komplizierter; es sind mehrere Drehungen nötig, um eine Folge der Form $1,2,3,4,5$ zu erhalten.
Doch nachdem der Konstrukteur die Brücke entworfen hatte, ging auch er auf Reisen. Niemand unter den übrigen Einwohnern konnte die wundersame Brücke bedienen. So wurde das Durcheinander auf der Brücke immer größer, bis eines Tages die heutige Situation entstand. Um die Brücke überqueren zu können, fand Kino am Brückenrand das Steuergerät und die Anleitung und entdeckte so wieder, wie man die Brücke bedient. Mit Hilfe der Anwohner gelang es Kino, die Cabrios auf der Brücke in die Reihenfolge $1,2,3,\ldots$ zu bringen, wobei alle in dieselbe Richtung zeigten. Weißt du, wie Kino das gemacht hat?
Eingabe
Dies ist eine Aufgabe, bei der nur Ausgabedateien abgegeben werden. Die Eingabedateien convertible1.in bis convertible10.in liegen bereits im Benutzerverzeichnis. Die erste Zeile einer Eingabedatei enthält die Anzahl $n$ der Cabrios auf der Brücke. Die Cabrios sind mit $1,2,\ldots,n$ nummeriert. Die zweite Zeile beschreibt ihre Positionen und Fahrtrichtungen als Folge von $+i$ oder $-i$. Steht an der $j$-ten Position $-i$, so befindet sich an der $j$-ten Position der Brücke das Cabrio $i$ mit Fahrtrichtung nach rechts. Steht dort $+i$, so befindet sich dort das Cabrio $i$ mit Fahrtrichtung nach links.
Ausgabe
Lege die Ausgabedateien convertible1.out bis convertible10.out im Benutzerverzeichnis ab; ein Programm musst du nicht abgeben. Die erste Zeile einer Ausgabedatei enthält die Anzahl $m$ der Drehungen. Jede der folgenden $m$ Zeilen beschreibt eine Drehung durch die Position der linken und der rechten Grenze. Deine Ausgabe muss sicherstellen, dass die endgültige Folge $1,2,3,\ldots,n$ ist und nicht $-1,-2,-3,\ldots,-n$ oder irgendeine andere Folge.
Beispiele
Eingabe 1
5 -3 -2 -1 4 5
Ausgabe 1
1 1 3
Teilaufgaben
Für jeden Test gibt es höchstens $10$ Punkte. Die erreichte Punktzahl hängt vom Verhältnis der Güte deiner Lösung zu der der Referenzlösung ab.
So testest du dein Programm
Für diese Aufgabe wird das Prüfprogramm convertible_c für Ausgabedateien bereitgestellt. Es wird folgendermaßen ausgeführt:
#./convertible_c 3
Damit wird geprüft, ob convertible3.out gültig ist.