結果
| 問題 | No.3408 1215 Segments |
| コンテスト | |
| ユーザー |
 kencho
|
| 提出日時 | 2025-11-25 06:16:30 |
| 言語 | Java (openjdk 23) |
| 結果 |
AC
|
| 実行時間 | 299 ms / 2,500 ms |
| コード長 | 7,942 bytes |
| 記録 | |
| コンパイル時間 | 7,511 ms |
| コンパイル使用メモリ | 82,404 KB |
| 実行使用メモリ | 50,248 KB |
| 最終ジャッジ日時 | 2025-12-14 23:30:17 |
| 合計ジャッジ時間 | 16,949 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 46 |
ソースコード
import java.io.PrintWriter;
import java.io.InputStream;
import java.io.IOException;
import java.util.NoSuchElementException;
public class WriterCode {
public static final int MOD998 = 998244353;
public static final int MOD100 = 1000000007;
public static void main(String[] args) throws Exception {
ContestScanner sc = new ContestScanner();
ContestPrinter cp = new ContestPrinter();
long n = sc.nextLong();
String s = String.valueOf(n);
int len = s.length();
String ans = null;
// Reusable arrays to avoid allocation
int[] counts = new int[10];
// Iterate lengths
for (int l = len; l <= 20; l++) {
minForLen = null;
dfs(0, l, counts, s, l);
if (minForLen != null) {
ans = minForLen;
break;
}
}
cp.println(ans);
cp.close();
}
static String minForLen = null;
// DFS to generate all digit distributions summing to 'total'
static void dfs(int digit, int remaining, int[] counts, String targetStr, int L) {
if (digit == 9) {
counts[9] = remaining;
checkAndUpdate(counts, targetStr, L);
counts[9] = 0; // backtrack
return;
}
for (int i = 0; i <= remaining; i++) {
counts[digit] = i;
dfs(digit + 1, remaining - i, counts, targetStr, L);
}
counts[digit] = 0; // backtrack
}
static void checkAndUpdate(int[] cnt, String targetStr, int L) {
// Fast validity check
if ((L + cnt[0] + cnt[6] + cnt[8]) % 2 != 0)
return;
// Calculate segcnts needed for logic
int s0 = cnt[0] + cnt[2] + cnt[3] + cnt[5] + cnt[6] + cnt[7] + cnt[8] + cnt[9];
int s1 = cnt[0] + cnt[1] + cnt[2] + cnt[3] + cnt[4] + cnt[7] + cnt[8] + cnt[9];
int s2 = L - cnt[2];
int s3 = cnt[0] + cnt[2] + cnt[3] + cnt[5] + cnt[6] + cnt[8] + cnt[9];
int s4 = cnt[0] + cnt[2] + cnt[6] + cnt[8];
int s5 = cnt[0] + cnt[4] + cnt[5] + cnt[6] + cnt[8] + cnt[9];
int s6 = cnt[2] + cnt[3] + cnt[4] + cnt[5] + cnt[6] + cnt[8] + cnt[9];
int base = (s2 + s4) / 2;
int nine = s3 - base;
int one = base - s4;
int zero = (s1 - one) - base;
int seven = base - (s5 - zero + one);
int six = (s0 - zero) - base;
if (one < 0 || zero < 0 || seven < 0 || six < 0 || nine < 0)
return;
if (one > cnt[1])
return;
if (zero > cnt[0])
return;
if (seven > cnt[7])
return;
if (six > cnt[6])
return;
if (nine > cnt[9])
return;
if (s0 - zero - six != base)
return;
if (s1 - one - zero != base)
return;
if (s2 - one != base)
return;
if (s3 - nine != base)
return;
if (s4 + one != base)
return;
if (s5 - zero + one + seven != base)
return;
if (s6 + zero != base)
return;
// If valid, find smallest
String candidate = findSmallest(cnt, targetStr);
if (candidate != null) {
if (minForLen == null) {
minForLen = candidate;
} else {
if (candidate.length() < minForLen.length()
|| (candidate.length() == minForLen.length() && candidate.compareTo(minForLen) < 0)) {
minForLen = candidate;
}
}
}
}
// Find smallest permutation >= targetStr
static String findSmallest(int[] counts, String targetStr) {
int totalDigits = 0;
for (int c : counts)
totalDigits += c;
if (totalDigits > targetStr.length()) {
// Find smallest non-zero digit for the first position
for (int d = 1; d <= 9; d++) {
if (counts[d] > 0) {
StringBuilder sb = new StringBuilder();
sb.append(d);
counts[d]--;
// Append remaining digits in increasing order
for (int k = 0; k <= 9; k++) {
for (int j = 0; j < counts[k]; j++) {
sb.append(k);
}
}
counts[d]++; // backtrack
return sb.toString();
}
}
return null;
} else {
// Same length, need >= targetStr
return solveRecursive(0, true, counts, targetStr);
}
}
static String solveRecursive(int idx, boolean tight, int[] counts, String targetStr) {
if (idx == targetStr.length()) {
return "";
}
int start = tight ? (targetStr.charAt(idx) - '0') : 0;
for (int d = start; d <= 9; d++) {
if (counts[d] > 0) {
counts[d]--;
boolean nextTight = tight && (d == start);
if (!nextTight) {
StringBuilder sb = new StringBuilder();
sb.append(d);
for (int k = 0; k <= 9; k++) {
for (int j = 0; j < counts[k]; j++) {
sb.append(k);
}
}
counts[d]++; // backtrack
return sb.toString();
}
String res = solveRecursive(idx + 1, nextTight, counts, targetStr);
if (res != null) {
counts[d]++; // backtrack
return d + res;
}
counts[d]++; // backtrack
}
}
return null;
}
static class ContestScanner {
private final InputStream in;
private final byte[] buffer = new byte[1024];
private int ptr = 0;
private int buflen = 0;
public ContestScanner() {
this.in = System.in;
}
private boolean hasNextByte() {
if (ptr < buflen) {
return true;
} else {
ptr = 0;
try {
buflen = in.read(buffer);
} catch (IOException e) {
e.printStackTrace();
}
if (buflen <= 0) {
return false;
}
}
return true;
}
private int readByte() {
if (hasNextByte())
return buffer[ptr++];
else
return -1;
}
private static 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();
}
if (b < '0' || '9' < b) {
throw new NumberFormatException();
}
while (true) {
if ('0' <= b && b <= '9') {
n *= 10;
n += b - '0';
} else if (b == -1 || !isPrintableChar(b)) {
return minus ? -n : n;
} else {
throw new NumberFormatException();
}
b = readByte();
}
}
}
static class ContestPrinter extends PrintWriter {
public ContestPrinter() {
super(System.out);
}
}
}