// CodeEval Ugly Numbers
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.*;
class Main {
public static void main(String[] args) {
ugly_numbers.main(args);
}
}
class ugly_numbers {
public static void main(String[] args) {
boolean LOCAL_TEST = false;
// LOCAL_TEST = true;// comment it before submitting
if (LOCAL_TEST)
CodeEvalGetInput("e:\\zin.txt");
else
CodeEvalGetInput(args[0]);
}
public static void CodeEvalGetInput(String arg) {
try {
File file = new File(arg);
BufferedReader in = new BufferedReader(new FileReader(file));
Initialize();
String line;
while ((line = in.readLine()) != null) {
String[] lineArray = line.split(",");
if (lineArray.length > 0) {
// Process line of input Here
Process(lineArray);
}
}
} catch (IOException e) {
System.out.println("File Read Error: " + e.getMessage());
}
}
private static void Initialize() {
}
static long totUgly;
private static void Process(String[] lineArray) {
String s0 = lineArray[0].trim();
long lastPart = Long.valueOf(s0.substring(0, 1));
totUgly = 0;
Generate('+', lastPart, s0, 1, lastPart);
System.out.println(totUgly);
}
private static boolean IsUgly(long n) {
if (n == 0 || n % 2 == 0 || n % 3 == 0
|| n % 5 == 0 || n % 7 == 0)
return true;
return false;
}
private static void Generate(char lastSign, long lastPart, String s, int xc,
long currentSum) {
if (xc == s.length()) {
if (IsUgly(currentSum))
totUgly++;
return;
}
else {
String firstChar = String.valueOf(s.charAt(xc));
long newLastPart;
long newCurSum;
// concat
newLastPart = (Math.abs(lastPart) * 10) + Long.valueOf(firstChar);
if (lastSign == '+')
newCurSum = currentSum - lastPart + newLastPart;
else
newCurSum = currentSum + lastPart - newLastPart;
Generate(lastSign, newLastPart, s, xc + 1, newCurSum);
// +
newLastPart = Long.valueOf(firstChar);
newCurSum = currentSum + newLastPart;
Generate('+', newLastPart, s, xc + 1, newCurSum);
// -
newLastPart = Long.valueOf(firstChar);
newCurSum = currentSum - newLastPart;
Generate('-', newLastPart, s, xc + 1, newCurSum);
}
}
}
Very hard to come to a so clean solution :S
ReplyDelete