// Hash simplu
#include <cstdio>
#include <cstdlib>
#include <ctime>
#define maxh 2000003

struct nod { int v; nod *n;};

nod *H[maxh];

inline int hash(int v)
{
	return v%maxh;
}

inline int find(int v)
{
	int h=hash(v);
	for(nod *i=H[h]; i; i=i->n)
		if(i->v == v) return 1;
	return 0;
}

inline void insert(int v)
{
	//if(find(v)) return;
	int h=hash(v);
	nod *p=new nod;
	p->v=v;
	p->n=H[h];
	H[h]=p;
}

int a[1000001];
int maxlen=0;
double medie=0;
int poz;

void calc()
{
	maxlen=0;
	medie=0;
	int nn=0;
	for(int n=0; n<maxh;++n)
	{
		int len=0;
		for(nod *i=H[n]; i; i=i->n) ++len;
		if(len > maxlen) maxlen=len;
		if(len) ++nn, medie+=(double)len;
	}
	medie/=(double)nn;
}
	
int main()
{
	
	srand(time(0));
	int n=1000000,i;
	
	double s=clock();

	
	for(i=1;i<=n;++i) a[i]=rand();//*rand();
	
	for(i=1;i<=n;++i) insert(a[i]);
	
	for(i=1;i<=n;++i) find(a[i]);
	
	for(i=1;i<=n;++i) find(rand());//*rand());

	printf("%d %d\n", hash(maxh), hash(2*maxh));
	
	calc();

	printf("Time: %lf\n", (clock()-s)/(double)CLOCKS_PER_SEC);
	printf("Maxim: %d\n", maxlen);
	printf("Medie: %lf\n", medie);
	
	return 0;
}