結果

問題 No.3204 Permuted Integer
コンテスト
ユーザー もの
提出日時 2025-07-18 21:29:18
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,165 ms / 2,000 ms
コード長 5,569 bytes
コンパイル時間 284 ms
コンパイル使用メモリ 82,252 KB
実行使用メモリ 131,108 KB
最終ジャッジ日時 2025-07-18 23:35:59
合計ジャッジ時間 23,562 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

############################################################################################
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
 
    if temp!=1:
        arr.append([temp, 1])
 
    if arr==[]:
        arr.append([n, 1])
 
    return arr
def cycle_detection(f, x0):
 
    power = lam = 1
    first = x0
    second = f(x0)
    while first != second:
        if power == lam:
            first = second
            power *= 2
            lam = 0
        second = f(second)
        lam += 1
    first = second = x0
    for i in range(lam):
        second = f(second)
    mu = 0
    while first != second:
        first = f(first)
        second = f(second)
        mu += 1
    return mu, lam
def cycle_detection_lists(f, x0):
    mu, lam = cycle_detection(f, x0)
    before_cycle = [0] * mu
    if mu > 0:
        before_cycle[0] = x0
        for i in range(mu - 1):
            before_cycle[i + 1] = f(before_cycle[i])
 
    cycle = [0] * lam
    cycle[0] = before_cycle[-1] if mu > 0 else x0
    for i in range(lam - 1):
        cycle[i + 1] = f(cycle[i])
    return before_cycle, cycle
 
import bisect,collections,copy,heapq,itertools,math,string,sys,queue,time,random
from decimal import Decimal
def I(): return input()
def IS(): return input().split()
def II(): return int(input())
def IIS(): return list(map(int,input().split()))
def LIIS(): return list(map(int,input().split()))
def comb(n, r):return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]
 
INF=float("inf")
MOD=998244353
MOD2=10**9+7
# sys.setrecursionlimit(10**7)
alpha="ABCDEFGHIJKLMNOPQRSTUVWXYZ"
def bit_count(x):
    return bin(x).count("1")
def yesno(f):
    if f:print("Yes")
    else:print("No")

# import pypyjit
# pypyjit.set_param('max_unroll_recursion=-1')

def prime_factorization(n):
    factors = []
    temp = n
    for i in range(2, int(-(-n**0.5//1)) + 1):
        if temp % i == 0:
            count = 0
            while temp % i == 0:
                count += 1
                temp //= i
            factors.append((i, count))
    if temp != 1:
        factors.append((temp, 1))
    if not factors:
        factors.append((n, 1))
    return factors

#n進数表示
def to_base(n, base):
    if n == 0:
        return [0]
    digits = []
    while n:
        digits.append(n % base)
        n //= base
    return digits[::-1]

class ncr_object:
    def __init__(self, n, mod=MOD):
        self.n = n
        self.mod = mod
        self.fact = [1] * (n + 1)
        for i in range(2, n + 1):
            self.fact[i] = self.fact[i - 1] * i % mod

    def comb(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * pow(self.fact[r], self.mod - 2, self.mod) * pow(self.fact[n - r], self.mod - 2, self.mod) % self.mod

def _ntt(a, invert, mod, root):
    n = len(a)
    j = 0
    for i in range(1, n):
        bit = n >> 1
        while j & bit:
            j ^= bit
            bit >>= 1
        j |= bit
        if i < j:
            a[i], a[j] = a[j], a[i]
    length = 2
    while length <= n:
        # wlen = root^((mod-1)/length) mod mod
        exp = (mod - 1) // length
        wlen = pow(root, exp, mod)
        if invert:
            wlen = pow(wlen, mod - 2, mod)
        for i in range(0, n, length):
            w = 1
            for k in range(i, i + length // 2):
                u = a[k]
                v = a[k + length // 2] * w % mod
                a[k] = (u + v) % mod
                a[k + length // 2] = (u - v + mod) % mod
                w = w * wlen % mod
        length <<= 1
    if invert:
        inv_n = pow(n, mod - 2, mod)
        for i in range(n):
            a[i] = a[i] * inv_n % mod



def convolution_ntt(a, b, mod=998244353, root=3):
    """
    Perform convolution of lists a and b under modulus `mod` using NTT.
    `root` is a primitive root of `mod`, where mod = k*2^m + 1.
    Returns a list of size len(a)+len(b)-1, results mod `mod`.
    """
    n = 1
    while n < len(a) + len(b) - 1:
        n <<= 1
    fa = a + [0] * (n - len(a))
    fb = b + [0] * (n - len(b))
    _ntt(fa, invert=False, mod=mod, root=root)
    _ntt(fb, invert=False, mod=mod, root=root)
    for i in range(n):
        fa[i] = fa[i] * fb[i] % mod
    _ntt(fa, invert=True, mod=mod, root=root)
    return fa[:len(a) + len(b) - 1]

# print(convolution_ntt([1, 2, 3], [4, 5, 6], mod=998244353, root=3))
# pragma GCC target("avx2")
# pragma GCC optimize("O3")
# pragma GCC optimize("unroll-loops")

from fractions import Fraction as fraction

####################################################
st=collections.defaultdict(lambda:INF)
for i in range(1,10**5)[::-1]:
    v=collections.Counter(list(map(int,list(str(i*i)))))
    res=[]
    for j in range(10):
        res.append(v[j])
    st[tuple(res)]=min(st[tuple(res)], i*i)
t=II()
for _ in range(t):
    n=II()
    v=collections.Counter(list(map(int,list(str(n)))))
    li=[]
    for i in range(10):
        li.append(v[i])
    res=st[tuple(li)]
    while li[0]:
        li[0]-=1
        res=min(res, st[tuple(li)])
    print(res if res!=INF else -1)
0