Генерация предподсчёта для задачи «Хорошие раскраски»: https://codeforces.com/gym/102936/problem/7

good_coloring_gen.cpp

#include <bits/stdc++.h>

using namespace std;

#define vi vector<int>
#define vvi vector<vector<int>>

minstd_rand mtrand;

int cost(vvi &t, int n, int m){
    int r = 0;
    for(int y1 = 0; y1 < n-1; ++y1)
        for(int y2 = y1+1; y2 < n; ++y2)
            for(int x1 = 0; x1 < m-1; ++x1)
                for(int x2 = x1+1; x2 < m; ++x2)
                    if(t[y1][x1] == t[y1][x2] && t[y1][x2] == t[y2][x1] && t[y2][x1] == t[y2][x2])
                        ++r;
    return r;
}

void resample(vvi &t, int n, int m, int c){
    for(int y = 0; y < n; ++y){
        for(int x = 0; x < m; ++x){
            t[y][x] = mtrand() % c + 1;
        }
    }
}

bool tryfix(vvi &t, int n, int m, int c){
    int cst = cost(t, n, m);
    if(cst == 0){
        return true;
    }

    for(int i = 0; i < n * m; ++i){
        for(int y = 0; y < n; ++y){
            for(int x = 0; x < m; ++x){
                int col = t[y][x];
                int col2 = mtrand() % c + 1;

                t[y][x] = col2;

                int newCost = cost(t, n, m);
                if(newCost < cst){
                    cst = newCost;
                    if(cst == 0){
                        return true;
                    }
                }else if(newCost > cst){
                    t[y][x] = col;
                }
            }
        }
    }
    return false;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    random_device device;
    mtrand.seed(device());

    for(int n = 2; n <= 10; ++n){
        for(int m = n; m <= 10; ++m){
            for(int c = 2; c <= 3; ++c){
                vvi t(n);
                for(int y = 0; y < n; ++y){
                    t[y] = vi(m, 1);
                }

                bool solved = false;

                int attempts = 0;
                while(attempts < 3000){
                    resample(t, n, m, c);

                    if(tryfix(t, n, m, c)){
                        solved = true;
                        break;
                    }
                    ++attempts;
                }

                cout << "ans[" << n << "][" << m << "][" << c << "] = ";
                if(solved){
                    cout << "[";
                    for(int y = 0; y < n; ++y){
                        cout << "[";
                        for(int x = 0; x < m; ++x){
                            cout << t[y][x];
                            if(x != m-1){
                                cout << ", ";
                            }
                        }
                        cout << "]";
                        if(y != n-1){
                            cout << ", ";
                        }
                    }
                    cout << "]" << endl;
                }else{
                    cout << "None" << endl;
                }
            }
        }
    }
}