結果

問題 No.3506 All Distance is Square Number
コンテスト
ユーザー e032_Ashmit_Rana
提出日時 2026-04-18 01:17:12
言語 Python3
(3.14.3 + numpy 2.4.4 + scipy 1.17.1)
コンパイル:
python3 -mpy_compile _filename_
実行:
python3 _filename_
結果
AC  
実行時間 205 ms / 2,000 ms
コード長 3,224 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 611 ms
コンパイル使用メモリ 20,828 KB
実行使用メモリ 15,360 KB
最終ジャッジ日時 2026-04-18 01:17:25
合計ジャッジ時間 9,563 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 29
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys


C = 169
A = [
    121, 19, 6, 131, 146, 87, 79, 70, 31, 34, 30, 59, 199, 99,
    1, 15, 16, 120, 90, 110, 45, 10, 181, 67, 160, 81, 105, 69,
    27, 165, 171, 84, 52, 74, 106, 141, 139, 36, 2, 117, 17, 152,
    92, 32, 104, 48, 95, 7, 47, 196, 76, 37, 55, 40, 197, 23, 26,
    73, 159, 66, 83, 172, 96, 180, 54, 142, 102, 12, 144, 192, 137,
    132, 115, 78, 41, 43, 150, 94, 166, 178, 157, 167, 58, 170, 127,
    187, 62, 168, 138, 143, 57, 186, 68, 151, 128, 190, 198, 136,
]
B = [
    4, 71, 100, 164, 44, 29, 140, 189, 35, 103, 56, 65, 72, 20, 49,
    50, 124, 175, 18, 85, 184, 61, 191, 25, 101, 9, 135, 53, 200,
    155, 5, 60, 154, 149, 118, 98, 130, 97, 183, 194, 14, 13, 91,
    89, 176, 133, 116, 38, 22, 119, 42, 3, 24, 11, 51, 21, 33, 28,
    93, 80, 8, 125, 64, 75, 156, 185, 46, 123, 147, 109, 126, 114,
    177, 77, 161, 148, 88, 107, 188, 108, 86, 112, 145, 134, 162,
    111, 195, 173, 122, 113, 63, 158, 174, 82, 193, 182, 129, 163,
]
SQUARES = {i * i for i in range(1, 50)}


def is_square(x: int) -> bool:
    return x in SQUARES


def leaf_index(v: int) -> int:
    return v - 3


def edge_a(t: int) -> int:
    return 2 + 2 * t


def edge_b(t: int) -> int:
    return 3 + 2 * t


def find_path(i: int, j: int, leaf_count: int) -> list[int]:
    if i == 1 and j == 2:
        return [1]

    if i == 1:
        v = leaf_index(j)
        if is_square(A[v]):
            return [edge_a(v)]
        if is_square(C + B[v]):
            return [1, edge_b(v)]
        for x in range(leaf_count):
            if x != v and is_square(A[x] + B[x] + B[v]):
                return [edge_a(x), edge_b(x), edge_b(v)]

    if i == 2:
        v = leaf_index(j)
        if is_square(B[v]):
            return [edge_b(v)]
        if is_square(C + A[v]):
            return [1, edge_a(v)]
        for x in range(leaf_count):
            if x != v and is_square(A[x] + B[x] + A[v]):
                return [edge_b(x), edge_a(x), edge_a(v)]

    u = leaf_index(i)
    v = leaf_index(j)
    if is_square(A[u] + A[v]):
        return [edge_a(u), edge_a(v)]
    if is_square(B[u] + B[v]):
        return [edge_b(u), edge_b(v)]
    if is_square(A[u] + C + B[v]):
        return [edge_a(u), 1, edge_b(v)]
    if is_square(B[u] + C + A[v]):
        return [edge_b(u), 1, edge_a(v)]
    for x in range(leaf_count):
        if x == u or x == v:
            continue
        if is_square(A[u] + A[x] + B[x] + B[v]):
            return [edge_a(u), edge_a(x), edge_b(x), edge_b(v)]
        if is_square(B[u] + B[x] + A[x] + A[v]):
            return [edge_b(u), edge_b(x), edge_a(x), edge_a(v)]

    raise RuntimeError(f"no square path for {i} {j}")


def main() -> None:
    data = sys.stdin.buffer.read().split()
    if not data:
        return

    n = int(data[0])
    leaf_count = n - 2
    out = [str(2 * n - 3), f"1 2 {C}"]

    for t in range(leaf_count):
        v = t + 3
        out.append(f"1 {v} {A[t]}")
        out.append(f"2 {v} {B[t]}")

    for i in range(1, n + 1):
        for j in range(i + 1, n + 1):
            path = find_path(i, j, leaf_count)
            out.append(f"{len(path)} {' '.join(map(str, path))}")

    sys.stdout.write("\n".join(out) + "\n")


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