AIOC Banner

Problem: Blackout

Want to try solving this problem? You can submit your code online if you log in or register.


Blackout

Input File: standard input
Output File: standard output
Time Limit: 1 second
Memory Limit: 128 MB

This time they had planned for every possible failure and made every system redundant: two independent electric fences, two control centers, two power lines connected to two separate power plants, and two GPS tracking devices attached to each beast. Nothing could possibly go wrong with this amount of security and redundancy.

What they never predicted is now happening: a national strike in every non-renewable energy power plant in the country, following the announcement of a new target of producing 100% of the country's energy from renewable sources within 5 years. The ensuing blackout is there to last, and the backup generators can only power the electric fences for a few more hours, before every Tyrannosaurus Rex of the brand new park is free to explore the neighboring residential areas.

You have been asked to participate in implementing the emergency plan. Paleontologists have recently discovered that T-Rexes won't eat salty food, and conjectured that salt can be used as a T-Rex repellent. Further, the brand new park is conveniently arranged as a S  x  S grid, broken up into unit squares. The plan is to use helicopters to drop sea water on certain squares of land so that the T-Rexes will avoid them and stay in the park. Your job is to write a program that will determine where to pour sea water each hour after the blackout in order to minimise the number of escaped T-Rexes.

There are two types of squares in the park; empty squares that T-Rexes can enter, and squares with obstacles, which they can not. The GPS trackers will give you the last position of each T-Rex in this grid before the power goes down. While you won't be able to track their movement, you do know that every hour each T-Rex can move to any of the 4 squares adjacent to its previous position (provided the square is not an obstacle, nor has had sea water dropped onto it). Each hour, you will be able to drop sea water on W squares, permanently preventing any T-Rex from entering these squares.

Input

Output

Sample Input

5 2 1
0 1 0 0 0
0 0 0 0 0
0 0 0 1 0
0 0 0 0 0
0 1 1 1 0
2 3

Sample Output

3
1 3
2 2
4 3

Explanation

The park is a 5  x  5 grid, with only one T-Rex. You can drop water on 2 squares every hour. The grid is represented below, where T is the initial location of the T-Rex.

0 1 0 0 0
0 0 0 0 0
0 0 0 1 0
0 0 T 0 0
0 1 1 1 0

One way to prevent the T-Rex from escaping the park is to drop water on two squares in the first hour, on the left (1,3) and above (2,2) the T-Rex's initial location. This means the T-Rex can either stay where it is, or move to the right. At the end of the first hour, the situation is the following, where W marks the squares where water has been dropped, and T marks the two squares where the T-Rex may now be located.

0 1 0 0 0
0 0 0 0 0
0 0 W 1 0
0 W T T 0
0 1 1 1 0

Dropping water on square (4, 3) will prevent the T-Rex from ever escaping the 2-square area that it is now confined to.

Constraints & Subtasks

For each test case of each subtask, you will score 100% if the output of your program enables the capture of the most T-Rexes among all judges' solutions. Otherwise, your score for that test will be :

\begin{equation*}
\frac{100 \times [\text{Number of T-Rexes your output
capture...
...{\text{Maximum number of T-Rexes captured by judges' solutions}}
\end{equation*}


If your program gives an invalid output, your score will be 0 for that test case.


Your total score for a subtask will be the sum of your score for each of its test cases.

 


Privacy statement
© Australian Mathematics Trust 2001-2019

Contact: training@orac.amt.edu.au
Page generated: 24 May 2019,  4:16am AEST