//Google Code Jam Round 1A 2009 A Multi-base happiness (small input)
import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;
//Google Code Jam
public class GoogleCode1 {
private static MyScanner in;
private static PrintStream out;
static HashSet<Integer>[] happynums;
static HashSet<Integer>[] unhappynums;
private static void solve() throws IOException
{
PreCalculate();
int C = in.nextInt();
in.nextLine();
for (int i = 0; i < C; i++) {
out.print("Case #" + (i + 1) + ": ");
solveCase();
}
}
static boolean[][] hhh = new boolean[11][12000000];
private static void PreCalculate() {
happynums = new HashSet[11];
unhappynums = new HashSet[11];
for (int base = 2; base <= 10; base++) {
happynums[base] = new HashSet<>();
unhappynums[base] = new HashSet<>();
}
// limit: 11814485
for (int n = 2; n < 11815000; n++) {
for (int base = 2; base <= 10; base++) {
if (n == 11814485)
n = n + 0;
boolean hp = IsHappy(n, base);
hhh[base][n] = hp;
}
}
}
private static boolean IsHappy(int n, int base) {
if (base == 2)
return true;
if (happynums[base].contains(n)) {
return true;
}
if (unhappynums[base].contains(n)) {
return false;
}
int x = n;
int sum = 0;
HashSet<Integer> nums = new HashSet<>();
boolean happy = false;
while (true) {
sum = 0;
if (nums.contains(x)) {
happy = false;
break;
}
if (x < 1000)
nums.add(x);
while (x > 0) {
int r = x % base;
sum += r * r;
x = x / base;
}
// out.println(sum);
if (happynums[base].contains(sum)) {
happy = true;
break;
}
if (unhappynums[base].contains(sum)) {
happy = false;
break;
}
if (sum == 1) {
happy = true;
break;
}
x = sum;
}
if (happy) {
happynums[base].addAll(nums);
}
else {
unhappynums[base].addAll(nums);
}
return happy;
}
private static void solveCase() throws IOException {
String line = in.nextLine();
String[] sbases = line.split(" ");
int len = sbases.length;
int[] b = new int[len];
for (int i = 0; i < sbases.length; i++) {
b[i] = Integer.valueOf(sbases[i]);
}
int ans = 0;
for (int n = 2; n < 11815000; n++) {
boolean allHappy = true;
for (int i = 0; i < b.length; i++) {
int base = b[i];
if (n == 11814485)
n = n + 0;
// boolean hp = IsHappy(n, base);
boolean hp = hhh[base][n];
allHappy = allHappy & hp;
if (!allHappy) {
break;
}
}
if (allHappy) {
ans = n;
break;
}
}
out.println(ans);
}
public static void main(String[] args) throws IOException {
// helpers for input/output
boolean usingFileForIO = true;
if (usingFileForIO) {
// using input.txt and output.txt as I/O
in = new MyScanner("E:\\zin.txt");
out = new PrintStream("E:\\zout.txt");
}
else {
in = new MyScanner();
out = System.out;
}
solve();
}
// =====================================
static class MyScanner {
Scanner inp = null;
public MyScanner() throws IOException
{
inp = new Scanner(System.in);
}
public MyScanner(String inputFile) throws IOException {
inp = new Scanner(new FileInputStream(inputFile));
}
public int nextInt() throws IOException {
return inp.nextInt();
}
public long nextLong() throws IOException {
return inp.nextLong();
}
public double nextDouble() throws IOException {
return inp.nextDouble();
}
public String nextString() throws IOException {
return inp.next();
}
public String nextLine() throws IOException {
return inp.nextLine();
}
}
}
No comments:
Post a Comment