//******************************************************************************
//
// Program:     Homework 9 -- Perfect Hash Function
//
// Author:      Travis Dillon
// Email:       tdillon@ace.cs.ohiou.edu
//
// Description: This program find a  perfect hash function.
//
// Date:        November 17, 2003
//
//******************************************************************************


#include <iostream>
#include <iomanip>
#include <float.h>

using std::cin;
using std::cout;
using std::endl;

size_t hash(const size_t x, const double a, const size_t M);

int main()
{
   cout.precision(20);
   bool bad = false;
   bool array[50];
   size_t num[27];
   size_t i;

   for(size_t x(1); x < 26; ++x) cin >> num[x];
   for(size_t w(0); w < 30; ++w) array[w] = false;

   for(size_t M(29); M < 30; ++M)
   {
      for(double a(2000000000); a < DBL_MAX; ++a)
      {
      if(size_t(a) % 1000000 == 0) cout << a << endl;
         for(i = 1; i < 26; ++i)
         {
            if(!array[hash(num[i], a, M)])
            {
               array[hash(num[i], a, M)] = true;
            }
            else
            {
               bad = true;
               break;
            }
         }
         if(!bad)
         {
            cout << "a and M found: a = " << a << " M = " << M << endl;
            for(size_t q(1); q < 26; ++q)
            {
               if(num[q] < 10000) cout << " ";
               cout << num[q] << "  ";
               if(hash(num[q], a, M) < 10) cout << " ";
               cout << hash(num[q], a, M) << endl;
            }
            exit(EXIT_SUCCESS);
         }
         else
         {
            bad = false;
            for(size_t t(0); t < 30; ++t) array[t] = false;
         }
      }
   }
   return EXIT_FAILURE;
}


//******************************************************************************
//
// Function:   hash
//
// Purpose:    Return the has function h(x) = (a*x) % M
//
// Parameters: x - number from file to find hash number of
//             a - times by x
//             M - mod with a*x
//
// Calls:      none
//
// Time Comp:  O(1)
//
// Space Com:  O(1)
//
//*****************************************************************************


size_t hash(const size_t x, const double a, const size_t M)
{
   return((size_t(size_t(a) % M) * size_t(x % M)) % M);
}