# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1143638 | Agageldi | Chessboard (IZhO18_chessboard) | C++17 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N 400005
#define ff first
#define ss second
#define pb push_back
#define sz(s) (int)s.size()
#define rep(c, a, b) for(c = a; c <= b; c++)
ll n, t, y, answer = LLONG_MAX, k, p, o[N], u[N], z[N], g[N];
vector <int> v;
void solve1(ll x,ll dv) {
ll white = (x + 1) / 2, black = (x / 2);
ll c = 0,c_c = 0, r = 0, ak = 0, gara = 0;
for(int i = 1; i <= k; i++) {
c_c = (o[i] + dv - 1) / dv;
r = (c_c % 2 == 1 ? 0 : 1);
c_c = (z[i] + dv - 1) / dv;
c = (c_c % 2 == 1 ? 0 : 1);
if(r == c) ak++;
}
answer = min(answer, ak + (black * dv * dv - (k - ak)));
}
void solve2(ll x,ll dv) {
ll white = x / 2, black = (x + 1) / 2;
ll c = 0,c_c = 0, r = 0, ak = 0, gara = 0;
for(int i = 1; i <= k; i++) {
c_c = (o[i] + dv - 1) / dv;
r = (c_c % 2 == 1 ? 0 : 1);
c_c = (z[i] + dv - 1) / dv;
c = (c_c % 2 == 1 ? 0 : 1);
if(r == c) gara++;
}
answer = min(answer, (k - gara) + (black * dv * dv - gara));
}
int main () {
ios: :sync_with_stdio(0);cin.tie(0);
cin >> n >> k;
for(int i = 1; i <= k; i++) {
cin >> o[i] >> z[i] >> u[i] >> g[i];
}
for(int i = 1; i < n; i++) {
if(n % i == 0) v.pb(i);
}
for(auto i : v) {
ll s_q = (n * n) / (i * i);
solve1(s_q,i);
solve2(s_q,i);
}
cout << answer << '\n';
}