import java.io.PrintStream; import java.util.Arrays; import java.util.Scanner; /** * Solution to Ducks in a Row * * @author vanb */ public class ducks_vanb { private static Scanner sc; private static PrintStream ps; /** The desired minimum length of a run of Ducks */ private int n; /** The desired number of at-least-n length runs of Ducks */ private int k; /** * A State captures two numbers: The length of the current run of Ducks, * and the number of at-least-n length segments we've seen. * * @author vanb */ private class State implements Comparable { /** The length of the current run of Ducks */ public int run; /** The number of at-least-n length segments we've seen */ public int num; /** * Create a State. * * @param run The length of the current run of Ducks * @param num The number of at-least-n length segments we've seen */ public State( int run, int num ) { this.run = run; this.num = num; } @Override /** * Compare this state to another state. * * @param other Another State * @return Standard for compareTo: <0, 0, or >0 */ public int compareTo( State other ) { // We always want to maximize the number of segments int diff = other.num - num; if( diff==0 ) { // If the number of segments are the same, then it's tricky. // If the last run is also the last segment, well, it's better // to add to the shorter one to get to the next number of segments. // If they're both too short, take the longer one. diff = (Math.max( run, other.run )0 ) { State s = better( flip[i-1][j], noflip[i-1][j-1] ); if( s!=null ) { flip[i][j] = new State( 0, s.num ); } } // Don't flip State s = better( flip[i-1][j], noflip[i-1][j] ); if( s!=null ) { noflip[i][j] = new State( s.run+1, (s.run==n-1) ? s.num+1 : s.num ); if( noflip[i][j].num==k && j0 ) { State s = better( flip[i-1][j], noflip[i-1][j-1] ); if( s!=null ) { flip[i][j] = new State( s.run+1, (s.run==n-1) ? s.num+1 : s.num ); if( flip[i][j].num==k && j