/* Import the Java I/O package */
import java.io.*;
import AppletConsoleApp;

/**
 * Solution to the 1999 British Informatics Olympiad exam
 * question 3: Playing Games
 *
 * This application that can be run either from the console
 * as a stand-alone application or from an in-applet
 * console created with the AppletConsole applet.
 *
 * Solution copyright (c) 1999 The British Informatics Olympiad (BIO).
 *
 * This program may be freely copied by persons or organisations
 * involved in the British Informatics Olympiad or the International
 * Olympiad in Informatics, on condition that no changes are made and
 * this notice is not altered. Distribution for profit is forbidden
 * unless permission is first obtained in writing from the BIO.
 *
 * This program is for educational purposes only and comes with no
 * warranty, implied or otherwise, as to its fitness for any purpose.
 *
 * Author:     Antony Rix
 * Internet:   http://www.christs.cam.ac.uk/bio/
 * E-mail:     a.rix@lineone.net
 * S-mail:     The British Informatics Olympiad
 *             Christ's College
 *             Cambridge CB2 3BU
 *             United Kingdom
 *
 * @author    Antony Rix
 * @version 0.1
 * @see         AppletConsoleApp
 * @see         AppletConsole
 */
class BIO99R1Q3App extends AppletConsoleApp {
    /**
     * Start the application from the command line.
     */
    public static void main(String[] args) {
        BIO99R1Q3App thisApp = new BIO99R1Q3App();
        thisApp.redirectStreams(System.in, System.out);
        thisApp.run();
    }

    /**
     * A StreamTokenizer object allow us to easily read in the input.
     */
    StreamTokenizer sin;

    /**
     * The implementation of this application.
     */
    public void run() {
        int opt;
        try {
            /* StreamTokenizer to read input */
            sin = new StreamTokenizer( in );

            do {
                out.println(
                    "BIO'99 question 3. Enter one of the following options." );
                out.println(
                    "1 Simple (and often incorrect) greedy solution to part 3a" );
                out.println(
                    "2 Test the dynamic programming method" );
                out.println(
                    "3 Full, correct dynamic programming solution to part 3a" );
                out.println(
                    "4 Solution to part 3c" );
                out.println(
                    "\n0 Exit" );
                out.print( ">" );
                sin.nextToken();
                opt = (int)sin.nval;
                switch (opt) {
                    case 1: if( read_input() ) { solve_greedy(); } break;
                    case 2: test_dynamic(); break;
                    case 3: if( read_input() ) { solve_dynamic(); } break;
                    case 4: part_3c(); break;
                }
                out.print( "\n" );
            } while (opt != 0);
        } catch (IOException e) { out.println("I/O failure"); };
        out.println( "Program finished." );
    }

    /**
     * Input data.
     */
    int n;
    int[] scores = new int[10];
    int m;
    int[] totals = new int[10];

    /**
     * Arrays used for the dynamic programming solution.
     */
    int[] num_rounds = new int[1001];
    int[] last_score = new int[1001];

    /**
     * Get the input for part 3a.
     */
    public boolean read_input() {
        int i;
        try {
            out.print( "Value of n:" );
            sin.nextToken();
            n = (int)sin.nval;
            if( (n < 1) || (n > 10) ) {
                out.println( "n must be from 1 to 10!" );
                return false;
            }
            out.print( "Enter " + n + " different positive scores separated by space.\n:" );
            for( i = 0; i < n; i++ ) {
                sin.nextToken();
                scores[i] = (int)sin.nval;
                if( (scores[i] < 1) || (scores[i] > 1000) ) {
                    out.println( "Scores must be from 1 to 1000!" );
                    return false;
                }
            }
            out.print( "Value of m:" );
            sin.nextToken();
            m = (int)sin.nval;
            if( (m < 1) || (m > 10) ) {
                out.println( "m must be from 1 to 10!" );
                return false;
            }
            out.print( "Enter " + m + " totals separated by space.\n:" );
            for( i = 0; i < m; i++ ) {
                sin.nextToken();
                totals[i] = (int)sin.nval;
            }
        } catch (IOException e) { out.println("I/O failure"); return false; };
        return true;
    }

    /**
     * Simple, greedy solution to the problem.  This is often incorrect.
     */
    public void solve_greedy() {
        int i, j, s, r;
        int[] num = new int[10];

        /* Sort the scores into decreasing order using a bubble sort */
        for( i = 1; i < n; i++ ) for( j = 1; j < n; j++ )
            if( scores[j] > scores[j-1] ) {
                s = scores[j]; scores[j] = scores[j-1]; scores[j-1] = s;
            }
        /* Test the sort using the following statement */
        /* for( i = 0; i < n; i++ ) out.println( scores[i] ); */

        /* For each total, allocate the scores in a greedy manner */
        for( i = 0; i < m; i++ ) {
            for( j = 0; j < n; j++ ) num[j] = 0;
            s = totals[i];
            j = 0;
            r = 0;
            while( (s != 0) && (j < n) ) {
                /* Test if score[j] is possible.  If so, choose it, otherwise
                   move on to the next score. */
                if( s >= scores[j] ) {
                    s = s - scores[j];
                    num[j] = num[j] + 1;
                    r = r + 1;
                }
                else
                    j = j + 1;
            }
            /* Show result for this total in increasing order of score if
               it has been possible to get the right total, or print Impossible */
            if( s == 0 ) {
                out.print( "Total " + totals[i] + " in " + r + " rounds:" );
                for( j = n-1; j >= 0; j-- ) if( num[j] > 0 )
                    out.print( " " + num[j] + "x" + scores[j] );
                out.print( "\n" );
            }
            else
                out.print( "Total " + totals[i] + " is Impossible\n" );
        }
    }

    /**
     * Finds the possible scores and (for testing) displays them if required.
     * Uses a dynamic programming method.
     */
    public void find_dynamic( boolean show ) {
        int i, j;

        /* Initialise the arrays that store the number of rounds required to
           reach each value, and the last score. */
        for( i = 1; i <= 1000; i++) {
            num_rounds[i] = 9999;
            last_score[i] = 9999;
        }
        num_rounds[0] = 0;
        last_score[0] = 0;

        /* Find the scores required to reach each total */
        i = 0;
        while( i <= 1000 ) {
            /* For each possible score, see if the new totals are reached
               in fewer rounds than before. */
            for( j = 0; j < n; j++ ) if( i + scores[j] <= 1000 )
                if( num_rounds[i + scores[j]] > num_rounds[i] + 1 ) {
                    num_rounds[i + scores[j]] = num_rounds[i] + 1;
                    last_score[i + scores[j]] = scores[j];
                }

            /* Show the steps leading to this point */
            if( (i > 0) && show ) {
                out.print( i + ":" );
                j = i;
                while( j > 0 ) {
                    out.print( last_score[j] + " " );
                    j = j - last_score[j];
                }
                out.print( "\n" );
            }

            /* Find the next valid total */
            while( true ) {
                i++;
                if( i > 1000 ) break; /* We are off the end of the array */
                if( num_rounds[i] < 9999 ) break; /* We have a valid total */
            }
        }
    }

    /**
     * Illustrates the dynamic method.
     */
    public void test_dynamic() {
        int i;

        /* Read in the scores */
        try {
            out.print( "Value of n:" );
            sin.nextToken();
            n = (int)sin.nval;
            if( (n < 1) || (n > 10) ) {
                out.println( "n must be from 1 to 10!" );
                return;
            }
            out.print( "Enter " + n + " different positive scores separated by space.\n:" );
            for( i = 0; i < n; i++ ) {
                sin.nextToken();
                scores[i] = (int)sin.nval;
                if( (scores[i] < 1) || (scores[i] > 1000) ) {
                    out.println( "Scores must be from 1 to 1000!" );
                    return;
                }
            }
        } catch (IOException e) { out.println("I/O failure"); return; };

        /* Use find_dynamic to find and show the results */
        find_dynamic( true );
    }

    /**
     * Full dynamic programming solution to 3a using find_dynamic.
     */
    public void solve_dynamic() {
        int i, j, p, c;

        /* Use find_dynamic to find the possible totals */
        find_dynamic( false );

        /* For each required total, test if it is reachable */
        for( i = 0; i < m; i++ ) {
            if( (totals[i] < 1) || (totals[i] > 1000) )
                out.print( "Total " + totals[i] + " is Impossible - out of range" );
            else if( num_rounds[totals[i]] == 9999 )
                out.print( "Total " + totals[i] + " is Impossible" );
            else {
                out.print( "Total " + totals[i] + " in " + num_rounds[totals[i]] + " rounds:" );
                /* Find the number of times each score is required. */
                for( p = 0; p < n; p++ ) {
                    c = 0;
                    j = totals[i];
                    while( j > 0 ) {
                        if( last_score[j] == scores[p] ) c++;
                        j = j - last_score[j];
                    }
                    if( c > 0 )
                        out.print( " " + c + "x" + scores[p] );
                }
            }
            out.print( "\n" );
        }
    }

    /**
     * Solution to part 3c.
     * Remus is playing a game where it is possible to score
     * 1, 4, 5, 17, 28, 43 or 100 each round. At the end of the game the final
     * score is 100. Furthermore, the scores for each round never got worse,
     * e.g. if 17 was scored in one round then the score for every future
     * round was at least 17. How many different ways might this have happened?
     */
    int[] scores3c = { 1, 4, 5, 17, 28, 43, 100 };
    public void part_3c() {
        /* To solve this we use a slightly different method.  As there is
           a score of 1 any score between 1 and 100 is possible; the problem
           is to count the number of permutations that reach each total.
           We do this using the recursive procedure perms_3c(). */
        out.println( "Number of different ways: " + perms_3c( 100, 6 ) );
    }
    public int perms_3c( int total, int num ) {
        /* Returns the number of permutations of the first num scores that
           sum to total, in strictly increasing order.  Calls itself. */
        int perms = 0;
        int current = total;

        /* There is only one way to reach a total of zero. */
        if( total == 0 ) return 1;

        /* There is only one way to reach any total using only 1s. */
        if( num == 0 ) return 1;

        /* Otherwise we count the permutations that finish with zero or
           more instances of the last number. */
        while( current >= 0 ) {
            perms = perms + perms_3c( current, num-1 );
            current = current - scores3c[num];
        }
        return perms;
    }
}