結果

問題 No.3740 Troublesome Congestion
コンテスト
ユーザー 👑 kencho
提出日時 2026-07-09 12:27:43
言語 Python3
(3.14.7 + numpy 2.5.2 + scipy 1.18.0 + ACL)
コンパイル:
python3 -mpy_compile _filename_
実行:
python3 _filename_
結果
WA  
実行時間 -
コード長 2,939 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 60 ms
コンパイル使用メモリ 15,104 KB
実行使用メモリ 11,264 KB
最終ジャッジ日時 2026-09-19 12:32:13
合計ジャッジ時間 2,162 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
サブタスク 配点 結果
部分点1 20 % WA * 7
部分点2 30 % WA * 12
満点 50 % WA * 26
合計 4 * 0% = 0 点
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys

N = 50
K = 31
H = 16  # first 16 stages use horizontal-continuation gadgets


def build_binary(M):
    if not (0 <= M < (1 << K)):
        return None

    G = [['#'] * N for _ in range(N)]

    r, c = 0, 0
    G[r][c] = '.'

    for k in range(K):
        if k < H:
            # State cell (r, c) has 2^k paths.
            #
            # Optional switch:
            #   go down to P, then continue down to bottom row.
            #
            # Main route:
            #   go right, then pass through a 2-way diamond.
            if (M >> k) & 1:
                pr, pc = r + 1, c
                G[pr][pc] = 'P'

                # unique suffix after pressing P
                for rr in range(pr + 1, N):
                    if G[rr][pc] != 'P':
                        G[rr][pc] = '.'
                for cc in range(pc, N):
                    if G[N - 1][cc] != 'P':
                        G[N - 1][cc] = '.'

            # binary doubling gadget
            # continue to C = (r, c+1), then 2 paths to next state
            cells = [
                (r, c + 1),
                (r, c + 2),
                (r + 1, c + 1),
                (r + 1, c + 2),
            ]
            for rr, cc in cells:
                if G[rr][cc] != 'P':
                    G[rr][cc] = '.'

            r, c = r + 1, c + 2
            G[r][c] = '.'

        else:
            # State cell (r, c) has 2^k paths.
            #
            # Optional switch:
            #   go right to P, then continue right to the right edge.
            #
            # Main route:
            #   go down, then pass through a 2-way diamond.
            if (M >> k) & 1:
                pr, pc = r, c + 1
                G[pr][pc] = 'P'

                # unique suffix after pressing P
                for cc in range(pc + 1, N):
                    if G[pr][cc] != 'P':
                        G[pr][cc] = '.'
                for rr in range(pr, N):
                    if G[rr][N - 1] != 'P':
                        G[rr][N - 1] = '.'

            # binary doubling gadget
            # continue to C = (r+1, c), then 2 paths to next state
            cells = [
                (r + 1, c),
                (r + 2, c),
                (r + 1, c + 1),
                (r + 2, c + 1),
            ]
            for rr, cc in cells:
                if G[rr][cc] != 'P':
                    G[rr][cc] = '.'

            r, c = r + 2, c + 1
            G[r][c] = '.'

    G[N - 1][N - 1] = '.'
    return G


def fallback_grid():
    # Always valid format, but gives 0 valid paths.
    G = [['#'] * N for _ in range(N)]
    for c in range(N):
        G[0][c] = '.'
    for r in range(N):
        G[r][N - 1] = '.'
    return G


def solve():
    M = int(sys.stdin.readline())

    G = build_binary(M)
    if G is None:
        G = fallback_grid()

    print(N)
    for row in G:
        print(''.join(row))


if __name__ == "__main__":
    solve()
0