/* Problem 6--Stamps
   This was accomplished by finding an upper bound for the maximum
   uncoverable postage and working down */

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

FILE *in, *out;

int main (int argc, char **argv);
void Process (int a, int b, int c);
int GCF (int a, int b);
int CanItBeDone (int a, int b, int c, int s);
int UpperBound (int a,int b,int c);
void Sort (int *a, int *b, int *c);

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

  int a, b, c;

 in = fopen ("prob6.in","r");
 out = fopen ("prob6.out","w");
 while (fscanf (in,"%d",&a),a > 0) { /* Read data until done */
  fscanf (in,"%d %d",&b,&c);
  Process (a,b,c);
 }
 fclose (in);
 fclose (out);
 return EXIT_SUCCESS;
}

/* Process each test case */
void Process (int a, int b, int c) {

  int x;

 if (a==1 || b==1 || c==1) { /* if there is a 1-cent stamp, we're done*/
  fprintf (out,"All postage can be covered.\n");
  return;
 }
 if (GCF (GCF (a,b),c) > 1) { /* If they all share a factor, done */
  fprintf (out,"There are an infinite number of postages that cannot "
               "be covered.\n");
  return;
 } /* Compute an upper bound and count down */
 for (x = UpperBound (a,b,c); x > 0; x--)
  if (!CanItBeDone (a,b,c,x)) { /* Do this until it cannot be done */
   fprintf (out,"The largest postage that cannot be covered is %d.\n",
                x);
   return;
  }
 }

/* Euclid's algorithm for Greatest Common Factor */
int GCF (int a, int b) {

 int r = a%b;
 if (r==0) return b;
 return GCF (b,r);
}

/* Checks whether a specific value s can be covered by a, b, and c. */
int CanItBeDone (int a, int b, int c, int s) {

  int x, y;

 for (x = 0; x <= s; x+=a) /* Add a stamps */
  for (y = 0; x+y <= s; y+=b) /* Add b stamps */
   if ((s-x-y)%c==0) return 1; /* See if what's left over is divisible*/
 return 0;                     /* by c */
}

/* Computes an upper bound for possible impossible postage */
int UpperBound (int a,int b,int c) {

  int t;

 Sort (&a,&b,&c);
 if (GCF (a,b)==1) return a*b-a-b; /* Max impossible for lowest 2 */
 if (GCF (a,c)==1) return a*c-a-c; /*Max impossible for first and last*/
 if (GCF (b,c)==1) return b*c-b-c; /* Max impossible for highest 2*/
 t = GCF (a,b); /* Compute max impossible when no 2 are rel. prime */
 return t*((a/t)*(b/t)-(a/t)-(b/t))+c*(t-1);
}

/* Sort the three integers. */
void Sort (int *a, int *b, int *c) {

  int t;

 if (*a > *b) {
  t = *a;
  *a = *b;
  *b = t;
 }
 if (*a > *c) {
  t = *a;
  *a = *c;
  *c = t;
 }
 if (*b > *c) {
  t = *b;
  *b = *c;
  *c = t;
 }
}