結果

問題 No.3316 Make 81181819 with only 0,1,or 8
コンテスト
ユーザー titia
提出日時 2025-10-31 23:52:55
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 88 ms / 6,000 ms
コード長 1,160 bytes
コンパイル時間 300 ms
コンパイル使用メモリ 82,296 KB
実行使用メモリ 77,416 KB
最終ジャッジ日時 2025-10-31 23:52:59
合計ジャッジ時間 3,287 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from functools import lru_cache
from collections import deque

LIST=[[] for i in range(8)]

LIST[0]=[(0,[])]

Q=[0,1,8]

for i in range(8):
    SET=set()
    for now,L in LIST[i-1]:
        for q in Q:
            if now+q in SET:
                continue
            SET.add(now+q)
            LIST[i].append((now+q,L+[q]))

MAX=81181819

T=int(input())

for tests in range(T):
    x=int(input())
    a=MAX-x

    ANS=[]
    flag=0

    for i in range(8):
        #print("!",i)
        Q=[(a,[0 for i in range(i)],0)]
        Q=deque(Q)
        
        while Q:
            #print(Q)
            x,ANS,now=Q.popleft()
            if x==0:
                flag=1
                LANS=ANS[:]
                break
            
            for s,L in LIST[i]:
                if x%10==s%10 and x>=s:
                    nex=x-s
                    ANS2=ANS[:]
                    for j in range(i):
                        ANS2[j]+=L[j]*(10**now)

                    Q.append((nex//10,ANS2,now+1))

        if flag:
            break

    print(len(LANS))
    for ans in LANS:
        print(ans)
0