結果

問題 No.3316 Make 81181819 with only 0,1,or 8
コンテスト
ユーザー 👑 loop0919
提出日時 2025-10-18 00:01:26
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,113 bytes
コンパイル時間 283 ms
コンパイル使用メモリ 82,248 KB
実行使用メモリ 230,220 KB
最終ジャッジ日時 2025-10-25 17:00:11
合計ジャッジ時間 8,011 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other TLE * 1 -- * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import defaultdict, deque
from itertools import product

Y = 81181819


def dfs(n):
    len_n = len(str(n))

    for prod in product([0, 1, 8], repeat=len_n):
        val = sum([10**i * prod[i] for i in range(len_n)])


def solve():
    N = Y - int(input())

    if N < 10:
        print(N // 8 + N % 8)
        return

    que = deque([(0, N)])
    prev = defaultdict(lambda: None)
    prev[N] = -1  # 終端

    while que:
        dist, n = que.popleft()
        len_n = len(str(n))

        for prod in product([0, 1, 8], repeat=len_n):
            val = n - sum([10**i * prod[~i] for i in range(len_n)])

            if val < 0:
                break

            if prev[val] is not None:
                continue

            if val == 0:
                print(dist + 1)
                prev[val] = n
                while (v := prev[val]) != -1:
                    print(v - val)
                    val = v
                return

            que.append((dist + 1, val))
            prev[val] = n


if __name__ == "__main__":
    T = int(input())
    for _ in range(T):
        solve()
0