Le mucche del fattore John adorano lanciare sassolini nel lago accanto al pascolo. Quando un sasso colpisce la superficie, genera un’onda che si propaga su di essa.
La superficie è una grande griglia di quadrati. La profondità di ogni quadrato dipende dall’interazione delle onde. Prima di lanciare sassi, ogni quadrato, tranne quelli delle rive originali del fiume, ha profondità 0. Si usa questa rappresentazione:
o: profondità minore di 0.-: profondità uguale a 0.*: profondità maggiore di 0.X: quadrato della riva originale del fiume.
Un sasso genera un’onda d’acqua sollevata che si espande a rombo, crescendo ogni secondo. La profondità di ogni quadrato sul rombo aumenta di 1 per un solo secondo. Due secondi dopo segue un’onda d’acqua abbassata, che riduce la profondità di 1 e si espande anch’essa a rombo. Ogni sasso causa solo due onde, prima sollevata e poi abbassata.
Per esempio, la figura mostra l’effetto di un sasso caduto al centro del lago dopo 0, 1, 2 e 3 secondi:
0 seconds 1 second 2 seconds 3 seconds ------- ------- ------- ---*--- ------- ------- ---*--- --*-*-- ------- ---*--- --*-*-- -*-o-*- ---*--- --*-*-- -*-o-*- *-o-o-* ------- ---*--- --*-*-- -*-o-*- ------- ------- ---*--- --*-*-- ------- ------- ------- ---*---
Le colonne da sinistra a destra corrispondono a 0, 1, 2 e 3 secondi.
Le rive hanno coordinate $x$ fisse e attraversano tutta la lunghezza del lago dall’alto in basso, con larghezza di un quadrato. Quando un’onda raggiunge una riva, non la attraversa: continua a crescere, ma la parte che colpisce la riva viene riflessa.
Sono mostrati i primi secondi di un’onda che colpisce una riva. Per chiarezza, la seconda onda d’acqua abbassata non è mostrata:
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*---*-
Le colonne da sinistra a destra corrispondono a 1, 2, 3, 4 e 5 secondi.
Quando parti delle onde si incontrano, non influenzano la propagazione reciproca. All’istante successivo cresceranno come se non ci fosse stato alcun incontro. Tuttavia i loro effetti sul lago si combinano. Per esempio:
1 second 2 seconds 3 seconds 4 seconds --------- --------- --------- ---*----- --------- --------- ---*----- --*-*-*-- --------- ---*----- --*-*-*-- -*-o-*-*- ---*----- --*-*-*-- -*-o-*-*- *-o-----* --*-*-*-- -*-o-*-*- *-o-----* -o-*-o--- ---*----- --*-*-*-- -*-o-*-*- *-o-----* --------- ---*----- --*-*-*-- -*-o-*-*- --------- --------- ---*----- --*-*-*-- --------- --------- --------- ---*-----
Le colonne da sinistra a destra corrispondono a 1, 2, 3 e 4 secondi.
Scrivi un programma per aiutare le mucche a capire come le onde si propagano nel tempo.
Input
Riga 1: quattro interi $P$, $B1$, $B2$, $R$, separati da spazi.
$P$ ($1 \le P \le 5$) indica il numero di sassi.
$B1$ ($-500{,}000 \le B1 \le 500{,}000$) e $B2$ ($-500{,}000 \le B2 \le 500{,}000$) sono le coordinate $x$ delle due rive.
$R$ ($1 \le R \le 500{,}000$) è l’istante in cui visualizzare il lago.
Due sassi non cadono nella stessa posizione allo stesso istante. Le rive hanno coordinate $x$ diverse e nessun sasso cade su una riva.
Righe $2..P+1$: tre interi separati da spazi descrivono un sasso: $X$ ($-500{,}000 \le X \le 500{,}000$), $Y$ ($-500{,}000 \le Y \le 500{,}000$) e $T$ ($1 \le T \le 500{,}000$).
$X$ e $Y$ sono le coordinate di caduta del sasso.
$T$ è l’istante della caduta.
Output
- Righe 1–9: una griglia $9 \times 9$ centrata in $(0,0)$. L’angolo inferiore sinistro rappresenta $(-4,-4)$ e quello superiore destro $(4,4)$. Deve rappresentare il lago all’istante $R$.
Esempi
Input 1
2 4 100 4 -3 0 1 0 0 2
Output 1
--------X -*------X *-*-*---X -o-*-*--X o-----*-X -o-*-*--X *-*-*---X -*------X --------X
Autore del problema: Richard Forster, BIO 2003, 2003