結果

問題 No.3365 Prefix and Suffix X
コンテスト
ユーザー 電たくT
提出日時 2025-11-17 23:40:32
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,480 bytes
コンパイル時間 301 ms
コンパイル使用メモリ 82,852 KB
実行使用メモリ 479,944 KB
最終ジャッジ日時 2025-11-17 23:40:41
合計ジャッジ時間 8,577 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 1
other TLE * 1 -- * 29
権限があれば一括ダウンロードができます

ソースコード

diff # 

T = int(input())

for _ in range(T):
    X,M = input().split()
    M = int(M)
    D = []
    ok = False
    for a in range(19):
        d = []
        for b in range(10):
            d.append((b*(10**a))%M)
        D.append(d)

    for a in range(len(X),19):
        if a <= len(X)*2:
            Ans = [-1]*a
            dm = False
            for b in range(len(X)):
                Ans[b] = X[b]
            for b in range(len(X)):
                if Ans[-1-b] != -1:
                    if Ans[-1-b] != X[-1-b]:
                        dm = True
                else:
                    Ans[-1-b] = X[-1-b]
                    
            if not dm:
                if -1 not in Ans: 
                    A = int("".join(Ans))
                    if A%M == 0:
                        print(A)
                        ok = True 
                        break
            continue
        
        T,S = [],[]
        for b in range(a//2):
            t = dict()
            if b > 0:
                E = T[-1]
            else:
                E = {int(X[-1]):(-1,-1)}
            
            if b < len(X):
                for d in E:
                    t[(d+D[b][int(X[-1-b])]) % M] = (int(X[-1-b]), d)
            else:
                for y in range(10):
                    for d in E:
                        t[(d + D[b][y]) % M] = (y, d)
            T.append(t)
        
        for b in reversed(range(a//2, a)):
            i = a-b-1
            s = dict()
            if i > 0:
                E = S[-1]
            else:
                E = {int(X[0]): (-1,-1)}

            if i < len(X):
                for d in E:
                    s[(d+D[b][int(X[i])]) % M] = (int(X[i]), d)
            else:
                for y in range(10):
                    for d in E:
                        s[(d+D[b][y]) % M] = (y, d)
            S.append(s)

        for t in T[-1]:
            if M-t in S[-1]:
                At, As = t, M-t
                ok = True
                break
        
        if ok:
            Ansl,Ansr = [],[]
            for b in reversed(range(a//2)):
                q, p = T[b][At]
                Ansr.append(str(q))
                At = p
            
            for b in reversed(range(a - a//2)):
                q, p = S[b][As]
                Ansl.append(str(q))
                As = p
                
            Ansl.reverse()

            print("".join(Ansl)+"".join(Ansr))
            break

    if not ok:
        print(-1)
0