Having three black objects B and one white object W they can be grouped in 7 ways like this:
(BBBW) | (B,BBW) | (B,B,BW) | (B,B,B,W) | (B,BB,W) | (BBB,W) | (BB,BW) |
In how many ways can sixty black objects B and forty white objects W be thus grouped?
Having three black objects B and one white object W they can be grouped in 7 ways like this:
(BBBW) | (B,BBW) | (B,B,BW) | (B,B,B,W) | (B,BB,W) | (BBB,W) | (BB,BW) |
In how many ways can sixty black objects B and forty white objects W be thus grouped?
public final class p181 {
public static void main(String[] args) {
long start=System.nanoTime();
String result = run();
long end=System.nanoTime();
System.out.println(result);
System.out.println( (end-start)/1000000 + "ms" );
}
static int maxIndex[]=new int[]{40,60};
static int size;
static long d[];
public static String run(){
size = 1;
for (int m : maxIndex) {
size *= m + 1;
}
d = new long[size];
d[0] = 1;
return ""+solve();
}
static public long solve() {
int zero[] = new int[maxIndex.length];
int add[] = new int[maxIndex.length];
while (increment(add, zero)) {
int start[] = new int[maxIndex.length];
int end[] = new int[maxIndex.length];
for (boolean ok = true; ok; ok = increment(start, add)) {
for (int i = 0; i < maxIndex.length; i++) {
end[i] = start[i] + add[i];
}
int start1 = encode(start);
int end1 = encode(end);
d[end1] += d[start1];
}
}
return d[size - 1];
}
static public int encode(int[] start) {
int result = 0;
int digitValue = 1;
for (int i = 0; i < maxIndex.length; i++) {
result += digitValue * start[i];
digitValue *= maxIndex[i] + 1;
}
return result;
}
/**
* @return false if increment overflows
*/
static public boolean increment(int[] index, int[] headRoom) {
for (int i = 0; i < maxIndex.length; i++) {
if (index[i] + headRoom[i] < maxIndex[i]) {
index[i]++;
return true; // increment accomplished
}
index[i] = 0; // zero and carry
}
return false;
}
}
83735848679360680
64ms