Farmer Johns Kühe werfen äußerst gern Kieselsteine in den See neben ihrer Weide. Trifft ein Stein auf die Wasseroberfläche, erzeugt er eine Welle, die sich über sie ausbreitet.
Die Seeoberfläche wird als großes Raster aus Quadraten dargestellt. Die Wassertiefe jedes Quadrats ergibt sich aus dem Zusammenwirken der Wellen. Vor dem ersten Stein hat jedes Quadrat außer den ursprünglichen Flussufern die Tiefe 0. Die Darstellung lautet:
o: Tiefe kleiner als 0.-: Tiefe gleich 0.*: Tiefe größer als 0.X: Quadrat des ursprünglichen Flussufers.
Ein Stein erzeugt eine Welle erhöhten Wassers, die sich als jede Sekunde wachsende Raute ausbreitet. Die Tiefe jedes Quadrats auf der Raute steigt um 1, für genau eine Sekunde. Zwei Sekunden später folgt eine Welle abgesenkten Wassers, die die Tiefe um 1 vermindert und sich ebenfalls rautenförmig ausbreitet. Jeder Stein erzeugt nur diese zwei Wellen, zuerst erhöhtes, dann abgesenktes Wasser.
Das folgende Bild zeigt beispielsweise die Wirkung eines Steins in der Seemitte 0, 1, 2 und 3 Sekunden nach seinem Fall:
0 seconds 1 second 2 seconds 3 seconds ------- ------- ------- ---*--- ------- ------- ---*--- --*-*-- ------- ---*--- --*-*-- -*-o-*- ---*--- --*-*-- -*-o-*- *-o-o-* ------- ---*--- --*-*-- -*-o-*- ------- ------- ---*--- --*-*-- ------- ------- ------- ---*---
Die Spalten stehen von links nach rechts für 0, 1, 2 und 3 Sekunden.
Die Ufer haben feste $x$-Koordinaten und verlaufen über die gesamte Länge des Sees von oben nach unten, bei einer Breite von einem Quadrat. Erreicht eine Welle ein Ufer, läuft sie nicht hindurch: Sie wächst weiter, aber der auf das Ufer treffende Teil wird reflektiert.
Hier sind die ersten Sekunden einer Welle an einem Ufer gezeigt. Zur besseren Übersicht fehlt die zweite Welle abgesenkten Wassers:
1 second 2 seconds 3 seconds 4 seconds 5 seconds X------ X------ X--*--- X-*-*-- X*---*- X------ X--*--- X-*-*-- X*---*- X*----* X--*--- X-*-*-- X*---*- X*----* X-*---- X-*-*-- X*---*- X*----* X-*---- X--*--- X--*--- X-*-*-- X*---*- X*----* X-*---- X------ X--*--- X-*-*-- X*---*- X*----* X------ X------ X--*--- X-*-*-- X*---*-
Die Spalten stehen von links nach rechts für 1, 2, 3, 4 und 5 Sekunden.
Treffen Teile von Wellen aufeinander, beeinflussen sie ihre gegenseitige Ausbreitung nicht. Beim nächsten Zeittakt wachsen sie, als hätte es kein Treffen gegeben. Ihre Wirkungen auf den See werden jedoch kombiniert. Zum Beispiel:
1 second 2 seconds 3 seconds 4 seconds --------- --------- --------- ---*----- --------- --------- ---*----- --*-*-*-- --------- ---*----- --*-*-*-- -*-o-*-*- ---*----- --*-*-*-- -*-o-*-*- *-o-----* --*-*-*-- -*-o-*-*- *-o-----* -o-*-o--- ---*----- --*-*-*-- -*-o-*-*- *-o-----* --------- ---*----- --*-*-*-- -*-o-*-*- --------- --------- ---*----- --*-*-*-- --------- --------- --------- ---*-----
Die Spalten stehen von links nach rechts für 1, 2, 3 und 4 Sekunden.
Schreibe ein Programm, das den Kühen zeigt, wie sich die Wellen im Laufe der Zeit ausbreiten.
Eingabe
Zeile 1: Vier durch Leerzeichen getrennte ganze Zahlen $P$, $B1$, $B2$, $R$.
$P$ ($1 \le P \le 5$) ist die Anzahl Kieselsteine.
$B1$ ($-500{,}000 \le B1 \le 500{,}000$) und $B2$ ($-500{,}000 \le B2 \le 500{,}000$) sind die $x$-Koordinaten der beiden Ufer.
$R$ ($1 \le R \le 500{,}000$) ist der Zeitpunkt, zu dem der See dargestellt werden soll.
Keine zwei Steine fallen gleichzeitig an dieselbe Position. Die Ufer haben verschiedene $x$-Koordinaten, und kein Stein fällt auf ein Ufer.
Zeilen $2..P+1$: Jeweils drei durch Leerzeichen getrennte ganze Zahlen beschreiben einen Stein: $X$ ($-500{,}000 \le X \le 500{,}000$), $Y$ ($-500{,}000 \le Y \le 500{,}000$) und $T$ ($1 \le T \le 500{,}000$).
$X$ und $Y$ sind die Koordinaten, an denen der Stein fällt.
$T$ ist der Zeitpunkt seines Falls.
Ausgabe
- Zeilen 1 bis 9: Ein $9 \times 9$-Raster mit Mittelpunkt $(0,0)$. Unten links liegt $(-4,-4)$, oben rechts $(4,4)$. Es soll den Zustand des Sees zum Zeitpunkt $R$ zeigen.
Beispiele
Eingabe 1
2 4 100 4 -3 0 1 0 0 2
Ausgabe 1
--------X -*------X *-*-*---X -o-*-*--X o-----*-X -o-*-*--X *-*-*---X -*------X --------X
Autor der Aufgabe: Richard Forster, BIO 2003, 2003