COCI '08 Contest 6 #3 Nered

View as PDF

Submit solution

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

Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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

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

3 2
1 1
1 1

Sample Output 1


Sample Input 2

4 3
2 2
4 4
1 1

Sample Output 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


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).


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

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

    • 0
      Riolku  commented on May 19, 2019, 7:12 p.m.

      Note that a solution will always exist, so yes.

    • -7
      jkguipqnjcy49979693  commented on Dec. 7, 2017, 3:56 p.m. edited

      This comment is hidden due to too much negative feedback. Click here to view it.

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

    Typo in problem description

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

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

      Fixed. Thanks for pointing that out!