Skip to content

Instantly share code, notes, and snippets.

@dualbus
Created April 11, 2016 12:22
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save dualbus/53dfa7d981d5dbe76dbe82ac5dfd24fd to your computer and use it in GitHub Desktop.
Save dualbus/53dfa7d981d5dbe76dbe82ac5dfd24fd to your computer and use it in GitHub Desktop.
import java.io.BufferedReader;
import java.io.FileReader;
import java.util.Arrays;
import java.io.FileNotFoundException;
import java.io.IOException;
public class A {
public static int solution(int N) {
int[] seen;
int i;
seen = new int[10];
Arrays.fill(seen, 0);
if(N == 0) return -1;
for(i = 1;; i++) {
int seenAll = 0;
//System.out.println(i * N);
for(char c : Integer.toString(i * N).toCharArray()) {
seen[Character.getNumericValue(c)]++;
}
for(int j = 0; j < 10; j++) {
if(seen[j] > 0) seenAll++;
}
if(seenAll >= 10) break;
}
return i * N;
}
public static void main(String[] args) {
try {
int count;
BufferedReader in = new BufferedReader(new FileReader(args[0]));
count = Integer.parseInt(in.readLine());
for(int i = 0; i < count; i++) {
int N = Integer.parseInt(in.readLine());
int s = solution(N);
System.out.printf("Case #%d: %s\n",
i + 1, (s == -1) ? "INSOMNIA" : s
);
}
} catch(FileNotFoundException e) {
} catch(IOException e) {
}
}
}
import java.io.BufferedReader;
import java.io.FileReader;
import java.util.Arrays;
import java.io.FileNotFoundException;
import java.io.IOException;
public class B {
public static int solution(char[] stack) {
int n;
int i;
char[] slice;
//System.out.println(new String(stack));
n = stack.length;
if(n < 1) return 0;
if(n == 1) {
if(stack[0] == '+') return 0;
if(stack[0] == '-') return 1;
}
for(i = n - 1; i >= 0; i--)
if(stack[i] == '-') break;
//System.out.println(i);
if(i < 0) return 0;
slice = new char[i + 1];
for(int j = 0; j <= i; j++)
slice[j] = (stack[j] == '+') ? '-' : '+';
return solution(slice) + 1;
}
public static void main(String[] args) {
try {
int count;
BufferedReader in = new BufferedReader(new FileReader(args[0]));
count = Integer.parseInt(in.readLine());
for(int i = 0; i < count; i++) {
System.out.printf("Case #%d: %d\n",
i + 1, solution(in.readLine().toCharArray())
);
}
} catch(FileNotFoundException e) {
} catch(IOException e) {
}
}
}
import java.util.Arrays;
import java.util.ArrayList;
// Numbers between 2**(N-1) + 1 & 2**N - 1
// Numbers between 3**(N-1) + 1 & 3**N - 1
public class C {
public static long p(int base, int power) {
return (long)Math.pow(base, power);
}
public static long getFactor(long N) {
long n = (long)Math.sqrt(N);
for(long i = 2; i <= n; i++)
if(N % i == 0) return i;
return 0;
}
public static long changeBase(long N, int base) {
long i, acc;
int k = 0;
for(i = N, acc = 0; i >= 2; i = i / 2, k++) {
acc += p(base, k) * (i % 2);
}
return acc + p(base, k) * i;
}
public static void main(String[] args) {
//int N = 16, J = 50;
int N = 32, J = 500;
//int N = 6, J = 3;
ArrayList<Long> coins = new ArrayList<Long>();
outer:
for(long i = p(2, N - 1) + 1; i <= p(2, N); i += 2) {
if(getFactor(i) == 0) continue;
for(int j = 3; j <= 10; j++) {
if(getFactor(changeBase(i, j)) == 0) {
continue outer;
}
}
if(J-- < 1) break;
coins.add(i);
}
System.out.println("Case #1:");
for(long i : coins) {
System.out.print(Long.toBinaryString(i));
System.out.print(" " + getFactor(i));
for(int j = 3; j <= 10; j++) {
System.out.print(" " + getFactor(changeBase(i, j)));
}
System.out.println();
}
}
}
@dualbus
Copy link
Author

dualbus commented Apr 11, 2016

Some tips for C.java:

  • It's only numbers between 2**(N-1) + 1 and 2**N - 1. For example, for N = 4, you only have to search between 2**3 + 1 (9) and 2**4 - 1 (15). The reason for this is that numbers are of the form: 1XXX, so it means the higher bit is always set, and that limits the amount of numbers in the range.
  • Also, it's only odd numbers, since the last bit is 1, like this 1XX1. It means that for N = 4, the only possible numbers to try are: 9 (1001), 11 (1011), 13 (1101) and 15 (1111).
  • It's easier to do it this way, since for N = 32, you only have to try: ( [2 ** 32 - 1] - [2 ** 31 + 1] ) / 2 possibilities, that is: 1,073,741,823 numbers (instead of 2**32, 8589934591)
  • My error was that this algorithm behaves bad when it encounters primes, because the getFactor function will try all numbers from 2 to sqrt(P), where P is the prime, for every prime it encounters. If there are enough big prime numbers in that interval, it will consume most of the program's time.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment