200% 190% 180% 170% 160% 150% 140% 130% 120% 110% 100%

Czech ACM Student Chapter

Czech Technical University in Prague

Charles University in Prague

Technical University of Ostrava

acm

ˇ a

Slovak University of Technology

Pavol Jozef Saf´rik University in Koˇice

s

cz

ˇ

University of Zilina

Masaryk University

Matej Bel University in Bansk´ Bystrica

a

University of West Bohemia

CTU Open Contest 2019

Screamers in the Storm

screamers.c, screamers.cpp, Screamers.java, screamers.py

As you might remember from your first years in school, the human race invented beer brewing

at least about 7000 years ago. The total amount of beer consumed from those times must be

monumental and surely the rate of consumption is not going to shrink in the coming millennia.

To celebrate these facts, we invite you to implement a game, seemingly unrelated to beer brewing.

It is quite possible, however, that after a successful implementation you might feel a little dizzy,

just as if you have had a little bit more than your daily dose of beer...

The game is played on a rectangular M × N grid consisting of square tiles of different types.

Animals and food

There is some number of animals on the grid, each animal occupies exactly one tile.

Grass grows, sheep eat grass, wolves eat sheep, and both wolves and sheep can die of starvation.

Turns and animal actions

Each turn consists of actions in the following order:

1. All animals on the grid move. Each wolf moves to a neighbouring tile in the east (to the

right). If the wolf 's move is not possible, the wolf moves to the westernmost tile in its row.

Each sheep moves to a neighbouring tile in the south (down). If the sheep's move is not

possible, the sheep moves to the northernmost tile in its column.

2. If a wolf and a sheep occupy the same tile, the wolf eats the sheep and the tile is changed

to a Soil with carcass tile.

3. If a sheep is located on a Soil with grass tile, the sheep eats the grass and the tile is

changed to a Soil tile.

4. If a wolf hasn't eaten in any of the last 10 turns including the current turn, it dies and the

tile is changed to a Soil with carcass tile.

5. If a sheep didn't eat in any of the last 5 turns including the current turn, it dies and the

tile is changed to a Soil with carcass tile.

Types of tiles and their changes

There are three types of tiles. The type of a tile may be changed in the course of the game.

1. Soil tile: After 3 turns after the beginning of the game or after 3 turns after the tile

became a Soil tile, the tile becomes a Soil with grass tile.

2. Soil with grass tile: If the grass is eaten by a sheep, the tile immediately becomes a Soil

tile. The grass will grow again at the tile after 3 turns.

3. Soil with carcass tile: Whenever an animal dies on a tile of any type, the tile immediately

becomes a Soil with carcass tile. Animals can still move to this tile, but the grass will

never grow on this tile again. As the game progresses, more carcasses may accumulate on

the tile.

Input Specification

First line of the input contains three integers T, N and M (1 ≤ T ≤ 100, 1 ≤ M, N ≤ 20), where

T is the number of turns, M is the number of rows and N is the number of columns of the grid.

The following M lines contain N characters each. Characters denote the types of tiles:

· . (dot character) denotes a Soil tile

· S denotes a Soil tile with a sheep on it

· W denotes a Soil tile with a wolf on it

Output Specification

Output M lines each containing N characters describing the state of the grid after the end of

the T -th turn. If there is an animal on a tile, output:

· W for a tile with a wolf on it

· S for a tile with a sheep on it

Otherwise, output:

· * for a Soil with carcass tile

· # for a Soil with grass tile

· . (dot character) for a Soil tile

Output for Sample Input 1

Sample Input 1

##S##

665

#####

..S..

#####

.....

#.###

.S...

W*.##

.....

#S.##

....W

.S...

Output for Sample Input 2

Sample Input 2

.##

14 3 3

#*#

S..

S##

W..

...

Output for Sample Input 3

Sample Input 3

.

231

.

S

S

.

.

Sample Input 4

Output for Sample Input 4

331

S

S

#

.

#

.

Sample Input 5

Output for Sample Input 5

431

#

S

S

.

#

.

Sample Input 6

Output for Sample Input 6

531

#

S

.

.

S

.