COCI '08 Contest 6 #3 Nered

View as PDF

Points: 10
Time limit: 1.0s
Memory limit: 32M

Problem type

In the nearby kindergarten they recently made up an attractive game of strength and agility that kids love.

The surface for the game is a large flat area divided into squares.

The children lay large spongy cubes onto the surface. The sides of the cubes are the same length as the sides of the squares. When a cube is put on the surface, its sides are aligned with some square. A cube may be put on another cube too.

Kids enjoy building forts and hiding them, but they always leave behind a huge mess. Because of this, prior to closing the kindergarten, the teachers rearrange all the cubes so that they occupy a rectangle on the surface, with exactly one cube on every square in the rectangle.

In one moving, a cube is taken off the top of a square to the top of any other square.

Write a program that, given the state of the surface, calculates the smallest number of moves needed to arrange all cubes into a rectangle.

Input Specification

The first line contains the integers and , the dimensions of the surface and the number of cubes currently on the surface.

Each of the following M lines contains two integers and , the coordinates of the square that contains the cube.

Output Specification

Output the smallest number of moves. A solution will always exist.

Sample Input 1

3 2
1 1
1 1

Sample Output 1

1

Sample Input 2

4 3
2 2
4 4
1 1

Sample Output 2

2

Sample Input 3

5 8
2 2
3 2
4 2
2 4
3 4
4 4
2 3
2 3

Sample Output 3

3

In the first example, it suffices to move one of the cubes from (1, 1) to (1, 2) or (2, 1). In the third example, a cube is moved from (2, 3) to (3, 3), from (4, 2) to (2, 5) and from (4, 4) to (3, 5).

• bradypotter16  commented on Dec. 6, 2017, 8:32 a.m. edited

If the number of cubes is prime, is it assumed that M ≤ N?

• aeternalis1  commented on Aug. 14, 2017, 5:38 a.m.

Typo in problem description

Line 3 should be 'cubes', not 'cues'.

• Kirito  commented on Aug. 14, 2017, 9:57 a.m.

Fixed. Thanks for pointing that out!