「みんなのプロコン 2018」決勝: B - 経路が色々

note

この手の「$K$個ちょうどのものを構成せよ」は$n$進数展開して桁ごとにやるのが定石。

solution

$2$進数展開して桁ごとに。あまり雑だと収まらないので2段に分ける。$O(\log K)$。

例えば入力が$756604737398252112 = 0b101010000000000000000000000000000000000000000010001001010000$なら以下のように。

100 100
...........########################################################################################.
.#######.#.########################################################################################.
..######.....######################################################################################.
...#######.#.######################################################################################.
#...######.....####################################################################################.
##...#######.#.####################################################################################.
###...######.....##################################################################################.
####...#######.#.##################################################################################.
#####...######......................................................................................
######...#######.#.################################################################################.
#######...######.....##############################################################################.
########...#######.#.##############################################################################.
#########...######..................................................................................
##########...#######.#.############################################################################.
###########...######.....##########################################################################.
############...#######.#.##########################################################################.
#############...######.....########################################################################.
##############...#######.#.########################################################################.
###############...######............................................................................
################...#######.#.######################################################################.
#################...######.....####################################################################.
##################...#######.#.####################################################################.
###################...######.....##################################################################.
####################...#######.#.##################################################################.
#####################...######.....################################################################.
######################...#######.#.################################################################.
#######################...######....................................................................
########################...#######.#.##############################################################.
#########################...######.....############################################################.
##########################...#######.#.############################################################.
###########################...######.....##########################################################.
############################...#######.#.##########################################################.
#############################....#####.....########################################################.
##############################.#.#######.#.########################################################.
##############################.....#####.....######################################################.
################################.#.#######.#.######################################################.
################################.....#####.....####################################################.
##################################.#.#######.#.####################################################.
##################################.....#####.....##################################################.
####################################.#.#######.#.##################################################.
####################################.....#####.....################################################.
######################################.#.#######.#.################################################.
######################################.....#####.....##############################################.
########################################.#.#######.#.##############################################.
########################################.....#####.....############################################.
##########################################.#.#######.#.############################################.
##########################################.....#####.....##########################################.
############################################.#.#######.#.##########################################.
############################################.....#####.....########################################.
##############################################.#.#######.#.########################################.
##############################################.....#####.....######################################.
################################################.#.#######.#.######################################.
################################################.....#####.....####################################.
##################################################.#.#######.#.####################################.
##################################################.....#####.....##################################.
####################################################.#.#######.#.##################################.
####################################################.....#####.....################################.
######################################################.#.#######.#.################################.
######################################################.....#####.....##############################.
########################################################.#.#######.#.##############################.
########################################################.....#####...##############################.
##########################################################.#.######################################.
##########################################################.....####################################.
############################################################.#.####################################.
############################################################.....##################################.
##############################################################.#.##################################.
##############################################################.....################################.
################################################################.#.################################.
################################################################.....##############################.
##################################################################.#.##############################.
##################################################################.....############################.
####################################################################.#.############################.
####################################################################.....##########################.
######################################################################.#.##########################.
######################################################################.....########################.
########################################################################.#.########################.
########################################################################.....######################.
##########################################################################.#.######################.
##########################################################################.....####################.
############################################################################.#.####################.
############################################################################.....##################.
##############################################################################.#.##################.
##############################################################################.....################.
################################################################################.#.################.
################################################################################.....##############.
################################################################################.#.#.##############.
################################################################################.#.....############.
################################################################################.###.#.############.
################################################################################.###.....##########.
################################################################################.###.#.#.##########.
################################################################################.###.#.....########.
################################################################################.###.###.#.########.
################################################################################.###.###...########.
################################################################################.###.###.##########.
################################################################################.###.###.##########.
################################################################################.###.###.##########.
################################################################################.###.###.##########.
################################################################################.###.###.##########.
################################################################################.###.###.##########.
....................................................................................................

implementation

#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < int(n); ++ (i))
#define REP3(i, m, n) for (int i = (m); (i) < int(n); ++ (i))
using namespace std;

int main() {
    // input
    long long k; scanf("%lld", &k);
    assert (k < (1ll << 60));

    // solve
    constexpr int N = 100;
    array<array<bool, N>, N> f = {};
    auto draw_box2 = [&](int y, int x) {
        REP (dy, 2) REP (dx, 2) {
            f[y + dy][x + dx] = true;
        }
    };
    auto draw_box3 = [&](int y, int x) {
        REP (dy, 3) REP (dx, 3) {
            if (dy == 1 and dx == 1) continue;
            f[y + dy][x + dx] = true;
        }
    };
    f[0][0] = true;
    REP (x, 8) f[0][x] = true;
    REP (z, 30) draw_box3(2 * z, 8 + 2 * z);  // for 1, 2, 4, ..., 2^29
    f[1][0] = true;
    REP (z, 30) draw_box2(2 + z, z);  // shift 30
    REP (z, 30) draw_box3(2 + 30 + 2 * z, 30 + 2 * z);  // for 2^30, ..., 2^59
    REP (x, N) f[N - 1][x] = true;
    REP (y, N) f[y][N - 1] = true;
    REP (z, 30) if (k & (1ll << z)) {
        REP3 (x, 8 + 2 * z, N) {
            f[2 * z][x] = true;
        }
    }
    REP (z, 30) if (k & (1ll << (30 + z))) {
        REP3 (y, 2 + 30 + 2 * z, N) {
            f[y][30 + 2 * z] = true;
        }
    }

    // output
    printf("%d %d\n", N, N);
    REP (y, N) {
        REP (x, N) {
            printf("%c", f[y][x] ? '.' : '#');
        }
        printf("\n");
    }
    return 0;
}