QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#473867 | #8436. Maximum Product | Oz121 | AC ✓ | 63ms | 54732kb | Java11 | 4.5kb | 2024-07-12 14:41:11 | 2024-07-12 14:41:12 |
Judging History
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