COCI '08 Contest 6 #3 Nered

Points: 10

Time limit: 0.6s

Memory limit: 32M

Problem types

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 $N \times N$ $N \times N$ 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 $N$ $N$ and $M$ $M$ $(1 \le N \le 100, 1 \le M \le N^2)$ $(1 \leq N \leq 100, 1 \leq M \leq N^{2})$ , the dimensions of the surface and the number of cubes currently on the surface.

Each of the following $M$ $M$ lines contains two integers $R$ $R$ and $C$ $C$ $(1 \le R, C \le N)$ $(1 \leq R, C \leq N)$ , 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

Copy

3 2
1 1
1 1

Sample Output 1

Copy

Sample Input 2

Copy

Sample Output 2

Copy

Sample Input 3

Copy

Sample Output 3

Copy

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

Comments

2

bradypotter16 commented on Dec. 6, 2017, 1:32 p.m. ← edited →

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

1

Riolku commented on May 19, 2019, 11:12 p.m.

Note that a solution will always exist, so yes.