QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#473863#8436. Maximum ProductOz121WA 59ms53832kbJava114.4kb2024-07-12 14:38:552024-07-12 14:38:56

Judging History

你现在查看的是最新测评结果

  • [2024-07-12 14:38:56]
  • 评测
  • 测评结果:WA
  • 用时:59ms
  • 内存:53832kb
  • [2024-07-12 14:38:55]
  • 提交

answer

import java.io.*;
import java.util.*;
public class MaximumProduct {
    public static int numA; public static int numB;
    public static int[] arrA; public static int[] arrB;
    public static void main(String[] args) throws IOException {
        BufferedReader scan = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer l1 = new StringTokenizer(scan.readLine());
        long a = Long.parseLong(l1.nextToken()); long b = Long.parseLong(l1.nextToken());
        create(a,b);

        ArrayList<Integer> ans = new ArrayList<>();
        if (numA!=numB) {
            for (int i = 0;i<numB;i++) {
                if (arrB[i]==0) continue;

                ArrayList<Integer> temp = new ArrayList<>();
                for (int j = 0;j<i;j++) temp.add(arrB[j]);
                if (arrB[i]>1) temp.add(arrB[i]-1);
                while (temp.size()<numB-((arrB[i]>1) ? 0 : 1)) temp.add(9);

                ans = max(ans, temp);
            }
        } else {
            int num = numA;
            ArrayList[][][] dp = new ArrayList[num][2][2];
            for (int i = 0;i<num;i++) {
                for (int j = 0;j<2;j++) {
                    for (int k = 0;k<2;k++) dp[i][j][k] = new ArrayList();
                }
            }

            //i==0
            for (int k = arrA[0];k<=arrB[0];k++) {
                int l = (k==arrA[0]) ? 1 : 0; int r = (k==arrB[0]) ? 1 : 0;
                dp[0][l][r] = new ArrayList(List.of(k));
            }

            for (int i = 1;i<num;i++) {
                ArrayList<Integer> temp = new ArrayList<>();

                //For (i,0,0)
                if (!dp[i-1][0][0].isEmpty()) { temp.addAll(dp[i-1][0][0]); temp.add(9);
                dp[i][0][0] = new ArrayList(max(dp[i][0][0],temp)); }

                if (!dp[i-1][0][1].isEmpty()) { temp.clear(); temp.addAll(dp[i-1][0][1]); temp.add(arrB[i]-1);
                dp[i][0][0] = new ArrayList(max(dp[i][0][0],temp)); }

                if (!dp[i-1][1][0].isEmpty()) { temp.clear(); temp.addAll(dp[i-1][1][0]); temp.add((arrA[i]==9) ? 0 : 9);
                dp[i][0][0] = new ArrayList(max(dp[i][0][0],temp)); }

                if (!dp[i-1][1][1].isEmpty()) { temp.clear(); temp.addAll(dp[i-1][1][1]);
                if (arrA[i]+2<=arrB[i]) {
                    temp.add(arrB[i]-1); dp[i][0][0] = new ArrayList(max(dp[i][0][0], temp));
                }}

                //For (i,0,1)
                if (!dp[i-1][0][1].isEmpty()) { temp.clear(); temp.addAll(dp[i-1][0][1]); temp.add(arrB[i]);
                dp[i][0][1] = new ArrayList(max(dp[i][0][1], temp)); }

                if (!dp[i-1][1][1].isEmpty()) { temp.clear(); temp.addAll(dp[i-1][1][1]);
                if (arrA[i]!=arrB[i]) {
                    temp.add(arrB[i]); dp[i][0][1] = new ArrayList(max(dp[i][0][1], temp));
                }}

                //For (i,1,0)
                if (!dp[i-1][1][0].isEmpty()) { temp.clear(); temp.addAll(dp[i-1][1][0]); temp.add(arrA[i]);
                dp[i][1][0] = new ArrayList(max(dp[i][1][0], temp));}

                if (!dp[i-1][1][1].isEmpty()) { temp.clear(); temp.addAll(dp[i-1][1][1]); temp.add(arrA[i]);
                if (arrA[i]!=arrB[i]) dp[i][1][0] = new ArrayList(max(dp[i][1][0], temp));}

                //For (i,1,1)
                if (!dp[i-1][1][1].isEmpty()) { temp.clear(); temp.addAll(dp[i-1][1][1]);
                if (arrA[i]==arrB[i]) {
                    temp.add(arrA[i]); dp[i][1][1] = new ArrayList(max(dp[i][1][1], temp));
                }}
            }

            ans = new ArrayList(max(ans, dp[num-1][0][0])); ans = new ArrayList(max(ans, dp[num-1][0][1])); ans = new ArrayList(max(ans, dp[num-1][1][0])); ans = new ArrayList(max(ans, dp[num-1][1][1]));
        }
        for (int i : ans) System.out.print(i);
    }

    public static ArrayList<Integer> max(ArrayList<Integer> l1, ArrayList<Integer> l2) {
        long prod1 = 1;
        for (int i : l1) prod1 *= i;

        long prod2 = 1;
        for (int i : l2) prod2 *= i;

        if (prod1>prod2) return l1;
        return l2;
    }

    public static void create(long a, long b) {
        while (Math.pow(10, numA)<=a) numA++;
        while (Math.pow(10, numB)<=b) numB++;

        arrA = new int[numA]; arrB = new int[numB];
        for (int i = numA-1;i>=0;i--) { arrA[i] = (int) (a%10); a = a/10;}
        for (int i = numB-1;i>=0;i--) { arrB[i] = (int) (b%10); b = b/10;}
    }
}

詳細信息

Test #1:

score: 100
Accepted
time: 48ms
memory: 48724kb

input:

1 10

output:

9

result:

ok OK

Test #2:

score: 0
Accepted
time: 42ms
memory: 48736kb

input:

51 62

output:

59

result:

ok OK

Test #3:

score: 0
Accepted
time: 52ms
memory: 48464kb

input:

1 1

output:

1

result:

ok OK

Test #4:

score: 0
Accepted
time: 52ms
memory: 52488kb

input:

1 1000000000000000000

output:

999999999999999999

result:

ok OK

Test #5:

score: -100
Wrong Answer
time: 59ms
memory: 53832kb

input:

1000000000000000000 1000000000000000000

output:


result:

wrong output format Unexpected end of file - int64 expected