-
Notifications
You must be signed in to change notification settings - Fork 2
/
Solution.java
92 lines (73 loc) · 2.15 KB
/
Solution.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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
package com.algorithm.playground.google.codejam._2019.qualification.cryptopangrams;
import java.math.BigInteger;
import java.util.Map;
import java.util.Scanner;
import java.util.TreeMap;
/**
* https://codingcompetitions.withgoogle.com/codejam/round/0000000000051705/000000000008830b
*/
public class Solution {
public static void main(String[] args) {
try (Scanner console = new Scanner(System.in)) {
int tests = console.nextInt();
for (int test = 1; test <= tests; test++) {
//skip n
console.next();
//len
int k = console.nextInt();
// skip the rest of line
console.nextLine();
String line = console.nextLine().trim();
String ans = solve(line, k);
System.out.println(String.format("Case #%s: %s", test, ans));
}
} catch (Exception e) {
e.printStackTrace(System.out);
}
}
static String solve(String line, int k) {
String[] parts = line.split(" ");
BigInteger[] integers = new BigInteger[parts.length];
for (int i = 0; i < parts.length; i++) {
integers[i] = new BigInteger(parts[i]);
}
BigInteger[] phrase = new BigInteger[k + 1];
int idx = 0;
while (integers[idx].equals(integers[idx + 1])) {
idx++;
}
BigInteger first = integers[idx];
BigInteger second = integers[idx + 1];
BigInteger gcb = first.gcd(second);
TreeMap<BigInteger, String> letters = new TreeMap<>();
first = first.divide(gcb);
phrase[idx] = first;
letters.put(first, "");
phrase[idx + 1] = gcb;
letters.put(gcb, "");
second = second.divide(gcb);
phrase[idx + 2] = second;
letters.put(second, "");
BigInteger prev = second;
for (int i = idx + 2; i < k; i++) {
BigInteger curr = integers[i].divide(prev);
phrase[i + 1] = curr;
letters.put(curr, "");
prev = curr;
}
for (int i = idx - 1; i >= 0; i--) {
BigInteger curr = integers[i].divide(phrase[i + 1]);
phrase[i] = curr;
letters.put(curr, "");
}
char ch = 'A';
for (Map.Entry<BigInteger, String> entry : letters.entrySet()) {
entry.setValue(String.valueOf(ch++));
}
StringBuilder ans = new StringBuilder();
for (BigInteger integer : phrase) {
ans.append(letters.get(integer));
}
return ans.toString();
}
}