結果

問題 No.2929 Miracle Branch
コンテスト
ユーザー D M
提出日時 2025-02-07 15:54:13
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 146 ms / 2,000 ms
コード長 2,399 bytes
コンパイル時間 785 ms
コンパイル使用メモリ 82,516 KB
実行使用メモリ 97,856 KB
最終ジャッジ日時 2025-02-07 15:54:24
合計ジャッジ時間 10,475 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 43
権限があれば一括ダウンロードができます

ソースコード

diff # 

#!/usr/bin/env python3
import sys

def main():
    input = sys.stdin.readline
    x = int(input())
    # X=1 の特例
    if x == 1:
        print(2)
        print("1 2")
        print("b g")
        return

    # 200,000 以下の因数で試し割り（200,000 を超える因数があれば後で検出）
    temp = x
    prime_factors = []  # 素因数をリストに列挙
    d = 2
    while d * d <= temp and d <= 200000:
        while temp % d == 0:
            prime_factors.append(d)
            temp //= d
        d += 1
    if temp > 1:
        prime_factors.append(temp)
    
    # もし因数の中に 200,000 を超えるものがあれば，頂点数が必ず制限を超える
    for p in prime_factors:
        if p > 200000:
            print(-1)
            return

    # ここで，素因数リスト prime_factors から「まとめるべき部分」
    # － 2 の因子は，2 個でまとめると 4 として使うと頂点数が減る
    factors = []
    count2 = prime_factors.count(2)
    non_twos = [p for p in prime_factors if p != 2]
    # 2 の個数が偶数なら，そのペアをまとめて 4 を作る
    factors.extend([4] * (count2 // 2))
    # 奇数個なら，最後の 1 つはそのまま 2 とする
    if count2 % 2 == 1:
        factors.append(2)
    # 2 以外の素因数はそのまま使う（それぞれの素因数 p は p+1 の頂点を必要とする）
    factors.extend(non_twos)
    
    # 茶色頂点の数 k と総緑色頂点数（因子和）から全体頂点数を計算
    k = len(factors)
    total_vertices = k + sum(factors)
    if total_vertices > 200000:
        print(-1)
        return

    n = total_vertices
    edges = []
    # 茶色頂点は 1,2,...,k とし，それらを鎖状につなぐ
    for i in range(1, k):
        edges.append((i, i+1))
    # 次に，各茶色頂点 i に対して factors[i-1] 個の緑色頂点を付ける
    current_green = k + 1
    for i, f in enumerate(factors, start=1):
        for _ in range(f):
            edges.append((i, current_green))
            current_green += 1

    # 色は，頂点 1..k を茶色 (b)，残りを緑色 (g) とする
    colors = ["b"] * k + ["g"] * (n - k)

    # 出力（フォーマットに厳密に従う）
    print(n)
    for u, v in edges:
        print(u, v)
    print(" ".join(colors))

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