QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#473863 | #8436. Maximum Product | Oz121 | WA | 59ms | 53832kb | Java11 | 4.4kb | 2024-07-12 14:38:55 | 2024-07-12 14:38:56 |
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]));
}
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