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

extern void registerme ( );
extern void startgame ( int );
extern int guess ( int );
extern void verifysoln ( int );

/* Linear search */
int playgame1 ()
{
   int a;

   startgame(1);
   for (a=1; a<=100000000; ++a) {
      if (guess(a) == 1) return a;
   }
   return 0;
}

/* Random search */
int playgame2 ()
{
   int a;

   startgame(2);
   while (1) {
      a = 1 + rand() % 100000000;
      if (guess(a) == 1) return a;
   }
}

/* ~ 2 lg N search */
int playgame3 ()
{
   int L, R, M;
   int d1, d2;

   startgame(3);
   L = 1; R = 100000000;
   while (L < R) {
      d1 = guess(L); if (d1 == 1) return L;
      d2 = guess(R); if (d2 == 1) return R;
      M = (L + R + 1) / 2;
      if (d2 == 2) L = M; else R = M-1;
   }
   return L;
}

/* ~ lg N search */
int playgame4 ()
{
   int L, R;  /* The current search interval [L,R] contains a4 */
   int P;     /* The previous guess */
   int G;     /* The current guess */
   int d;

   startgame(4);

   /* Initially L = 1, R = 100000000. Make the first guess at L */
   P = L = 1; d = guess(L); if (d == 1) return L;
   R = 100000000;

   /* Repeat until the search interval reduces to only one element */
   while (L < R) {
      /* All guesses lie outside the open interval (L,R). It is allowed
         to have a guess < L or > R. The black box still provides hints.
         In order to make a new guess G, look at the previous guess P.
         Place G equidistant from (the center of) [L,R] on the opposite
         side of P. That is, if the previous query was L - D for some
         D >= 0, then the current query should be R + D, and conversely.
         Since L and R change from iteration to iteration, the distance
         D is to be calculated dynamically. */
      if (P <= L) {
         G = R + (L - P);
         d = guess(G); if (d == 1) return G;
         if (d == 2) L = (L + R + 1) / 2; else R = (L + R - 1) / 2;
      } else if (P >= R) {
         G = L - (P - R);
         d = guess(G); if (d == 1) return G;
         if (d == 2) R = (L + R) / 2; else L = (L + R) / 2 + 1;
      } else {
         printf("*** This case should not have occurred\n");
         return 0;
      }
      P = G; /* The current guess is the previous guess in the next iteration */
   }
   return L;
}

int main ()
{
   int a1, a2, a3, a4;
   clock_t c1, c2;

   registerme();

   c1 = clock(); a1 = playgame1(); c2 = clock();
   printf("\n+++ Game 1\n    a1 = %d\n", a1);
   printf("    Time taken = %lf sec\n", (double)(c2-c1)/(double)CLOCKS_PER_SEC);
   verifysoln(a1);

   c1 = clock(); a2 = playgame2(); c2 = clock();
   printf("\n+++ Game 2\n    a2 = %d\n", a2);
   printf("    Time taken = %lf sec\n", (double)(c2-c1)/(double)CLOCKS_PER_SEC);
   verifysoln(a2);

   c1 = clock(); a3 = playgame3(); c2 = clock();
   printf("\n+++ Game 3\n    a3 = %d\n", a3);
   printf("    Time taken = %lf sec\n", (double)(c2-c1)/(double)CLOCKS_PER_SEC);
   verifysoln(a3);

   c1 = clock(); a4 = playgame4(); c2 = clock();
   printf("\n+++ Game 4\n    a4 = %d\n", a4);
   printf("    Time taken = %lf sec\n", (double)(c2-c1)/(double)CLOCKS_PER_SEC);
   verifysoln(a4);
}