/****** Problem 2--Cycles, Period. ************************************
 I thought this was the hardest problem of the bunch.  Others may
 disagree with me.  What made this problem hard was seeing all the
 checks that had to be made.  In particular, the sample data given in
 the problem description did not test all of these cases.
 First of all, there is no limit given on the number of observations,
 so this had to be handled dynamically; I used a linked list.
 Then, when all the data had been read in (and there is no guarantee
 that this data will be sorted in any particular order), possible
 cycle lengths are found by seeing which observations recorded the
 same value.  Since all values are unique within a period,
 the difference in observation times of the same value must be a
 multiple of the period.  Thus, to find the greatest possible period,
 you need to compute the greatest common factor of all of these
 potential periods.
 Finally, it is very possible that there is no period at all in the
 data.  Once you figure out what the period could be, you have to go
 through and make sure that all of the data does indeed abide by this
 period; if two observation times differ by a multiple of the cycle
 length, yet the values observed are different, there is no observable
 cycle, and this should be reported.  Additionally, if there is no
 repetition in the data, there is also no observable cycle.  The test
 data supplied gives an example of the latter problem, but not one
 of the former.
 **********************************************************************/

#include <fstream>
#include <cstdlib>
using namespace std;

class pairlist;

class pairlist {   // linked list for pairs
 public:
  int t, v;
  pairlist *next;
  pairlist (int t, int v);
  ~pairlist ();
};

int main (int argc, char **argv);
pairlist * readlist ();
int GCF (int a, int b);
int maxcyclelength (pairlist *p);
int verify (pairlist *p, int len);
int cycle (pairlist *p);
void freelist (pairlist *p);

ifstream in ("prob2.in");
ofstream out ("prob2.out");

/**** pairlist constructor ********************************************/
pairlist::pairlist (int t, int v) {

 this->t = t; this->v = v; next = NULL;
}

/**** pairlist destructor *********************************************/
pairlist::~pairlist () {

 if (next != NULL) delete next;
}

/****** main **********************************************************
 This program repeatedly reads in a list of observation times and values
 and determines if a cycle is present.  If there is one, it prints the
 length of the greatest possible cycle.  If not, it prints a message
 to that effect.  The program ends when an empty list is provided.
 **********************************************************************/

int main (int argc, char **argv) {

  int c;          // computed cycle length
  pairlist *p;    // the list of observations

 for (int cs=0;(p=readlist())!=NULL;) {
                         // read in a list
                         // done if an empty list is read
  out << "Case " << ++cs << ": ";
  if ((c = cycle (p))>0)   // print computed cycle time
   out << "cycle time = " << c << "." << endl;
  else
   out << "no cycle time can be determined." << endl;
  delete (p);    // free up our linked list
 }
 return EXIT_SUCCESS;
}

/***** readlist *******************************************************
 readlist reads in a linked list of ordered pairs.  The routine is
 standard.  Note that we are not guaranteed any specific order
 of the pairs in the listing, thus it won't make any difference that
 they appear in the linked list in the opposite order of entry.
 **********************************************************************/

pairlist * readlist () {

  pairlist *p,   // The list of pairs (to be returned)
           *q;   // temporary
  int t, v;        // The input values to be added to the list

 for (p=NULL;;) {
  in >> t >> v;
  if (t==0 && v==0) break;    // if both are 0, then the list is done
  q = new pairlist (t,v);
  q->next = p;
  p = q;
 }
 return p;
}

/****** GCF ***********************************************************
 GCF compute the greatest common factor of two integers.  The algorithm
 below is Euclid's algorithm, the easiest method of computing it.
 **********************************************************************/

int GCF (int a, int b) {

 return b==0 ? a : GCF (b, a%b);
}

/********* maxcyclelength *********************************************
 maxcyclelength accepts a list of pairs and returns the GCF of all
 potential cycles in the list.  If there is no repetition of data in
 the list, this function returns 0.
 This function simply uses nested loops to try every pair of values in
 the list to see if there is a potential cycle.
 **********************************************************************/

int maxcyclelength (pairlist *p) {

  int len=0;          // the cycle length (to be returned)

 for (pairlist *q=p;q!=NULL;q=q->next) // q loops from p to the end
  for (pairlist *r=q->next;r!=NULL;r=r->next)
                     // r loops from one past q to the end
   if (q->v == r->v)   // compute the GCF of this cycle with all
    len = GCF (len,abs(q->t-r->t)); // previously found cycles.
 return len;
}

/******* verify *******************************************************
 verify accepts a list of pairs and a potential cycle length and
 determines whether that cycle length could possibly work.  What it
 does is check whether there are any pairs that are a full number of
 cycles apart but still have a different value.
 verify returns true if the cycle length is valid, false otherwise.
 This function simply uses nested loops to check whether all pairs
 of observations are consistent with this cycle length.
 **********************************************************************/

int verify (pairlist *p, int len) {

  int b=1;            // boolean value (to be returned)

 for (pairlist *q=p;q!=NULL && b;q=q->next)
              // q goes from p to the end, but the loop will abort
              // early if b ever becomes 0
  for (pairlist *r=q->next;r!=NULL && b;r=r->next)
             // r goes from q to the end, but the loop will abort
             // early if b ever becomes 0
   b = abs(q->t-r->t)%len != 0 || q->v == r->v;
          // check for validity of the pairs at q and r
 return b;
}

/******* cycle ********************************************************
 cycle computes the maximum cycle length supported by input data in p.
 if no cycle is supported, this function returns 0.
 **********************************************************************/

int cycle (pairlist *p) {

 int c = maxcyclelength (p);     // the max cycle length
 if (c > 0 && !verify (p,c))     // if this length is not borne out
  return 0;                      // by the data, we must assume there
 return c;                       // is no cycle.
}