結果

問題 No.1880 Many Ways
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 16:25:25
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,218 bytes
コンパイル時間 219 ms
コンパイル使用メモリ 82,520 KB
実行使用メモリ 55,128 KB
最終ジャッジ日時 2025-06-12 16:25:42
合計ジャッジ時間 16,416 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 6 WA * 8
権限があれば一括ダウンロードができます

ソースコード

diff # 

def decompose(A):
    m = 0
    while A % 2 == 0 and A != 0:
        m += 1
        A = A // 2
    return m, A

def main():
    import sys
    A = int(sys.stdin.readline().strip())
    if A == 0:
        print("2 0")
        return
    elif A == 1:
        print("1 0")
        return
    
    m, k = decompose(A)
    
    if k > 126:
        # Handle the case where k is larger than 126
        # We need to create a graph where 1 connects to k nodes, each connects to N=k+1
        # But ensure N does not exceed 128
        if k + 1 > 128:
            N = 128
            M = (N - 1) * 2
            print(f"{N} {M}")
            for i in range(2, N + 1):
                print(f"1 {i}")
            for i in range(2, N):
                print(f"{i} {N}")
        else:
            N = k + 1
            M = (N - 1) * 2
            print(f"{N} {M}")
            for i in range(2, N + 1):
                print(f"1 {i}")
            for i in range(2, N):
                print(f"{i} {N}")
    else:
        # Proceed with the initial approach
        edges = []
        nodes = [1]
        current_node = 1
        
        # Add layers for each factor of 2
        for _ in range(m):
            a = current_node + 1
            b = current_node + 2
            edges.append((current_node, a))
            edges.append((current_node, b))
            next_node = current_node + 3
            edges.append((a, next_node))
            edges.append((b, next_node))
            nodes.extend([a, b, next_node])
            current_node = next_node
        
        # Add the final layer if k > 1
        if k > 1:
            start = current_node + 1
            end = start + k - 1
            nodes.extend(range(start, end + 1))
            for i in range(start, end + 1):
                edges.append((current_node, i))
            next_node = end + 1
            nodes.append(next_node)
            for i in range(start, end + 1):
                edges.append((i, next_node))
            current_node = next_node
        
        # Output the result
        N = len(nodes)
        M = len(edges)
        print(f"{N} {M}")
        for u, v in edges:
            print(f"{u} {v}")

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