Submission #3792300


Source Code Expand

import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.io.IOException;
import java.util.NoSuchElementException;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        FasterScanner in = new FasterScanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Task solver = new Task();
        solver.solve(1, in, out);
        out.close();
    }

    static class Task {
        long[][][][][] memo;

        public void solve(int testNumber, FasterScanner in, PrintWriter out) {
            char[] a = in.next().toCharArray();
            char[] b = in.next().toCharArray();

            int dl = b.length;

            char[] na = new char[dl];
            Arrays.fill(na, '0');
            System.arraycopy(a, 0, na, dl - a.length, a.length);
            a = na;

            memo = new long[dl + 1][2][2][2][2];   // digit more less has4 has9
            memo[0][0][0][0][0] = 1;

            for (int i = 0; i < dl; i++) {
                for (int j = 0; j < 2; j++) {
                    for (int k = 0; k < 2; k++) {
                        for (int l = 0; l < 2; l++) {
                            for (int m = 0; m < 2; m++) {
                                int start = (j == 1) ? 0 : (a[i] - '0');
                                int end = (k == 1) ? 9 : (b[i] - '0');
                                for (int n = start; n <= end; n++) {
                                    int more = (j == 1 || n > start) ? 1 : 0;
                                    int less = (k == 1 || n < end) ? 1 : 0;
                                    int has4 = (l == 1 || n == 4) ? 1 : 0;
                                    int has9 = (m == 1 || n == 9) ? 1 : 0;
                                    memo[i + 1][more][less][has4][has9] += memo[i][j][k][l][m];
                                }
                            }
                        }
                    }
                }
            }

            long ans = 0;
            for (int i = 0; i < 2; i++)
                for (int j = 0; j < 2; j++)
                    for (int k = 0; k < 2; k++)
                        for (int l = 0; l < 2; l++)
                            if ((k | l) == 1)
                                ans += memo[dl][i][j][k][l];
            out.print(ans);
        }

    }

    static class FasterScanner {
        private InputStream in;
        private byte[] buffer;
        private int bufPointer;
        private int bufLength;

        public FasterScanner(InputStream in) {
            this.in = in;
            buffer = new byte[1024];
        }

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

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

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

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

        public String next() {
            if (!hasNext()) throw new NoSuchElementException();
            StringBuilder sb = new StringBuilder();
            int b = readByte();
            while (isPrintableChar(b)) {
                sb.appendCodePoint(b);
                b = readByte();
            }
            return sb.toString();
        }

    }
}

Submission Info

Submission Time
Task D - 禁止された数字
User kawazu
Language Java8 (OpenJDK 1.8.0)
Score 0
Code Size 4075 Byte
Status WA
Exec Time 71 ms
Memory 23508 KB

Judge Result

Set Name Sample Subtask1 Subtask2
Score / Max Score 0 / 0 0 / 30 0 / 70
Status
WA × 4
WA × 16
WA × 39
Set Name Test Cases
Sample subtask0_sample01.txt, subtask0_sample02.txt, subtask0_sample03.txt, subtask0_sample04.txt
Subtask1 subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask0_sample01.txt, subtask0_sample02.txt, subtask0_sample03.txt
Subtask2 subtask0_sample01.txt, subtask0_sample02.txt, subtask0_sample03.txt, subtask0_sample04.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt, subtask2_13.txt, subtask2_14.txt, subtask2_15.txt, subtask2_16.txt, subtask2_17.txt, subtask2_18.txt, subtask2_19.txt, subtask2_20.txt, subtask2_21.txt, subtask2_22.txt
Case Name Status Exec Time Memory
subtask0_sample01.txt WA 70 ms 19668 KB
subtask0_sample02.txt WA 70 ms 20436 KB
subtask0_sample03.txt WA 70 ms 20820 KB
subtask0_sample04.txt WA 70 ms 18004 KB
subtask1_01.txt WA 70 ms 20308 KB
subtask1_02.txt WA 70 ms 20564 KB
subtask1_03.txt WA 69 ms 21332 KB
subtask1_04.txt WA 70 ms 20820 KB
subtask1_05.txt WA 69 ms 20436 KB
subtask1_06.txt WA 70 ms 21332 KB
subtask1_07.txt WA 68 ms 20436 KB
subtask1_08.txt WA 69 ms 21332 KB
subtask1_09.txt WA 69 ms 21588 KB
subtask1_10.txt WA 69 ms 20436 KB
subtask1_11.txt WA 69 ms 21460 KB
subtask1_12.txt WA 69 ms 18900 KB
subtask1_13.txt WA 68 ms 23508 KB
subtask2_01.txt WA 70 ms 20820 KB
subtask2_02.txt WA 70 ms 16468 KB
subtask2_03.txt WA 70 ms 21332 KB
subtask2_04.txt WA 69 ms 20052 KB
subtask2_05.txt WA 68 ms 20436 KB
subtask2_06.txt WA 68 ms 19796 KB
subtask2_07.txt WA 70 ms 16596 KB
subtask2_08.txt WA 69 ms 20820 KB
subtask2_09.txt WA 69 ms 21716 KB
subtask2_10.txt WA 69 ms 20692 KB
subtask2_11.txt WA 68 ms 20692 KB
subtask2_12.txt WA 70 ms 19284 KB
subtask2_13.txt WA 68 ms 19796 KB
subtask2_14.txt WA 70 ms 18516 KB
subtask2_15.txt WA 70 ms 20820 KB
subtask2_16.txt WA 68 ms 20052 KB
subtask2_17.txt WA 68 ms 16468 KB
subtask2_18.txt WA 69 ms 21588 KB
subtask2_19.txt WA 71 ms 21200 KB
subtask2_20.txt WA 70 ms 22740 KB
subtask2_21.txt WA 69 ms 20436 KB
subtask2_22.txt WA 68 ms 17748 KB