Problem A
Forest Fires
Fires can spread in a forest more easily if the trees in the forest are densely packed – it makes it easy for the fire to jump from tree to tree. Write a forest fire simulator which ‘grows’ a forest tree-by-tree. As the forest grows, your simulator should answer queries about whether a fire starting at tree $A$ can spread to tree $B$ (where trees $A$ and $B$ may vary with each query).
The forest is modeled as a grid of size $100 \times 100$, where each grid square can hold exactly one tree. The bottom-left grid square is $(0,0)$ and the top-right is at $(99,99)$. Each square has an associated number, with square at $(x,y)$ numbered $100 x + y$.
Fire spreads directly from tree $A$ to $B$ if $A$ is on fire and $B$ is adjacent vertically or horizontally to $A$. Fire continues to spread until has reached all the trees it can reach in the forest. Note that we are only interested in whether a fire is able to reach from tree $A$ to tree $B$, but we do not actually remove any trees related to the query.
The simulator relies on a random number generator, which is defined as:
\[ r \leftarrow (r * 5\, 171 + 13\, 297) \mod 50\, 021 \]where each simulation starts with a different ‘seed’ for $r$. Every time a random number is needed, including the first time, this generator is used to generate a new value for $r$.
Given a seed $r$ and length of simulation $n$, the simulator should proceed as follows:
-
Initialize: let $i \leftarrow 0$.
-
Stopping condition: if $i \geq n$, then stop.
-
Place a tree: choose a random square $m \leftarrow r \mod 10\, 000$ from the random number generator. If the square numbered $m$ is occupied by a tree, generate another value of $m$ in the same way. Keep doing this until $m$ is for an unoccupied square. Place a tree at square $m$, and call this tree $t_ i$.
-
Choose $A$: compute $a \leftarrow r\mod (i+1)$, and let $A \leftarrow t_ a$.
-
Choose $B$: compute $b \leftarrow r\mod (i+1)$, and let $B \leftarrow t_ b$. It is okay if $A$ and $B$ represent the same tree.
-
Fire query: discover whether a fire started at tree $A$ can burn to tree $B$.
-
Increment: let $i \leftarrow i + 1$.
-
Loop: go back to step 2.
Report a summary of the fire queries every $100$ iterations during the simulation.
Input
Input contains up to $200$ test cases. Each test case is a line containing two integer values $0 \le r < 50\, 021$, representing the seed value of the random number generator, and $0 \le n \le 10\, 000$, representing the number of times the main simulation loop should execute. Also, $n$ is a multiple of $100$. Input ends at end of file.
Output
For each test case, after each set of $100$ iterations, output the number of fire queries (step $6$ above) which succeeded. That is, the first block is between $i=0$ and $i=99$, the second block is between $i=100$ and $i=199$, etc.
| Sample Input 1 | Sample Output 1 |
|---|---|
4 1000 22 2000 25 1000 |
9 1 0 0 0 0 0 0 0 0 7 1 0 0 1 0 1 0 0 0 1 0 0 1 0 1 0 0 0 0 1 2 0 0 0 0 1 1 0 0 |
