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

You are working hard to make informatics competitions more entertaining to the public, and are organizing this year's olympiad in a big indoor stadium, with a big audience. While all the contestants will try hard to concentrate on solving problems, cheerleaders will cheer as scores appear on giant screens in real time, the olympiad's mascot will throw small gifts to the crowd and guides will perform as a giant human LCD screen.

All this costs more than expected and you had to find an extra sponsor at the last minute. A fast food chain has agreed to pay for the extra costs on the condition that their logo be added to the end of the human LCD routine.

At the end of the existing routine, the guides will be arranged as a nice 2-dimentional grid. Each cell will contain a guide wearing a coloured t-shirt, forming one pixel of the human LCD screen. You are given a description of this grid and the colour of the guide contained in each cell. You are also given a description of the colour that each cell should display to represent the sponsor's logo perfectly.

As you don't have much time to train the guides for this extra move, you want to make it simple: each guide will either not move, or swap their position with one of the guides in the 4 adjacent cells. All swaps happen simultaneously, and no guide may be involved in more than one swap. Note that unlike real human LCDs, the guides cannot change their colour.

Your goal is to find a collection of such swaps, so that the resulting image formed on the grid is as close as possible to the sponsor's logo.

The first line of input will contain two space-separated integers
*R, C*: the number of rows and columns of the grid
(*1 ≤ R,C ≤ 100*).

The following *R* lines will describe the initial grid as it is shown to
the public at the end of the original routine. Each line describes a row of the
grid and contains *C* space-separated integers, the
colours of the guides in the cells of that row. All colours are integers
between 0 and 9, inclusive.

The following *R* lines will describe the grid that you are trying to
obtain, representing the sponsor's logo. Each line describes a row and contains
*C* space-separated integers, the colours the cells should show to form
the sponsor's logo.

See the *Scoring* section for a breakdown of the marks awarded for
different test cases.

Your program must write several lines to standard output.
The first line should contain a single integer *S*, the number of swaps in
your solution.

Each of the *S* following lines will contain four integers: the
coordinates *(r _{1}, c_{1})* and

3 4 1 2 3 4 4 3 2 1 1 1 2 2 4 3 2 4 1 1 1 2 2 3 2 2

4 0 0 1 0 0 1 0 2 1 1 2 1 1 2 1 3

Performing the swaps in the sample output above gives the following grid:

4 3 2 4 1 1 1 2 1 3 2 2

Out of 12 cells, 11 match the sponsor's logo. This is an optimal solution.

The score for each input scenario will be calculated based on the number of cells that match the desired logo, as follows:

- If the sequence of swaps is invalid (e.g. an invalid move is made or a guide is moved more than once) then the score for the test case will be 0%.
- If the number of cells that match is optimal (i.e., no other set of swaps gives a result with more matching cells), then the score for the test case will be 100%.
- If the number of cells that match is the same as, or less than, the original image, then the score for the test case will be 0%.
- Otherwise, let
*a*be the number of matching cells in an optimal solution. Let*b*be the number of matching cells in the original input. Let*x*be the number of matching cells in your solution. The score for the test case (out of 100) will be computed by the formula: 100 * ((*x*-*b*) ÷ (*a*-*b*))^{6}

For example, suppose that the optimal solution has *a*=100 matching cells
and the original input has *b*=50 matching cells. Then scores would be
assigned as follows:

Matching cells (x) |
40 | 50 | 60 | 70 | 80 | 85 | 90 | 95 | 100 |

Score (%, rounded) | 0 | 0 | 0 | 0 | 5 | 12 | 26 | 53 | 100 |

The judge's solution finds an optimal solution within the time and memory limits.

The following table lists the sizes of the inputs used in the test data.

R | C | Percentage of marks |

1 | 100 | 10% |

10 | 10 | 10% |

20 | 20 | 10% |

100 | 100 | 70% |

Privacy
statement

© Australian Mathematics Trust 2001-2021

Page generated: 21 October 2021, 8:18pm AEDT