Submission #570528

#	Time	Username	Problem	Language	Result	Execution time	Memory
570528		timreizin	Lamps (JOI19_lamps)	C++17	0 / 100	1 ms	212 KiB

lamp

#include <iostream>
#include <vector>
#include <numeric>
#include <cmath>
#include <set>
#include <array>
#include <algorithm>

using namespace std;

using ll = long long;

int counter(int a, string b, int n)
{
    b.push_back('0');
    int cnt1 = 0;
    for (int i = 1; i <= n; ++i) cnt1 += b[i] == '0' && b[i - 1] == '1';
    b.back() = '1';
    int cnt2 = 0;
    for (int i = 1; i <= n; ++i) cnt2 += b[i] == '1' && b[i - 1] == '0';
    if (a != 0) ++cnt1;
    if (a != (1 << n) - 1) ++cnt2;
    return min(cnt1, cnt2);
}

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    int n;
    string a, b;
    cin >> n >> a >> b;
    int minRes = 1e9;
    for (int mask = 0; mask < (1 << n); ++mask)
    {
        int na = 0, add = 0;
        for (int i = 0; i < n; ++i)
        {
            na += (((a[i] - '0') + (mask & (1 << i))) % 2) * (1 << i);
            if (i > 0) add += !(mask & (1 << i)) && (mask & (1 << (i - 1)));
        }
        minRes = min(minRes, counter(na, b, n) + add);
    }
    cout << minRes;
    return 0;
}

• Subtask 1: 0 / 6
• Subtask 2: 0 / 41
• Subtask 3: 0 / 4
• Subtask 4: 0 / 49