competitive-programming/neps/neps3267.cpp at main · oldirtty/competitive-programming · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
/*
 * Contest : OBI 2025 - Fase 2
 * Problem : Mania de Ímpar
 * Link    : https://neps.academy/br/exercise/3267
 */

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#define fastio ios::sync_with_stdio(0); cin.tie(0);

int grid[101][101], n, m;

bool condition(int i, int j, int parity) {
  int sum = i + j;
  return (sum % 2 == 0 && grid[i][j] % 2 != parity) || (sum % 2 == 1 && grid[i][j] % 2 == parity);
}

int main() {
  fastio

  cin >> n >> m;

  for (int i = 0; i < n; ++i)
    for (int j = 0; j < m; ++j) cin >> grid[i][j];

  int parity = grid[0][0] % 2, cnt = 0;

  /*
      Caso 1: Incrementar em todas posições pares do xadrez de valor
      com paridade != grid[0][0] OU Todas as posições impares de valor
      com paridade == grid[0][0].

      Caso 2: Se o caso 1 acabar alterando mais valores do que deixando
      valores passar, a melhor opção é alterar os valores que NÃO enquadram
      o caso 1.
  */
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
      if ((i + j) % 2 == 0 && grid[i][j] % 2 != parity) cnt++;
      if ((i + j) % 2 == 1 && grid[i][j] % 2 == parity) cnt++;
    }
  }

  if (cnt <= n * m - cnt) {
    cout << cnt << '\n';

    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < m; ++j) {
        if (condition(i, j, parity)) grid[i][j]++;

        cout << grid[i][j] << " \n"[j == m - 1];
      }
    }
  }
  else {
    cout << n * m - cnt << '\n';

    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < m; ++j) {
        if (!condition(i, j, parity)) grid[i][j]++;
        cout << grid[i][j] << " \n"[j == m - 1];
      }
    }
  }

  return 0;
}