結果

問題 No.3204 Permuted Integer
コンテスト
ユーザー amesyu
提出日時 2025-07-22 17:43:33
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 446 ms / 2,000 ms
コード長 2,140 bytes
コンパイル時間 362 ms
コンパイル使用メモリ 82,776 KB
実行使用メモリ 109,848 KB
最終ジャッジ日時 2025-07-22 17:43:46
合計ジャッジ時間 12,694 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

# Generated By Gemini 2.5 Pro

import sys

# --- 事前計算 ---
# プログラム開始時に一度だけ実行する
# maps_by_len[d] は、d桁の数に対する {桁の構成: 最小の平方数} を格納する辞書
maps_by_len = [{} for _ in range(11)] 

# Nは最大10^9 (10桁)。並び替えた数も10桁以下になる。
# 10桁以下の最大の平方数は (10^10-1) なので、その平方根までループすれば十分。
limit = int((10**10)**0.5)

for i in range(limit + 1):
    square = i * i
    s_str = str(square)
    len_s = len(s_str)
    
    # この平方数sが、d桁の数Nの並び替えで作れる場合を考える (d >= len_s)
    # 不足分は先頭の'0'で補う
    for d in range(len_s, 11):
        # d桁になるように左側を'0'で埋める
        padded_str = s_str.zfill(d)
        # 桁の構成をタプル（辞書のキーとして使える）にする
        signature = tuple(sorted(padded_str))
        
        # この構成がまだ辞書になければ、現在の平方数を追加する
        # iが小さい順なので、最初に追加されたものが最小の平方数となる
        if signature not in maps_by_len[d]:
            maps_by_len[d][signature] = square

# --- メイン処理 ---
def solve():
    """
    1つのテストケースを解決する関数
    事前計算された結果をO(1)で検索する
    """
    n_str = sys.stdin.readline().strip()
    if not n_str:
        return
        
    n_len = len(n_str)
    n_signature = tuple(sorted(n_str))
    
    # 対応する桁数の辞書から、Nの桁構成に一致する答えを取得する
    # 存在しない場合は -1 を返す (dict.getのデフォルト値)
    result = maps_by_len[n_len].get(n_signature, -1)
    print(result)


def main():
    """
    T個のテストケースを処理する
    """
    try:
        t_str = sys.stdin.readline()
        if not t_str:
            return
        T = int(t_str)
        
        for _ in range(T):
            solve()
            
    except (IOError, ValueError):
        return

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