Les vaches du fermier John adorent jeter des cailloux dans le lac voisin de leur pâturage. Lorsqu’un caillou touche sa surface, il produit une vague qui s’y propage.
La surface est représentée par une grande grille de carrés. La profondeur de chaque carré dépend de l’interaction des vagues. Avant tout lancer, elle vaut 0 partout sauf sur les berges initiales de la rivière. Les carrés sont affichés ainsi :
o: profondeur inférieure à 0.-: profondeur égale à 0.*: profondeur supérieure à 0.X: carré appartenant à une berge initiale.
Un caillou produit une vague d’eau élevée se propageant en losange, qui grandit chaque seconde. La profondeur de chaque carré du losange augmente de 1 pendant une seule seconde. Deux secondes après suit une vague d’eau abaissée, réduisant la profondeur de 1, également en losange. Chaque caillou ne produit que deux vagues, élevée puis abaissée.
Par exemple, voici l’effet d’un caillou tombé au milieu du lac, 0, 1, 2 et 3 secondes après sa chute :
0 seconds 1 second 2 seconds 3 seconds ------- ------- ------- ---*--- ------- ------- ---*--- --*-*-- ------- ---*--- --*-*-- -*-o-*- ---*--- --*-*-- -*-o-*- *-o-o-* ------- ---*--- --*-*-- -*-o-*- ------- ------- ---*--- --*-*-- ------- ------- ------- ---*---
Les colonnes correspondent de gauche à droite à 0, 1, 2 et 3 secondes.
Les berges ont des coordonnées $x$ fixes et parcourent toute la longueur du lac, de haut en bas, sur un carré de largeur. Une vague qui atteint une berge ne la traverse pas : elle continue de grandir, mais la partie qui heurte la berge est réfléchie.
Voici les premières secondes d’une vague heurtant une berge. Pour la clarté du dessin, la seconde vague d’eau abaissée est omise :
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*---*-
Les colonnes correspondent de gauche à droite à 1, 2, 3, 4 et 5 secondes.
Lorsque des parties de vagues se rencontrent, elles ne modifient pas leur propagation respective. Au prochain instant, elles grandissent comme si elles ne s’étaient pas rencontrées. Leurs effets sur le lac se combinent néanmoins. Par exemple :
1 second 2 seconds 3 seconds 4 seconds --------- --------- --------- ---*----- --------- --------- ---*----- --*-*-*-- --------- ---*----- --*-*-*-- -*-o-*-*- ---*----- --*-*-*-- -*-o-*-*- *-o-----* --*-*-*-- -*-o-*-*- *-o-----* -o-*-o--- ---*----- --*-*-*-- -*-o-*-*- *-o-----* --------- ---*----- --*-*-*-- -*-o-*-*- --------- --------- ---*----- --*-*-*-- --------- --------- --------- ---*-----
Les colonnes correspondent de gauche à droite à 1, 2, 3 et 4 secondes.
Écrivez un programme aidant les vaches à déterminer la propagation des vagues au fil du temps.
Entrée
Ligne 1 : quatre entiers $P$, $B1$, $B2$, $R$, séparés par des espaces.
$P$ ($1 \le P \le 5$) indique le nombre de cailloux.
$B1$ ($-500{,}000 \le B1 \le 500{,}000$) et $B2$ ($-500{,}000 \le B2 \le 500{,}000$) sont les coordonnées $x$ des deux berges.
$R$ ($1 \le R \le 500{,}000$) est l’instant auquel afficher le lac.
Deux cailloux ne tombent jamais au même endroit au même instant. Les berges ont des coordonnées $x$ différentes, et aucun caillou ne tombe sur une berge.
Lignes $2..P+1$ : trois entiers séparés par des espaces décrivant un caillou : $X$ ($-500{,}000 \le X \le 500{,}000$), $Y$ ($-500{,}000 \le Y \le 500{,}000$) et $T$ ($1 \le T \le 500{,}000$).
$X$ et $Y$ sont les coordonnées de chute du caillou.
$T$ est l’instant de sa chute.
Sortie
- Lignes 1 à 9 : affichez une grille $9 \times 9$ centrée en $(0,0)$. Le coin inférieur gauche représente $(-4,-4)$ et le supérieur droit $(4,4)$. Elle doit représenter le lac à l’instant $R$.
Exemples
Entrée 1
2 4 100 4 -3 0 1 0 0 2
Sortie 1
--------X -*------X *-*-*---X -o-*-*--X o-----*-X -o-*-*--X *-*-*---X -*------X --------X
Auteur du problème : Richard Forster, BIO 2003, 2003