結果
| 問題 |
No.3316 Make 81181819 with only 0,1,or 8
|
| コンテスト | |
| ユーザー |
 37zigen
|
| 提出日時 | 2025-11-01 00:34:32 |
| 言語 | Java (openjdk 23) |
| 結果 |
AC
|
| 実行時間 | 4,614 ms / 6,000 ms |
| コード長 | 7,598 bytes |
| コンパイル時間 | 5,060 ms |
| コンパイル使用メモリ | 92,384 KB |
| 実行使用メモリ | 59,308 KB |
| 最終ジャッジ日時 | 2025-11-01 00:36:38 |
| 合計ジャッジ時間 | 113,250 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 22 |
ソースコード
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 < Math.max(dp[j].size(), dp[M].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();
}
}