-
Notifications
You must be signed in to change notification settings - Fork 1
/
PrimitiveCalculator.java
60 lines (55 loc) · 1.65 KB
/
PrimitiveCalculator.java
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
52
53
54
55
56
57
58
59
60
import java.util.*;
public class PrimitiveCalculator {
private static int[] genSeq(int a) {
int[] res = new int[a + 1];
res[0] = 0;
res[1] = 0;
for (int i = 2; i <= a; i++) {
if (i % 3 == 0) {
res[i] = Math.min(res[i / 3], res[i - 1]) + 1;
} else if (i % 2 == 0) {
res[i] = Math.min(res[i / 2], res[i - 1]) + 1;
} else {
res[i] = res[i - 1] + 1;
}
}
return res;
}
private static List<Integer> getSequence(int[] seq){
List<Integer> ans = new ArrayList<>();
int i = seq.length - 1;
while (i > 0) {
ans.add(i);
if (i % 3 == 0) {
if (seq[i / 3] == seq[i] - 1) {
i /= 3;
} else {
i -= 1;
}
} else if (i % 2 == 0) {
if (seq[i / 2] == seq[i] - 1) {
i /= 2;
} else {
i -= 1;
}
} else {
i -= 1;
}
}
return ans;
}
private static List<Integer> optimal_sequence(int n) {
int[] seq = genSeq(n);
List<Integer> getSeq = getSequence(seq);
return getSeq;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
List<Integer> sequence = optimal_sequence(n);
System.out.println(sequence.size() - 1);
for(int i = sequence.size() - 1; i >= 0; i--){
System.out.print(sequence.get(i) + " ");
}
}
}