using System;
using System.Collections.Generic;
using System.Text;
using System.Collections;

namespace _2313_raffle
{
    class Program
    {
        static void Main(string[] args)
        {
            int p;
            int n;
            UInt64 count = 0; // use an unsigned long 64 bit int to keep a large number

            DateTime startTime;
            DateTime finishTime;
            TimeSpan timeToComplete;

            Random r = new Random();

            // prompt the user for the number of prizes (p)
            Console.Write("Please enter the number of prizes: ");
            p = Int32.Parse(Console.ReadLine());

            // prompt the user for the number of players (n)
            Console.Write("Please enter the number of people: ");
            n = Convert.ToInt32(Console.ReadLine());

            // ensure that the number of prizes is <= number of players
            if (p > n)
            {
                Console.WriteLine("p must be less than or equal to n.");
                return; // exit the program.
            }

            // record the starting time of the number generation
            startTime = DateTime.Now;

/* VERSION 1 - loop through, picking p numbers
 *             but notice we have to check for duplicates
 */
            // VERSION 1 - drawing at random and checking for duplicates
            // We need the arralist if we're to maintain a list of 
            // numbers already picked as winners.

            ArrayList picked = new ArrayList();

            for (int i = 0; i < p; i++)
            {
                int next_winner;
 
                do
                {
                    next_winner = r.Next(n) + 1;
                    count++;
                } while (picked.Contains(next_winner));
 
                Console.WriteLine(next_winner + " wins prize number " + i);
                picked.Add(next_winner);
            }
 
/* END OF VERSION 1 */

            // This is the second verson we wrote.
            // It generates n numbers, randomizes them, and picks
            // p of them.  This version is MUCH faster since we
            // don't have to worry about duplicates.

/* VERSION 2
 * 
 * Comment from here to the VERSION 2 marker below and uncomment above to
 * run version 1.
 *

            int[] picked = new int[n];

            // initialize the array such that the i-th spot in the array
            // contains the value i
            for (int i = 0; i < n; i++)
                picked[i] = i;

            int temp;
            int next_winner;

            // randomize/shuffle the numbers.
            for (int i = 0; i < n; i++)
            {
                temp = picked[i];
                next_winner = r.Next(n);
                count++;
                picked[i] = picked[next_winner];
                picked[next_winner] = temp;
            }


            //  display who won each of the p prizes.
            for (int i = 0; i < p; i++)
                Console.WriteLine(picked[i] + " wins prize " + i);

/* END OF VERSION 2 */

            // store the finishing time
            finishTime = DateTime.Now;

            // calculate the total computation time
            timeToComplete = finishTime.Subtract(startTime);

            // display how long it took
            Console.WriteLine("That took " + timeToComplete);

            // in both versions, the variable "count" maintains how many
            // numbers were drawn.  In version 1, this could be quite a few.
            // In version 2, it should be exactly p.
            Console.WriteLine(count + " numbers were drawn");
        }
    }
}