問題一覧 > 通常問題

No.1669 Puzzle Creation

レベル : / AI推定難易度 : 2200 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 16
作問者 : 沙耶花 / テスター : penguinman
お気に入りにしたユーザー ProblemId : 5998 / 自分の提出
問題文最終更新日: 2021-05-02 15:30:39
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 312 (順位表) の他の問題:

Problem Statement

There is an $N \times N$ grid.
Initially, for each $i=1,2,...,M$, the cell at row $r_i$ and column $c_i$ is black, and the remaining $N^2 - M$ cells are white.

First, you may perform the following operation any number of times (possibly $0$ times).

  • Operation $X$: Choose $1$ white cell and paint it black.

    • After that, you may perform the following $2$ types of operations in any order, any number of times (again, possibly $0$ times).
  • Operation $Y$: Choose any $1$ row and invert the colors of the cells in it (white becomes black, black becomes white).
  • Operation $Z$: Choose any $1$ column and invert the colors of the cells in it.

    • What is the minimum number of times operation $X$ must be performed in order to make all cells black?

    Input

    $N\ M$
$r_1\ c_1$
$\vdots$
$r_M\ c_M$

  • $1 \le N \le 5000$
  • $0 \le M \le \min (10^5, N^2)$
  • $1 \le r_i,c_i \le N$
  • If $i \ne j$, then $(r_i,c_i) \ne (r_j,c_j)$
  • All inputs are integers.

    • Output

    Output the answer.
    Print a newline at the end.

    Sample

    Sample 1
    Input
    2 1
1 2
    Output
    1

    You can make all cells black by performing operation $X$ on the cell at row $1$, column $1$, and performing operation $Y$ on row $2$.

    Sample 2
    Input
    2 0
    Output
    0

    Sample 3
    Input
    4 5
1 1
2 2
3 2
4 1
1 2
    Output
    3

    提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。