ソースコード
#include <iostream>
#include <vector>
#include <string>
#include <tuple>
#include <algorithm>
using namespace std;
int Rand(int p, int q) {
int s = 0, t = 1;
for (int i = 0; i < 3; i++) { s += (rand() % 1024)*t; t *= 1024; }
return p + s % (q - p + 1);
}
long long dp[44][44], dp2[44][44];
pair<vector<string>, long long> solve(long long N) {
for (int i = 2; i < 44; i++) {
long long H = i / 2, W = (i + 1) / 2;
for (int j = 1; j <= 100; j++) {
vector<string>F(H, "");
for (int j = 0; j < H; j++) { for (int k = 0; k < W; k++) F[j] += "."; }
long long S = Rand(H * W / 2, H * W * 2 / 3 + 1);
for (int k = 1; k <= S; k++) {
while (true) {
int px = Rand(0, H - 1), py = Rand(0, W - 1);
if (F[px][py] == '.') { F[px][py] = '2'; break; }
}
}
bool OK = false; dp[0][0] = 1; if (F[0][0] == '2') dp[0][0] = 2;
for (int k = 0; k < H; k++) {
for (int l = 0; l < W; l++) {
if (k == 0 && l == 0) continue;
dp[k][l] = 0;
if (k >= 1) dp[k][l] += dp[k - 1][l];
if (l >= 1) dp[k][l] += dp[k][l - 1];
if (F[k][l] == '2') dp[k][l] *= 2;
if (dp[k][l] > N) { OK = true; break; }
}
}
if (OK == true || !(N * 5 / 6 <= dp[H - 1][W - 1] && dp[H - 1][W - 1] <= N)) continue;
dp2[H - 1][W - 1] = 1; if (F[H - 1][W - 1] == '2') dp2[H - 1][W - 1] = 2;
for (int k = H - 1; k >= 0; k--) {
for (int l = W - 1; l >= 0; l--) {
if (k == H - 1 && l == W - 1) continue;
dp2[k][l] = 0;
if (k < H - 1) dp2[k][l] += dp2[k + 1][l];
if (l < W - 1) dp2[k][l] += dp2[k][l + 1];
if (F[k][l] == '2') dp2[k][l] *= 2;
}
}
long long A = N - dp[H - 1][W - 1];
vector<tuple<long long, int, int>>vec;
for (int k = 0; k < H; k++) {
for (int l = 0; l < W; l++) { if (F[k][l] == '.') vec.push_back(make_tuple(dp[k][l] * dp2[k][l], k, l)); }
}
sort(vec.begin(), vec.end()); reverse(vec.begin(), vec.end());
for (int k = 0; k < vec.size(); k++) {
if (A >= get<0>(vec[k])) { F[get<1>(vec[k])][get<2>(vec[k])] = '1'; A -= get<0>(vec[k]); }
}
long long SS = 0, V = A;
while (A >= 2) { if (A % 2 == 1) SS++; A /= 2; SS++; }
if (SS <= (H + W + 1)) {
return make_pair(F, V);
}
}
}
return make_pair(vector<string>{""}, -1);
}
char c[60][60];
void getans(long long N) {
for (int i = 0; i < 60; i++) { for (int j = 0; j < 60; j++) c[i][j] = '#'; }
pair<vector<string>, int>C = solve(N);
int H = C.first.size(), W = C.first[0].size();
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) { c[i][j + 2] = C.first[i][j]; }
}
for (int i = 0; i < H + 2; i++) c[i][0] = '.'; c[0][1] = '.'; c[H][W + 1] = '.';
for (int i = 0; i < W + 2; i++) c[H + 1][i] = '.';
vector<int>G; long long V = C.second;
while (V >= 2) { if (V % 2 == 1) { G.push_back(1); V--; } G.push_back(2); V /= 2; }
reverse(G.begin(), G.end());
if (V == 0) { c[1][0] = '#'; }
int cx = 1, cy = 0;
for (int i = 0; i < G.size(); i++) { c[cx][cy] = ('0' + G[i]); if (cx < H + 1) cx++; else cy++; }
cout << H + 2 << " " << W + 2 << endl;
for (int i = 0; i < H + 2; i++) {
for (int j = 0; j < W + 2; j++) cout << c[i][j]; cout << endl;
}
}
int main() {
long long n; cin >> n;
getans(n);
return 0;
}