QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#473867#8436. Maximum ProductOz121AC ✓63ms54732kbJava114.5kb2024-07-12 14:41:112024-07-12 14:41:12

Judging History

This is the latest submission verdict.

  • [2024-07-12 14:41:12]
  • Judged
  • Verdict: AC
  • Time: 63ms
  • Memory: 54732kb
  • [2024-07-12 14:41:11]
  • Submitted

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]));
        }
        if (ans.isEmpty()) System.out.println(b);
        else 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: 54ms
memory: 48680kb

input:

1 10

output:

9

result:

ok OK

Test #2:

score: 0
Accepted
time: 39ms
memory: 48700kb

input:

51 62

output:

59

result:

ok OK

Test #3:

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

input:

1 1

output:

1

result:

ok OK

Test #4:

score: 0
Accepted
time: 50ms
memory: 53032kb

input:

1 1000000000000000000

output:

999999999999999999

result:

ok OK

Test #5:

score: 0
Accepted
time: 45ms
memory: 50072kb

input:

1000000000000000000 1000000000000000000

output:

1000000000000000000

result:

ok OK

Test #6:

score: 0
Accepted
time: 48ms
memory: 50616kb

input:

5 5

output:

5

result:

ok OK

Test #7:

score: 0
Accepted
time: 44ms
memory: 50496kb

input:

70 79

output:

79

result:

ok OK

Test #8:

score: 0
Accepted
time: 40ms
memory: 49940kb

input:

70 80

output:

79

result:

ok OK

Test #9:

score: 0
Accepted
time: 51ms
memory: 49880kb

input:

3425 3456

output:

3449

result:

ok OK

Test #10:

score: 0
Accepted
time: 48ms
memory: 49312kb

input:

999999999999999997 999999999999999999

output:

999999999999999999

result:

ok OK

Test #11:

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

input:

13 2898

output:

2889

result:

ok OK

Test #12:

score: 0
Accepted
time: 53ms
memory: 49164kb

input:

14 2897

output:

2889

result:

ok OK

Test #13:

score: 0
Accepted
time: 51ms
memory: 48652kb

input:

456053432 456067112

output:

456067112

result:

ok OK

Test #14:

score: 0
Accepted
time: 63ms
memory: 48600kb

input:

111111111111111111 222222222222222222

output:

199999999999999999

result:

ok OK

Test #15:

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

input:

64360 78999

output:

78999

result:

ok OK

Test #16:

score: 0
Accepted
time: 48ms
memory: 48668kb

input:

28011 104546

output:

99999

result:

ok OK

Test #17:

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

input:

17167 17969

output:

17899

result:

ok OK

Test #18:

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

input:

88278 88345

output:

88299

result:

ok OK

Test #19:

score: 0
Accepted
time: 50ms
memory: 50012kb

input:

30343 36941

output:

36899

result:

ok OK

Test #20:

score: 0
Accepted
time: 44ms
memory: 48572kb

input:

12381 12776

output:

12699

result:

ok OK

Test #21:

score: 0
Accepted
time: 56ms
memory: 52760kb

input:

21474 21517

output:

21499

result:

ok OK

Test #22:

score: 0
Accepted
time: 50ms
memory: 49792kb

input:

70176 71753

output:

71699

result:

ok OK

Test #23:

score: 0
Accepted
time: 46ms
memory: 49096kb

input:

100 1000

output:

999

result:

ok OK

Test #24:

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

input:

123645345234123567 124757567312345987

output:

123999999999999999

result:

ok OK

Test #25:

score: 0
Accepted
time: 50ms
memory: 48932kb

input:

780486494154701 204780168467981317

output:

199999999999999999

result:

ok OK

Test #26:

score: 0
Accepted
time: 56ms
memory: 49988kb

input:

549877333042920 279932504133663116

output:

279899999999999999

result:

ok OK

Test #27:

score: 0
Accepted
time: 48ms
memory: 48888kb

input:

334870717087458 269164361460806719

output:

268999999999999999

result:

ok OK

Test #28:

score: 0
Accepted
time: 58ms
memory: 48872kb

input:

716243113764596 279807646223906864

output:

278999999999999999

result:

ok OK

Test #29:

score: 0
Accepted
time: 51ms
memory: 48924kb

input:

626616423994234 489648120316208689

output:

488999999999999999

result:

ok OK

Test #30:

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

input:

157530030642776 289142859147693620

output:

288999999999999999

result:

ok OK

Test #31:

score: 0
Accepted
time: 51ms
memory: 48548kb

input:

969116295013065 37981651701690409

output:

37899999999999999

result:

ok OK

Test #32:

score: 0
Accepted
time: 41ms
memory: 50612kb

input:

765435123543654321 765435123543654324

output:

765435123543654324

result:

ok OK

Test #33:

score: 0
Accepted
time: 46ms
memory: 48848kb

input:

578129945321321681 578129945321321692

output:

578129945321321689

result:

ok OK

Test #34:

score: 0
Accepted
time: 57ms
memory: 48264kb

input:

985431234675843123 985431234675843541

output:

985431234675843499

result:

ok OK

Test #35:

score: 0
Accepted
time: 58ms
memory: 48984kb

input:

547381234759832123 547381234759838451

output:

547381234759837999

result:

ok OK

Test #36:

score: 0
Accepted
time: 47ms
memory: 48760kb

input:

473812348564732184 473812348564764387

output:

473812348564759999

result:

ok OK

Test #37:

score: 0
Accepted
time: 58ms
memory: 49272kb

input:

574831274583452571 574831274583858009

output:

574831274583799999

result:

ok OK

Test #38:

score: 0
Accepted
time: 43ms
memory: 50600kb

input:

474714262133471189 474866569259143246

output:

474799999999999999

result:

ok OK

Test #39:

score: 0
Accepted
time: 51ms
memory: 48816kb

input:

821367374987338732 821374369672573226

output:

821369999999999999

result:

ok OK

Test #40:

score: 0
Accepted
time: 51ms
memory: 53032kb

input:

285936135423542478 285936726954414258

output:

285936699999999999

result:

ok OK

Test #41:

score: 0
Accepted
time: 51ms
memory: 50856kb

input:

677247293875325122 677247719755976514

output:

677247699999999999

result:

ok OK

Test #42:

score: 0
Accepted
time: 55ms
memory: 54732kb

input:

132896614735128778 132896664235958429

output:

132896659999999999

result:

ok OK

Test #43:

score: 0
Accepted
time: 48ms
memory: 51080kb

input:

938121823239542411 938121823714586298

output:

938121823699999999

result:

ok OK

Test #44:

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

input:

899698889389844865 899698889468278213

output:

899698889399999999

result:

ok OK

Test #45:

score: 0
Accepted
time: 59ms
memory: 49252kb

input:

395826553549112593 395826553568673732

output:

395826553559999999

result:

ok OK

Test #46:

score: 0
Accepted
time: 50ms
memory: 48608kb

input:

246161414957811254 246161414958747724

output:

246161414957999999

result:

ok OK

Test #47:

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

input:

143381626947378896 143381626947697772

output:

143381626947689999

result:

ok OK

Test #48:

score: 0
Accepted
time: 55ms
memory: 48632kb

input:

913191883352177948 913191883352178487

output:

913191883352177999

result:

ok OK

Test #49:

score: 0
Accepted
time: 56ms
memory: 48256kb

input:

459215245791812785 459215245791818124

output:

459215245791817999

result:

ok OK

Test #50:

score: 0
Accepted
time: 49ms
memory: 48780kb

input:

855924816615118433 855924816615118589

output:

855924816615118589

result:

ok OK

Test #51:

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

input:

295388628164876714 295388628164876737

output:

295388628164876737

result:

ok OK

Test #52:

score: 0
Accepted
time: 58ms
memory: 48964kb

input:

692997335593784421 692997335593784425

output:

692997335593784425

result:

ok OK