|Online Judge||Problem Set||Authors||Online Contests||User|
Farmer John's cows thoroughly enjoy throwing pebbles into the lake next to their grazing field. When a pebble hits the surface of the lake, it generates a wave that propagates across the surface of the lake.
The surface of the lake is represented by a large grid of squares. The water at each square is at some depth, which is determined by the interaction of the waves. Before any pebbles are dropped, every square (except those on the original river banks) has a depth of 0. When displayed, each square will be represented as follows:
o Square has a depth < 0
When a pebble in dropped into the lake it causes a wave of raised water to spread out in a diamond pattern that grows every second. The depth of each square in the diamond is increased by 1 for just one single second. This wave is followed two seconds later by a wave of lowered water (depth decreased by 1) which also spreads out as a diamond. Each pebble causes only two waves, the raised wave followed by the lowered wave.
For example, the diagram below shows the effect of a pebble dropped in the middle of the lake at time intervals of 0, 1, 2 and 3 seconds:
after it is dropped:
0 seconds 1 second 2 seconds 3 seconds
The river banks have fixed x co-ordinates and run for the entire length (top to bottom) of the lake with a width of a single square. When a wave reaches a river bank, rather than carrying on, it continues to grow but the part that hits the bank is reflected.
The early seconds of a wave hitting one of the river banks are shown below. To make the picture clearer, the second wave of lowered water is not shown:
1 second 2 seconds 3 seconds 4 seconds 5 seconds
When sections of waves meet they have no effect on the way each other propagates. In other words, at the next clock tick the waves will grow as though there was no encounter. Note however that their effects are combined on the lake. For example:
1 second 2 seconds 3 seconds 4 seconds
Write a program to help the cows figure out how the waves will spread out over time.
* Line 1: Four space-separated integers: P, B1, B2, and R:
* P (1 <= P <= 5) indicates the number of pebbles,
* Lines 2..P+1: Each line contains three space-separated integers that describe a pebble: X (-500,000 <= X <= 500,000), Y (-500,000 <= Y <= 500,000), and and T (1 <= T <= 500,000)
* X and Y are the coordinates where a pebble is dropped
* T is the time at which the pebble is dropped
* Lines 1..9: The output contains a 9 x 9 grid, centered on 0,0. The bottom left of the grid represents (-4, -4) and the top right represents (4,4). The grid should represent the state of the lake at time R.
2 4 100 4 -3 0 1 0 0 2
--------X -*------X *-*-*---X -o-*-*--X o-----*-X -o-*-*--X *-*-*---X -*------X --------X
[Submit] [Go Back] [Status] [Discuss]
Home Page Go Back To top
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator