p262.ans1
======================
2
1000
1000

=================
p262.cpp
======================
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int n, m, k;
vector<vector<bool>> symbols;

void read() {
    cin >> n >> m >> k;
    symbols.resize(k);
    for(int i = 0; i < k; i++) {
        symbols[i] = {};
        for(int j = 0; j < n; j++) {
            string s;
            cin >> s;
            for(char c: s) {
                symbols[i].push_back(c - '0');
            }
        }
    }
}

void solve() {
    // For problems like this it's often useful to define what exactly we are
    // looking for. Here we want each of the k symbols to be distinguishable,
    // meaning that for each pair of the C(k, 2), there should be at least one
    // selected pixel where the symbols differ. The key observation is that k <=
    // 6, implies that C(k, 2) <= 15. Therefore, 2^C(k, 2) isn't very large, and
    // we can do some approach that encodes the mask of pairs that are already
    // distinguishable. To finish it off, we can do a DP[position][mask], where
    // position <= n*m is the current pixel we are considering. We have two
    // options - either include the pixel at the current position, meaning that
    // some of the relationships will become "1", or skip it, keeping the
    // current mask. Note that we can precompute for each position, the mask it
    // will "or" / "|", so that each transition is in O(1). Overall, the time
    // complexity would be O(n * m * 2^C(k, 2)) which comfortably passes the
    // given constraints.

    int total = n * m;
    int pairs = 0;
    vector<pair<int, int>> pair_list;
    for(int a = 0; a < k; a++) {
        for(int b = a + 1; b < k; b++) {
            pair_list.push_back({a, b});
            pairs++;
        }
    }

    int full_mask = (1 << pairs) - 1;

    vector<int> pixel_mask(total);
    for(int p = 0; p < total; p++) {
        for(int i = 0; i < pairs; i++) {
            auto [a, b] = pair_list[i];
            if(symbols[a][p] != symbols[b][p]) {
                pixel_mask[p] |= (1 << i);
            }
        }
    }

    vector<vector<int>> dp(total + 1, vector<int>(full_mask + 1, total + 1));
    vector<vector<int>> prev_mask_of(total + 1, vector<int>(full_mask + 1, -1));
    dp[0][0] = 0;

    for(int p = 0; p < total; p++) {
        for(int mask = 0; mask <= full_mask; mask++) {
            if(dp[p][mask] > total) {
                continue;
            }
            if(dp[p + 1][mask] > dp[p][mask]) {
                dp[p + 1][mask] = dp[p][mask];
                prev_mask_of[p + 1][mask] = mask;
            }
            int new_mask = mask | pixel_mask[p];
            if(dp[p + 1][new_mask] > dp[p][mask] + 1) {
                dp[p + 1][new_mask] = dp[p][mask] + 1;
                prev_mask_of[p + 1][new_mask] = mask;
            }
        }
    }

    vector<bool> chosen(total, false);
    int mask = full_mask;
    for(int p = total; p > 0; p--) {
        int pm = prev_mask_of[p][mask];
        if(pm != mask) {
            chosen[p - 1] = true;
        }
        mask = pm;
    }

    cout << dp[total][full_mask] << '\n';
    for(int i = 0; i < total; i++) {
        cout << (chosen[i] ? '1' : '0');
        if((i + 1) % m == 0) {
            cout << '\n';
        }
    }
}

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

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        solve();
    }

    return 0;
}

=================
p262.in1
======================
2 4 3
0000
0001

1000
0001

1111
1001

=================
statement.txt
======================
262. Symbol Recognition
time limit per test: 0.25 sec.
memory limit per test: 65536 KB
input: standard
output: standard



Consider a monochrome computer monitor with N x M pixels resolution. It can display K symbols. Symbol is a non-empty set of black pixels on the screen. You are to write a program, that computes minimal possible amount of pixels, that are enough to recognize a symbol.

Input
First line of input contains integers N, M, K (1 <= N, M <= 10, 2 <= K <= 6). K blocks follow, separated by empty lines. Each block consists of N rows of M characters. It's a symbols representation on the N x M screen. `1' denotes black pixel, `0' denotes white pixel. You may assume that symbols are unique.

Output
Print on the first line of output the minimal possible amount of pixels that enough to recognize symbol. I.e. you have to find set of pixels that has different color in each pair of symbols. If there are several sets with equal amount of pixels, output any of them. Then print N lines M characters each. `1' denotes that corresponding pixel is in your set. `0' denotes that corresponding pixel is not in your set.

Sample test(s)

Input
2 4 3
0000
0001

1000
0001

1111
1001

Output
2
1000
1000

Note
In this example output set consists of two most left pixels. They are both white in first symbol; black and white in second symbol; both black in third symbol. So, it's possible to recognize each symbol using this set of pixels.
Author:	Andrew V. Lazarev
Resource:	Saratov SU Contest: Golden Fall 2004
Date:	October 2, 2004








=================
