結果

問題 No.3316 Make 81181819 with only 0,1,or 8
コンテスト
ユーザー 37zigen
提出日時 2025-10-31 22:17:10
言語 Java
(openjdk 23)
結果
WA  
実行時間 -
コード長 7,574 bytes
コンパイル時間 2,586 ms
コンパイル使用メモリ 92,188 KB
実行使用メモリ 59,396 KB
最終ジャッジ日時 2025-10-31 22:19:11
合計ジャッジ時間 108,298 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 2 WA * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.Random;
import java.util.Set;

class ModInt {
    long mod;

    public ModInt(long mod) {
        this.mod = mod;
    }
}

class FastScanner {
    private static FastScanner instance = null;

    private final InputStream in = System.in;

    private final byte[] buffer = new byte[1024];

    private int ptr = 0;

    private int buflen = 0;

    private FastScanner() {
    }

    public static FastScanner getInstance() {
        if (instance == null) {
            instance = new FastScanner();
        }
        return instance;
    }

    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        }
        ptr = 0;
        try {
            buflen = in.read(buffer);
        } catch (IOException e) {
            e.printStackTrace();
        }
        return buflen > 0;
    }

    private int readByte() {
        if (hasNextByte()) {
            return buffer[ptr++];
        } else {
            return -1;
        }
    }

    private boolean isPrintableChar(int c) {
        return (33 <= c) && (c <= 126);
    }

    public boolean hasNext() {
        while (hasNextByte() && (!isPrintableChar(buffer[ptr]))) {
            ptr++;
        } 
        return hasNextByte();
    }

    public long nextLong() {
        if (!hasNext()) {
            throw new NoSuchElementException();
        }
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        while ((b >= '0') && (b <= '9')) {
            n = (n * 10) + (b - '0');
            b = readByte();
        } 
        return minus ? -n : n;
    }

    public int nextInt() {
        return ((int) (nextLong()));
    }
}

class MyPrintWriter extends PrintWriter {
    private static MyPrintWriter instance = null;

    private MyPrintWriter() {
        super(System.out);
    }

    public static MyPrintWriter getInstance() {
        if (instance == null) {
            instance = new MyPrintWriter();
        }
        return instance;
    }
}

/**
 * *
 * lenがa.lengthに比べて小さくなっても配列を取り直さない。
 *
 * @param <T>
 */
class MyDeque<T> implements Iterable<T> {
	T[] a = (T[]) new Object[16];
	int head = 0;
	int tail = 0;
	int len = 0;
	//[head, tail)に値を持つ。
	public MyDeque() {
		
	}
	
	public T peekFirst() {
		return a[head];
	}
		
	public T peekLast() {
		return a[(tail - 1) & (a.length - 1)];
	}
	
	void addFirst(T v) {
		if (len == a.length) resize(2 * len);
		head = (head - 1) & (a.length - 1);
		a[head] = v;
		len++;
	}
	
	public void addLast(T v) {
		if (len == a.length) resize(2 * len);
		a[tail] = v;
		tail = (tail + 1) & (a.length - 1);
		++len;
	}
	
	public T pollFirst() {
		if (len == 0) throw new NoSuchElementException();
		T ret = a[head];
		head = (head + 1) & (a.length - 1);
		len--;
		return ret;
	}
	
	public T pollLast() {
		if (len == 0) throw new NoSuchElementException();
		T ret = a[(tail - 1) & (a.length  - 1)];
		tail = (tail - 1) & (a.length - 1);
		len--;
		return ret;
	}
	
	public boolean isEmpty() {
		return len == 0;
	}
	
	public T get(int id) {
		if (id < 0 || id >= len) throw new IndexOutOfBoundsException();
		return a[(head + id) & (a.length - 1)];
	}
	
	void resize(int size) {
		T[] na = (T[]) new Object[size];
		for (int i = 0; i < len; i++) {
			na[i] = a[(head + i) & (a.length - 1)];
		}
		head = 0;
		tail = len;
		a = na;
	}
	
	public int size() {
		return len;
	}
	
	
    @Override
    public Iterator<T> iterator() {
        return new Iterator<T>() {
            int idx = 0;

            @Override
            public boolean hasNext() {
                return idx < len;
            }

            @Override
            public T next() {
                if (!hasNext()) throw new NoSuchElementException();
                T val = get(idx);
                idx++;
                return val;
            }
        };
    }
}

public class Main implements Runnable {
    public static void main(String[] args) throws IOException {
        Thread.setDefaultUncaughtExceptionHandler((t, e) -> System.exit(1));
        // new Main().gen();
        new Thread(null, new Main(), "MainThreadWithLargeStack", (1024 * 1024) * 1024).start();// 1024MBスタックを確保して実行

        // MergeFilesTest.test();
    }

    long mod = ((long) (1.0E9)) + 7;

    Set<Integer> set = new HashSet<>();
    MyDeque<Integer>dq=new MyDeque<Integer>();
    
    {
        dq.addLast(0);
        for (int i = 0; i < 4; i++) {
            int size = dq.size();
            for (int j = 0; j < size; j++) {
                int v = dq.get(j);
                dq.addLast(10 * v);
                dq.addLast((10 * v) + 1);
                dq.addLast((10 * v) + 8);
            }
        }
        for (int v : dq) {
            set.add(v);
        }
    }

    void solve() {
        FastScanner sc = FastScanner.getInstance();
        MyPrintWriter pw = MyPrintWriter.getInstance();
        ArrayList<Integer>[] dp = new ArrayList[((int) (1000000.0))];
        for (int v : set) {
            dp[v] = new ArrayList<>();
            dp[v].add(v);
        }
        for (int i = 0; i < 7; i++) {
            for (int j = dp.length - 1; j >= 0; j--) {
                for (int add : set) {
                    if (((dp[j] != null) && ((j + add) < dp.length)) && (dp[j + add] == null)) {
                        dp[j + add] = ((ArrayList<Integer>) (dp[j].clone()));
                        dp[j + add].add(add);
                    }
                }
            }
        }
        int T = sc.nextInt();
        out : for (int TEST = 0; TEST < T; TEST++) {
            int N = sc.nextInt();
            N = 81181819 - N;
            int ans = Integer.MAX_VALUE;
            for (int j = 0; (j < dp.length) && (j <= N); ++j) {
                if (dp[j] == null) {
                    continue;
                }
                // 下４桁決定済み
                int M = N - j;
                if ((M % 10000) != 0) {
                    continue;
                }
                M /= 10000;
                if (dp[M] != null) {
                    ans = Math.min(ans, Math.max(dp[j].size(), dp[M].size()));
                }
            }
            for (int j = 0; (j < dp.length) && (j <= N); ++j) {
                if (dp[j] == null) {
                    continue;
                }
                // 下４桁決定済み
                int M = N - j;
                if ((M % 10000) != 0) {
                    continue;
                }
                M /= 10000;
                if (dp[M] != null) {
                    if (ans == Math.max(dp[j].size(), dp[M].size())) {
                        System.out.println(ans);
                        for (int i = 0; i < dp[j].size(); i++) {
                            System.out.println((i < dp[j].size() ? dp[j].get(i) : 0) + ((i < dp[M].size() ? dp[M].get(i) : 0) * 10000));
                        }
                        continue out;
                    }
                }
            }
        }
    }

    public void run() {
        var sc = FastScanner.getInstance();
        var pw = MyPrintWriter.getInstance();
        solve();
        pw.flush();
    }
}
0