-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathA.java
More file actions
51 lines (47 loc) · 1.95 KB
/
Copy pathA.java
File metadata and controls
51 lines (47 loc) · 1.95 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
package atcoder.grand_44;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.Set;
public final class A {
public static void main(String[] args) {
final Scanner in = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
final int t = in.nextInt();
for (int i = 0; i < t; i++) {
final long n = in.nextLong();
final int a = in.nextInt();
final int b = in.nextInt();
final int c = in.nextInt();
final int d = in.nextInt();
in.nextLine();
System.out.println(dfs(n, a, b, c, d));
}
}
private static long dfs(long n, int a, int b, int c, int d) {
final Set<Long> seen = new HashSet<>();
final PriorityQueue<long[]> q = new PriorityQueue<>(Comparator.comparingLong(l -> l[1]));
q.offer(new long[] { n, 0 });
while (!q.isEmpty()) {
final long[] curr = q.remove();
if (curr[0] == 0) {
return curr[1];
}
if (!seen.add(curr[0])) {
continue;
}
q.offer(new long[] { curr[0] / 5, curr[1] + c + (d * (curr[0] % 5)) });
q.offer(new long[] { (curr[0] / 5) + 1, curr[1] + c + (d * (5 - (curr[0] % 5))) });
q.offer(new long[] { curr[0] / 3, curr[1] + b + (d * (curr[0] % 3)) });
q.offer(new long[] { (curr[0] / 3) + 1, curr[1] + b + (d * (3 - (curr[0] % 3))) });
q.offer(new long[] { curr[0] / 2, curr[1] + a + (d * (curr[0] % 2)) });
q.offer(new long[] { (curr[0] / 2) + 1, curr[1] + a + (d * (2 - (curr[0] % 2))) });
if (curr[0] <= Math.floorDiv(Long.MAX_VALUE, d) && curr[1] + curr[0] * d > 0) {
q.offer(new long[] { 0, curr[1] + curr[0] * d });
}
}
return -1;
}
}