A solution for problem "Projekt planszy" from 28th Olimpiada Informatyczna

pro.cpp

#include <iostream>
#ifdef SELFTEST
#include <cstring>
#include <cassert>
#include <random>
#endif

using namespace std;

unsigned patterns[] = {
    0, 2184, 2188, 2190, 2247, 2191, 2286, 2279, 3271, 2255,
    2295, 3326, 2287, 3279, 3303, 2303, 3703, 3815, 3827, 3311,
};

int N;
uint64_t K;

int digits[15];
int ndigits;

bool design[100][100];

void print() {
    cout << N << endl;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cout << (design[i][j] ? '.' : '#');
        }
        cout << endl;
    }
}

void place(int a, int b, unsigned pattern) {
    for (int i = a; i < a + 3; i++) {
        for (int j = b; j < b + 4; j++) {
            design[i][j] = pattern & 1;
            pattern >>= 1;
        }
        design[i][b-1] = 1;
    }
}

void rplace(int b, int a, unsigned pattern) {
    for (int i = a; i < a + 3; i++) {
        for (int j = b; j < b + 4; j++) {
            design[j][i] = pattern & 1;
            pattern >>= 1;
        }
        design[b-1][i] = 1;
    }
}

uint64_t count() {
    uint64_t counts[N][N];
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (!design[i][j]) {
                counts[i][j] = 0;
            } else if (i == 0 && j == 0) {
                counts[i][j] = 1;
            } else {
                uint64_t above = i ? counts[i - 1][j] : 0;
                uint64_t left = j ? counts[i][j - 1] : 0;
                counts[i][j] = above + left;
            }
        }
    }
    return counts[N - 1][N - 1];
}

void make() {
    ndigits = 0;
    while (K) {
        digits[ndigits++] = K % 20;
        K /= 20;
    }

    N = ndigits * 3 + 4;

    for (int i = 0; i < N; i++) {
        design[i][0] = design[0][i] = 1;
    }

    for (int a = 1; a <= ndigits; a++) {
        if (a % 2 == 0) {
            place(1, 3*a, patterns[digits[ndigits - a]]);

            for (int i = 4; i < 3*a; i++) {
                design[i][3*a + 3] = 1;
            }
        } else {
            rplace(3*a, 1, patterns[digits[ndigits - a]]);

            for (int j = 4; j < 3*a + 3; j++) {
                design[3*a + 3][j] = 1;
            }
        }

        if (a == 1) continue;

        for (int i = 3*a; i < 3*a+4; i++) {
            for (int j = 3*a; j < 3*a+4; j++) {
                design[i][j] = 1;
            }
        }
    }

    design[N-1][N-1] = 1;
}

#ifdef SELFTEST
int main() {
    // https://stackoverflow.com/a/21096340/5863987
    std::random_device rd;
    std::mt19937_64 e2(rd());
    std::uniform_int_distribution<long long int> dist(std::llround(std::pow(2,61)), std::llround(std::pow(2,62)));
    for (int kk = 0; kk < 100000; kk++) {
        uint64_t e = dist(e2);
        K = e;
        memset(design, 0, sizeof design);
        make();
        assert(count() == e);
    }
}
#else
int main() {
    ios::sync_with_stdio(false); cin.tie();

    cin >> K;
    make();
    print();
}
#endif