Загрузка данных


#include <algorithm>
#include <cstdint>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

bool combinePatterns(int left, int right, int variableCount, int& combined) {
    int differingVariable = -1;
    for (int variable = 0; variable < variableCount; ++variable) {
        const int leftValue = (left >> (2 * variable)) & 3;
        const int rightValue = (right >> (2 * variable)) & 3;
        if (leftValue == rightValue) {
            continue;
        }
        if (differingVariable != -1 || leftValue > 1 || rightValue > 1) {
            return false;
        }
        differingVariable = variable;
    }

    if (differingVariable == -1) {
        return false;
    }

    const int shift = 2 * differingVariable;
    combined = (left & ~(3 << shift)) | (2 << shift);
    return true;
}

bool coversMinterm(int pattern, int minterm, int variableCount) {
    for (int variable = 0; variable < variableCount; ++variable) {
        const int value = (pattern >> (2 * variable)) & 3;
        const int mintermValue = (minterm >> (variableCount - variable - 1)) & 1;
        if (value != 2 && value != mintermValue) {
            return false;
        }
    }
    return true;
}

vector<int> makePrimeImplicants(const vector<int>& ones, int variableCount) {
    vector<int> current;
    for (int minterm : ones) {
        int pattern = 0;
        for (int variable = 0; variable < variableCount; ++variable) {
            const int value = (minterm >> (variableCount - variable - 1)) & 1;
            pattern |= value << (2 * variable);
        }
        current.push_back(pattern);
    }

    vector<int> primes;
    while (!current.empty()) {
        vector<int> next;
        vector<bool> combined(current.size(), false);

        for (size_t i = 0; i < current.size(); ++i) {
            for (size_t j = i + 1; j < current.size(); ++j) {
                int combinedPattern;
                if (!combinePatterns(current[i], current[j], variableCount,
                                    combinedPattern)) {
                    continue;
                }

                combined[i] = true;
                combined[j] = true;
                if (find(next.begin(), next.end(), combinedPattern) == next.end()) {
                    next.push_back(combinedPattern);
                }
            }
        }

        for (size_t i = 0; i < current.size(); ++i) {
            if (!combined[i] &&
                find(primes.begin(), primes.end(), current[i]) == primes.end()) {
                primes.push_back(current[i]);
            }
        }
        current = move(next);
    }
    return primes;
}

int literalCount(int pattern, int variableCount) {
    int count = 0;
    for (int variable = 0; variable < variableCount; ++variable) {
        if (((pattern >> (2 * variable)) & 3) != 2) {
            ++count;
        }
    }
    return count;
}

bool isValidInput(int variableCount, const string& values) {
    return variableCount >= 1 && variableCount <= 5 &&
           values.size() == static_cast<size_t>(1 << variableCount) &&
           values.find_first_not_of("01") == string::npos;
}

string minimize(int variableCount, const string& values) {
    vector<int> ones;
    for (size_t i = 0; i < values.size(); ++i) {
        if (values[i] == '1') {
            ones.push_back(static_cast<int>(i));
        }
    }

    if (ones.empty()) {
        return "0";
    }
    if (ones.size() == values.size()) {
        return "1";
    }

    const vector<int> primes = makePrimeImplicants(ones, variableCount);
    vector<vector<int>> covering(ones.size());
    for (size_t prime = 0; prime < primes.size(); ++prime) {
        for (size_t target = 0; target < ones.size(); ++target) {
            if (coversMinterm(primes[prime], ones[target], variableCount)) {
                covering[target].push_back(static_cast<int>(prime));
            }
        }
    }

    vector<int> best;
    int bestLiteralCount = 0;
    const uint64_t subsetCount = uint64_t{1} << primes.size();
    for (uint64_t subset = 1; subset < subsetCount; ++subset) {
        int termCount = 0;
        for (uint64_t bits = subset; bits != 0; bits &= bits - 1) {
            ++termCount;
        }
        if (!best.empty() && termCount > static_cast<int>(best.size())) {
            continue;
        }

        bool coversAll = true;
        for (const auto& candidates : covering) {
            bool covered = false;
            for (int prime : candidates) {
                if ((subset & (uint64_t{1} << prime)) != 0) {
                    covered = true;
                    break;
                }
            }
            if (!covered) {
                coversAll = false;
                break;
            }
        }
        if (!coversAll) {
            continue;
        }

        int literals = 0;
        vector<int> selected;
        for (size_t prime = 0; prime < primes.size(); ++prime) {
            if ((subset & (uint64_t{1} << prime)) != 0) {
                selected.push_back(static_cast<int>(prime));
                literals += literalCount(primes[prime], variableCount);
            }
        }
        if (best.empty() || termCount < static_cast<int>(best.size()) ||
            (termCount == static_cast<int>(best.size()) &&
             literals < bestLiteralCount)) {
            best = move(selected);
            bestLiteralCount = literals;
        }
    }

    sort(best.begin(), best.end(), [&](int left, int right) {
        for (int variable = 0; variable < variableCount; ++variable) {
            const int shift = 2 * variable;
            const int leftValue = (primes[left] >> shift) & 3;
            const int rightValue = (primes[right] >> shift) & 3;
            if (leftValue != rightValue) {
                return leftValue < rightValue;
            }
        }
        return false;
    });

    const string variableNames = "xyztu";
    string result;
    bool firstTerm = true;
    for (int primeIndex : best) {
        if (!firstTerm) {
            result += " v ";
        }
        firstTerm = false;

        const int pattern = primes[primeIndex];
        for (int variable = 0; variable < variableCount; ++variable) {
            const int value = (pattern >> (2 * variable)) & 3;
            if (value == 2) {
                continue;
            }
            char name = variableNames[variable];
            if (value == 1) {
                name = static_cast<char>(name - 'a' + 'A');
            }
            result += name;
        }
    }
    return result;
}

int main() {
    int variableCount;
    string values;
    if (!(cin >> variableCount >> values)) {
        cerr << "Input must contain the variable count and the truth vector.\n";
        return 1;
    }
    if (!isValidInput(variableCount, values)) {
        cerr << "Expected 1 to 5 variables and a matching binary truth vector.\n";
        return 1;
    }

    cout << minimize(variableCount, values) << '\n';
    return 0;
}