ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

USU Championship 2001

About     Problems     Submit solution     Judge status     Standings
Contest is over

A. Mosaic

Time limit: 0.25 second
Memory limit: 64 MB
There's no doubt that one of the most important and crucial things to do in this world is to bring up children. May be, if you study properly and reach good results at the competition you'll get a position of nanny in a kindergarten. But you are to get ready for it! Let's consider some problems that a nanny has to solve in a kindergarten.
Everyone knows the game "Mosaic". Playing the game, one is to lay out pictures of different colored pieces. Let there be M different boxes and N mosaic pieces of each of the M colors. After playing the game children rarely put the pieces back to their boxes correctly so that the color of the box and the colors of its pirces would be the same. A nanny has to do that.
Children have already put the mosaic pieces to the boxes but possibly not correctly. There are N pieces in each box. Some pieces (possibly all of them) are located in wrong boxes (i.e. boxes with pieces of a different color). Moving a hand once one can take a piece from one box to another or simply move the hand to another box. You may start from any box you like. The movement towards the first box is not taken into account. Find out the minimal number of movements one needs to put all the mosaic pieces to their boxes.


The first line contains integers 2 ≤ M ≤ 500 (the number of colors) and 2 ≤ N ≤ 50 (the number of pieces of each color). Each of the next M lines contains N integers in the range from 1 to M (the i+1-st line contains colors of pieces located in the i-th box).


the minimal possible number of hand movements that one has to make in order to take all the pieces to their boxes.


4 3
1 3 1
2 3 3
1 2 2
4 4 4
Problem Author: Stanislav Vasilyev
Problem Source: VI Ural State University Collegiate Programming Contest (21.10.2001)
To submit the solution for this problem go to the Problem set: 1124. Mosaic