import java.io.*; import java.lang.reflect.Array; import java.util.*; import java.awt.geom.*; /** * Solution to Heads or Tails * * @author vanb */ public class headsortails { public Scanner sc; public PrintStream ps; /** * Compute nCm, the number of ways to randomly * select m things from a group of n, where order doesn't matter. * * @param n n * @param m m * @return nCm */ public long choose( long n, long m ) { long result = 1L; if( m>=0 && n>=m ) { m = Math.min( m, n-m ); for( long i=0; i configs = new LinkedList(); // adjacents[i][j] is the number of adjacent coins (including itself) // of the coin at board position (i,j) int adjacents[][] = new int[7][7]; for(;;) { /// Read in the 6 parameters int n = sc.nextInt(); int m = sc.nextInt(); int k = sc.nextInt(); int a = sc.nextInt(); int b = sc.nextInt(); long c = sc.nextLong(); if( n==0 && m==0 ) break; // Total number of coins on the board double ncoins = n*m; // Compute counts[] and adjacents[][] Arrays.fill( counts, 0 ); for( int i=0; i0 ? 1.0 : 0.0; // Go through k random presses for( int i=0; i0 ) { // At each step, the coin is a Head if: // 1) It starts out as a head and you press one of the ncoins-j other coins // that won't flip it, or // 2) It starts out as a tail, and you press one of the j coins that flips it prob[j] = prob[j]*((ncoins-j)/ncoins) + (1.0-prob[j])*(j/ncoins); } } // Figure out the expected number of Heads // if we start with a given configuration. // If it's in the range of interest, remember it. // (We'll skip 0. Since we count the coin itself as a neighbor, // every coin must have at least one neighbor.) configs.clear(); for( int i1=0; i1<=counts[1]; i1++ ) for( int i2=0; i2<=counts[2]; i2++ ) for( int i3=0; i3<=counts[3]; i3++ ) for( int i4=0; i4<=counts[4]; i4++ ) for( int i5=0; i5<=counts[5]; i5++ ) { double expected = i1*prob[1] + (counts[1]-i1)*(1.0-prob[1]); expected += i2*prob[2] + (counts[2]-i2)*(1.0-prob[2]); expected += i3*prob[3] + (counts[3]-i3)*(1.0-prob[3]); expected += i4*prob[4] + (counts[4]-i4)*(1.0-prob[4]); expected += i5*prob[5] + (counts[5]-i5)*(1.0-prob[5]); // If the expected number of heads is in the range [a,b], then // remember the configuration if( a<=expected && expected<=b ) { configs.add( new int[] { 0, i1, i2, i3, i4, i5 } ); } } // Build up the grid char grid[][] = new char[n][m]; Arrays.fill( heads, 0 ); long index = 0L; for( int i=0; icounts[t] ) possible=false; // If we already have placed more than we need, we're hosed. if( config[t]0 ) { // This is the total number of ways to fill // the slots we haven't filled yet, with // the number of Heads we need. total *= choose( counts[t], config[t]-heads[t] ); } increment += total; } } // Does this not take us far enough? if( index+increment