結果

問題 No.3316 Make 81181819 with only 0,1,or 8
コンテスト
ユーザー titia
提出日時 2025-10-31 23:30:09
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,536 bytes
コンパイル時間 376 ms
コンパイル使用メモリ 82,668 KB
実行使用メモリ 324,168 KB
最終ジャッジ日時 2025-10-31 23:30:29
合計ジャッジ時間 19,645 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 1 WA * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from functools import lru_cache
from collections import deque

Q=[1,8]
MAX=81181819

SET=set()

while Q:
    x=Q.pop()
    if x<=81181819 and x not in SET:
        SET.add(x)

        for i in [0,1,8]:
            y=x*10+i

            Q.append(y)

LIST=sorted(SET,reverse=True)
@lru_cache(maxsize=None)
def calc(x):
    if x==0:
        return 0,[]

    ANS=1<<60
    FROM=[]

    for s in LIST:
        if s<=x:
            k,L=calc(x-s)
            if k>=8:
                continue
            if k>=ANS-1:
                continue
                

            if ANS>k+1:
                ANS=k+1
                FROM=L+[s]


    return ANS,FROM
            
#for x in range(1000):
#    print(x,calc(x))

T=int(input())

for tests in range(T):
    x=int(input())
    a=MAX-x
    Q=[(a,[])]
    Q=deque(Q)
    USE={a}
    flag0=0

    while flag0==0:
        #print(Q)
        NQ=deque()

        while Q:
            if len(NQ)>=50000:
                break
            x,L=Q.popleft()
            for s in LIST:
                if len(NQ)>=50000:
                    break
                if s>x:
                    continue
                if s==x:
                    flag0=1
                    ANS=L+[s]
                    break
                if x-s not in USE:
                    NQ.append((x-s,L+[s]))
            if flag0==1:
                break
        Q=NQ
        if flag0==1:
            break
                
            

    #print(ANS)

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