/*************************************************************************
  *  Name:    Donna Gabai 
  *  Login:   dgabai 
  *  Precept: P01
  * 
  *  Compilation:  javac BirthdayPart2.java
  *  Execution:    java BirthdayPart2 max T
  *
  *  Description: input max and T from command line.
  *  For 2 thru max, generate birthdays to find 2 thru max matches.
  *  Repeat T trials.
  *  Output how many generated on average to find 2 thru max matches.
  *************************************************************************/

public class BirthdayPart2 {
    // how many possible birthdays?
    private static final int DAYS = 366;
    
    // find a birthday that repeats M times
    // return how many random birthdays generated before M repeats
    public static int experiment(int M) {
        // set up array to hold matches for possible birthdays
        int[] bdays = new int[DAYS];
        boolean done = false;        // Did we find M repeats?
        int index = -1;              // Which birthday repeated M times?
        int count = 0;               // how many birthdays generated?
        
        // generate birthdays until matches found
        while (!done) {
            int day = (int) (Math.random()*DAYS);
            count++;
            bdays[day]++;
            if (bdays[day] == M) {
                done = true;
                index = day;
            }
        }
        return count;
    }
    
    public static void main(String[] args) {
     
        // command-line inputs
        int MAX = Integer.parseInt(args[0]);
        int T   = Integer.parseInt(args[1]);
        
        // for each value 2 thru MAX
        for (int match = 2; match <= MAX; match++) {
            // sum of how many days generated
            // double to avoid both overflow and int division 
            double sum = 0;  
            
            // T trials
            for (int t = 0; t < T; t++) {
                // sum results
                sum = sum + experiment(match);        
            }

            // average - need rounded answer for output table
            int tableAve = (int) Math.round(sum / T);
            StdOut.println(match + " " + tableAve);
        }
    }
}