using System;
using System.IO;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace HashTables
{
    public class Hashtables
    {

        static int[] N = new int[] { 5000, 10000, 20000 };

        static void Main(String[] args)
        {
            Random rand = new Random();
            //StreamReader r = new StreamReader(Hashtables.in);
            for (int j = 0; (j < N.Length); j++)
            {
                int[] key = new int[(N[j] / 2)];
                data_s[] da = new data_s[N[j]];
                for (int i = 0; (i
                            < (N[j] / 2)); i++)
                {
                    int kbef = ((int)((rand.Next(1, 100) * 100000)));
                    int kaft = Hashtables.hash(kbef, N[j]);
                    key[i] = kbef;
                    while ((da[kaft] != null))
                    {
                        kaft++;
                        if ((kaft == N[j]))
                        {
                            kaft = 0;
                        }

                    }

                    da[kaft] = new data_s(kbef);
                }

                int[] rrr = new int[N[j]];
                int k = N[j];
                for (int i = 0; (i
                            < (N[j] / 2)); i++)
                {
                    int kaft = Hashtables.hash(key[i], N[j]);
                    while ((key[i] != da[kaft].L))
                    {
                        rrr[i]++;
                        k++;
                        kaft++;
                        if ((kaft == N[j]))
                        {
                            kaft = 0;
                        }

                    }

                }

                Console.WriteLine(("" + (N[j] + (")" + ((k * (1 / N[j])) + "")))));
            }

        }

        public static int hash(int key, int N)
        {
            return (key % N);
        }
    }
    class data_s
    {

        public int L;

        public data_s(int data)
        {
            this.L = data;
        }
    }
}