#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int binSearch(char **a,int n,char *key,int *probeCount)
{
  int low,high,mid,comp;
  (*probeCount)=0;
  low=0;
  high=n-1;
  while (low<=high)
  {
    (*probeCount)++;
    mid=(low+high)/2;
    comp=strcmp(a[mid],key);
    if (comp==0) // (a[mid]==key)
      return mid;
    if (comp<0)  // (a[mid]<key)
      low=mid+1;
    else
      high=mid-1;
  }

  return (-1);
}

main()
{
char **tab;
int n;
int i,count,slot;

tab=(char **) malloc(1000*sizeof(char*));
for (i=0;i<1000;i++)
  tab[i]=(char *) malloc(51*sizeof(char));

n=0;
while (fgets(tab[n],51,stdin)!=NULL)
{
  tab[n][strlen(tab[n])-1]='\0';
  n++;
}

printf("n=%d\n",n);

for (i=0;i<n;i++)
{
  slot=binSearch(tab,n,tab[i],&count);
  printf("%d key=\"%s\" returned %d with %d probes\n",
    i,tab[i],slot,count);
}
}