問題一覧 > 通常問題

No.1669 パズル作成

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 18
作問者 : 沙耶花沙耶花 / テスター : penguinmanpenguinman
11 ProblemId : 5998 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-05-02 15:30:39

問題文

N×N のマス目があります.
はじめ, i=1,2,...,M に対し rici 列目のマスは黒く, 残る N2M 個のマスは白いです.

まず, あなたは次の操作を好きな回数(0 回でもよい)行えます.

  • 操作X: 白いマスを 1 つ選び, 黒くする

  • その後, あなたは次の 2 種類の操作を好きな順番で好きな回数(やはり 0 回でもよい)行えます.
  • 操作Y: 好きな行を 1 つ選び, そこに属するマスの色を反転(白なら黒に, 黒なら白に変更)する
  • 操作Z: 好きな列を 1 つ選び, そこに属するマスの色を反転する

  • すべてのマスを黒くするために, 操作Xは最小で何回必要ですか?

    入力

    N M
    r1 c1
    
    rM cM
    

  • 1N5000
  • 0Mmin(105,N2)
  • 1ri,ciN
  • ij ならば (ri,ci)(rj,cj)
  • 入力はすべて整数
  • 出力

    答えを出力してください.
    最後に改行してください.

    サンプル

    サンプル1
    入力
    2 1
    1 2
    
    出力
    1
    

    11 列目に操作 X を行い, 2 行目に操作 Y を行うことですべてのマスを黒くできます.

    サンプル2
    入力
    2 0
    
    出力
    0
    

    サンプル3
    入力
    4 5
    1 1
    2 2
    3 2
    4 1
    1 2
    
    出力
    3
    

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