結果

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

ソースコード

diff #
raw source code 

import sys

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

    N = 50

    # Fibonacci:
    # F[1] = 1, F[2] = 1, F[3] = 2, ...
    # We use F[2]..F[87].
    F = [0] * 90
    F[1] = 1
    F[2] = 1
    for i in range(3, 90):
        F[i] = F[i - 1] + F[i - 2]

    # Zeckendorf representation using F[2], F[3], ...
    terms = []
    rem = M
    for t in range(87, 1, -1):
        if F[t] <= rem:
            terms.append(t)
            rem -= F[t]

    assert rem == 0

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

    # ------------------------------------------------------------
    # 1. Fibonacci prefix band
    #
    # Open cells satisfying 0 <= row - col <= 3.
    #
    # In this band:
    #   paths to (i, i)       = F[2i - 1]
    #   paths to (i + 2, i-1) = F[2i]
    #
    # We only open the necessary finite part.
    # ------------------------------------------------------------
    for r in range(46):      # 0..45
        for c in range(45):  # 0..44
            if 0 <= r - c <= 3:
                G[r][c] = '.'

    # ------------------------------------------------------------
    # 2. Upper collector
    #
    # Odd Fibonacci term F[2i-1] uses switch at:
    #   (i, i+1)
    #
    # After pressing it, the successful route goes right into:
    #   U_i = (i, i+2)
    #
    # Then all U_i are connected by a one-way staircase:
    #   U_i -> (i, i+3) -> U_{i+1}
    # ------------------------------------------------------------
    for i in range(1, 44):  # i = 1..43
        G[i][i + 2] = '.'       # U_i
        G[i][i + 3] = '.'       # horizontal step
        G[i + 1][i + 3] = '.'   # U_{i+1}

    # Terminal part from U_44 = (44, 46)
    G[44][46] = '.'
    for c in range(47, 50):
        G[44][c] = '.'
    for r in range(45, 50):
        G[r][49] = '.'

    # ------------------------------------------------------------
    # 3. Lower collector
    #
    # Even Fibonacci term F[2i] uses switch at:
    #   (i+3, i-1)
    #
    # After pressing it, the successful route goes down into:
    #   L_i = (i+4, i-1)
    #
    # Then all L_i are connected by a one-way staircase:
    #   L_i -> (i+5, i-1) -> L_{i+1}
    # ------------------------------------------------------------
    for i in range(1, 43):  # i = 1..42
        G[i + 4][i - 1] = '.'   # L_i
        G[i + 5][i - 1] = '.'   # vertical step
        G[i + 5][i] = '.'       # L_{i+1}

    # Terminal part from L_43 = (47, 42)
    G[47][42] = '.'
    G[48][42] = '.'
    for c in range(42, 50):
        G[49][c] = '.'

    # ------------------------------------------------------------
    # 4. Place switches corresponding to Zeckendorf terms
    # ------------------------------------------------------------
    for t in terms:
        if t % 2 == 1:
            # t = 2i - 1
            i = (t + 1) // 2
            G[i][i + 1] = 'P'
        else:
            # t = 2i
            i = t // 2
            G[i + 3][i - 1] = 'P'

    G[0][0] = '.'
    G[49][49] = '.'
    
    print(N)
    print('\n'.join(''.join(row) for row in G))


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