289b0513ba 2014-02-03        kinaba: #include <iostream>
289b0513ba 2014-02-03        kinaba: #include <sstream>
289b0513ba 2014-02-03        kinaba: #include <iomanip>
289b0513ba 2014-02-03        kinaba: #include <vector>
289b0513ba 2014-02-03        kinaba: #include <string>
289b0513ba 2014-02-03        kinaba: #include <map>
289b0513ba 2014-02-03        kinaba: #include <set>
289b0513ba 2014-02-03        kinaba: #include <algorithm>
289b0513ba 2014-02-03        kinaba: #include <numeric>
289b0513ba 2014-02-03        kinaba: #include <iterator>
289b0513ba 2014-02-03        kinaba: #include <functional>
289b0513ba 2014-02-03        kinaba: #include <complex>
289b0513ba 2014-02-03        kinaba: #include <queue>
289b0513ba 2014-02-03        kinaba: #include <stack>
289b0513ba 2014-02-03        kinaba: #include <cmath>
289b0513ba 2014-02-03        kinaba: #include <cassert>
289b0513ba 2014-02-03        kinaba: #include <tuple>
289b0513ba 2014-02-03        kinaba: using namespace std;
289b0513ba 2014-02-03        kinaba: typedef long long LL;
289b0513ba 2014-02-03        kinaba: typedef complex<double> CMP;
289b0513ba 2014-02-03        kinaba: 
289b0513ba 2014-02-03        kinaba: class EllysPairing { public:
289b0513ba 2014-02-03        kinaba: 	int getMax(int M, vector <int> count, vector <int> first, vector <int> mult, vector <int> add)
289b0513ba 2014-02-03        kinaba: 	{
289b0513ba 2014-02-03        kinaba: 		int all = accumulate(count.begin(), count.end(), 0);
289b0513ba 2014-02-03        kinaba: 		int max_cnt = maxFreq(M, 0, M, count, first, mult, add);
289b0513ba 2014-02-03        kinaba: 
289b0513ba 2014-02-03        kinaba: 		if(max_cnt <= all/2)
289b0513ba 2014-02-03        kinaba: 			return all/2;
289b0513ba 2014-02-03        kinaba: 		else
289b0513ba 2014-02-03        kinaba: 			return all - max_cnt;
289b0513ba 2014-02-03        kinaba: 	}
289b0513ba 2014-02-03        kinaba: 
289b0513ba 2014-02-03        kinaba: 	int maxFreq(unsigned M, int L, int R,
289b0513ba 2014-02-03        kinaba: 		const vector<int>& count, const vector<int>& first, const vector<int>& mult, const vector<int>& add)
289b0513ba 2014-02-03        kinaba: 	{
289b0513ba 2014-02-03        kinaba: 		static const int Z = 1<<20;
289b0513ba 2014-02-03        kinaba: 		if(R-L <= Z) {
289b0513ba 2014-02-03        kinaba: 			int freq[Z] = {};
289b0513ba 2014-02-03        kinaba: 			for(int i=0; i<count.size(); ++i) {
289b0513ba 2014-02-03        kinaba: 				unsigned c = count[i];
289b0513ba 2014-02-03        kinaba: 				unsigned f = first[i];
289b0513ba 2014-02-03        kinaba: 				unsigned m = mult[i];
289b0513ba 2014-02-03        kinaba: 				unsigned a = add[i];
289b0513ba 2014-02-03        kinaba: 				for(unsigned k=0; k<c; ++k) {
289b0513ba 2014-02-03        kinaba: 					if(L<=f && f<R) freq[f-L]++;
289b0513ba 2014-02-03        kinaba: 					f=(f*m+a)&(M-1);
289b0513ba 2014-02-03        kinaba: 				}
289b0513ba 2014-02-03        kinaba: 			}
289b0513ba 2014-02-03        kinaba: 			return *max_element(freq, freq+(R-L));
289b0513ba 2014-02-03        kinaba: 		}
289b0513ba 2014-02-03        kinaba: 
289b0513ba 2014-02-03        kinaba: 		int freq[2] = {}, C = L+(R-L)/2;
289b0513ba 2014-02-03        kinaba: 		for(int i=0; i<count.size(); ++i) {
289b0513ba 2014-02-03        kinaba: 			unsigned c = count[i];
289b0513ba 2014-02-03        kinaba: 			unsigned f = first[i];
289b0513ba 2014-02-03        kinaba: 			unsigned m = mult[i];
289b0513ba 2014-02-03        kinaba: 			unsigned a = add[i];
289b0513ba 2014-02-03        kinaba: 			for(unsigned k=0; k<c; ++k) {
289b0513ba 2014-02-03        kinaba: 				if(L<=f && f<R)
289b0513ba 2014-02-03        kinaba: 					freq[f<C ? 0 : 1]++;
289b0513ba 2014-02-03        kinaba: 				f=(f*m+a)&(M-1);
289b0513ba 2014-02-03        kinaba: 			}
289b0513ba 2014-02-03        kinaba: 		}
289b0513ba 2014-02-03        kinaba: 		if(freq[0] < freq[1])
289b0513ba 2014-02-03        kinaba: 			return maxFreq(M, C, R, count, first, mult, add);
289b0513ba 2014-02-03        kinaba: 		else
289b0513ba 2014-02-03        kinaba: 			return maxFreq(M, L, C, count, first, mult, add);
289b0513ba 2014-02-03        kinaba: 	}
289b0513ba 2014-02-03        kinaba: };
289b0513ba 2014-02-03        kinaba: 
289b0513ba 2014-02-03        kinaba: // BEGIN CUT HERE
289b0513ba 2014-02-03        kinaba: #include <ctime>
289b0513ba 2014-02-03        kinaba: double start_time; string timer()
289b0513ba 2014-02-03        kinaba:  { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
289b0513ba 2014-02-03        kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
289b0513ba 2014-02-03        kinaba:  { os << "{ ";
289b0513ba 2014-02-03        kinaba:    for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
289b0513ba 2014-02-03        kinaba:    os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
289b0513ba 2014-02-03        kinaba: void verify_case(const int& Expected, const int& Received) {
289b0513ba 2014-02-03        kinaba:  bool ok = (Expected == Received);
289b0513ba 2014-02-03        kinaba:  if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
289b0513ba 2014-02-03        kinaba:  cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
289b0513ba 2014-02-03        kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
289b0513ba 2014-02-03        kinaba: #define END	 verify_case(_, EllysPairing().getMax(M, count, first, mult, add));}
289b0513ba 2014-02-03        kinaba: int main(){
289b0513ba 2014-02-03        kinaba: 
289b0513ba 2014-02-03        kinaba: CASE(0)
289b0513ba 2014-02-03        kinaba: 	int M = 16;
289b0513ba 2014-02-03        kinaba: 	int count_[] = {4, 7};
289b0513ba 2014-02-03        kinaba: 	  vector <int> count(count_, count_+sizeof(count_)/sizeof(*count_));
289b0513ba 2014-02-03        kinaba: 	int first_[] = {5, 3};
289b0513ba 2014-02-03        kinaba: 	  vector <int> first(first_, first_+sizeof(first_)/sizeof(*first_));
289b0513ba 2014-02-03        kinaba: 	int mult_[] = {2, 3};
289b0513ba 2014-02-03        kinaba: 	  vector <int> mult(mult_, mult_+sizeof(mult_)/sizeof(*mult_));
289b0513ba 2014-02-03        kinaba: 	int add_[] = {1, 0};
289b0513ba 2014-02-03        kinaba: 	  vector <int> add(add_, add_+sizeof(add_)/sizeof(*add_));
289b0513ba 2014-02-03        kinaba: 	int _ = 5;
289b0513ba 2014-02-03        kinaba: END
289b0513ba 2014-02-03        kinaba: CASE(1)
289b0513ba 2014-02-03        kinaba: 	int M = 8;
289b0513ba 2014-02-03        kinaba: 	int count_[] = {6, 4, 3};
289b0513ba 2014-02-03        kinaba: 	  vector <int> count(count_, count_+sizeof(count_)/sizeof(*count_));
289b0513ba 2014-02-03        kinaba: 	int first_[] = {0, 3, 2};
289b0513ba 2014-02-03        kinaba: 	  vector <int> first(first_, first_+sizeof(first_)/sizeof(*first_));
289b0513ba 2014-02-03        kinaba: 	int mult_[] = {3, 7, 5};
289b0513ba 2014-02-03        kinaba: 	  vector <int> mult(mult_, mult_+sizeof(mult_)/sizeof(*mult_));
289b0513ba 2014-02-03        kinaba: 	int add_[] = {0, 3, 2};
289b0513ba 2014-02-03        kinaba: 	  vector <int> add(add_, add_+sizeof(add_)/sizeof(*add_));
289b0513ba 2014-02-03        kinaba: 	int _ = 5;
289b0513ba 2014-02-03        kinaba: END
289b0513ba 2014-02-03        kinaba: CASE(2)
289b0513ba 2014-02-03        kinaba: 	int M = 128;
289b0513ba 2014-02-03        kinaba: 	int count_[] = {42, 13, 666, 17, 1337, 42, 1};
289b0513ba 2014-02-03        kinaba: 	  vector <int> count(count_, count_+sizeof(count_)/sizeof(*count_));
289b0513ba 2014-02-03        kinaba: 	int first_[] = {18, 76, 3, 122, 0, 11, 11};
289b0513ba 2014-02-03        kinaba: 	  vector <int> first(first_, first_+sizeof(first_)/sizeof(*first_));
289b0513ba 2014-02-03        kinaba: 	int mult_[] = {33, 17, 54, 90, 41, 122, 20};
289b0513ba 2014-02-03        kinaba: 	  vector <int> mult(mult_, mult_+sizeof(mult_)/sizeof(*mult_));
289b0513ba 2014-02-03        kinaba: 	int add_[] = {66, 15, 10, 121, 122, 1, 30};
289b0513ba 2014-02-03        kinaba: 	  vector <int> add(add_, add_+sizeof(add_)/sizeof(*add_));
289b0513ba 2014-02-03        kinaba: 	int _ = 1059;
289b0513ba 2014-02-03        kinaba: END
289b0513ba 2014-02-03        kinaba: CASE(3)
289b0513ba 2014-02-03        kinaba: 	int M = 1048576;
289b0513ba 2014-02-03        kinaba: 	int count_[] = {4242, 42, 9872, 13, 666, 21983, 17, 1337, 42, 1};
289b0513ba 2014-02-03        kinaba: 	  vector <int> count(count_, count_+sizeof(count_)/sizeof(*count_));
289b0513ba 2014-02-03        kinaba: 	int first_[] = {19, 18, 76, 42, 3, 112, 0, 11, 11, 12};
289b0513ba 2014-02-03        kinaba: 	  vector <int> first(first_, first_+sizeof(first_)/sizeof(*first_));
289b0513ba 2014-02-03        kinaba: 	int mult_[] = {27, 33, 10, 8, 17, 9362, 90, 41, 122, 20};
289b0513ba 2014-02-03        kinaba: 	  vector <int> mult(mult_, mult_+sizeof(mult_)/sizeof(*mult_));
289b0513ba 2014-02-03        kinaba: 	int add_[] = {98, 101, 66, 15, 10, 144, 3, 1, 5, 1};
289b0513ba 2014-02-03        kinaba: 	  vector <int> add(add_, add_+sizeof(add_)/sizeof(*add_));
289b0513ba 2014-02-03        kinaba: 	int _ = 16232;
289b0513ba 2014-02-03        kinaba: END
289b0513ba 2014-02-03        kinaba: CASE(4)
289b0513ba 2014-02-03        kinaba: 	int M = 1073741824;
289b0513ba 2014-02-03        kinaba: 	int count_[] = {894602, 946569, 887230, 856152, 962583, 949356, 904847, 829100, 842183, 958440,
289b0513ba 2014-02-03        kinaba:  811081, 864078, 809209, 938727, 949135, 892809, 816528, 961237, 979142, 890922};
289b0513ba 2014-02-03        kinaba: 	  vector <int> count(count_, count_+sizeof(count_)/sizeof(*count_));
289b0513ba 2014-02-03        kinaba: 	int first_[] = {844085078, 898937259, 243490172, 887804102, 187696417, 156820442, 237600210, 618812924, 153000239, 912364033,
289b0513ba 2014-02-03        kinaba:  254936966, 650298774, 982988140, 649258331, 566444626, 201481721, 492943390, 1061953081, 492672963, 960519711};
289b0513ba 2014-02-03        kinaba: 	  vector <int> first(first_, first_+sizeof(first_)/sizeof(*first_));
289b0513ba 2014-02-03        kinaba: 	int mult_[] = {1036482037, 583219072, 819168094, 253755052, 548208982, 401830167, 638626082, 43642932, 123607749, 485521178,
289b0513ba 2014-02-03        kinaba:  860368129, 30334704, 219771462, 733375600, 130839219, 415503960, 294132484, 1044831462, 256910484, 198852170};
289b0513ba 2014-02-03        kinaba: 	  vector <int> mult(mult_, mult_+sizeof(mult_)/sizeof(*mult_));
289b0513ba 2014-02-03        kinaba: 	int add_[] = {889169006, 604831366, 967292994, 980686280, 844875791, 1027687492, 357734882, 295879743, 48284748, 421729100,
289b0513ba 2014-02-03        kinaba:  1049536313, 327207332, 948053446, 271229570, 664579359, 795815285, 842856528, 876662975, 675611938, 634229925};
289b0513ba 2014-02-03        kinaba: 	  vector <int> add(add_, add_+sizeof(add_)/sizeof(*add_));
289b0513ba 2014-02-03        kinaba: 	int _ = 8971965;
289b0513ba 2014-02-03        kinaba: END
289b0513ba 2014-02-03        kinaba: CASE(5)
289b0513ba 2014-02-03        kinaba: 	int M = 1073741824;
289b0513ba 2014-02-03        kinaba: 	int count_[] = {227399,73015,235546,945352,318629,384458,55809,766035,530600,755410,601579,841014,823193,223692,508381,636658,788171,265961,119515,822571,869554,564235,312051,105107,625704,480200,761095,588825,745857,74091,897771,900844,174101,352520,437181,680487,550423,923744,591847,998330,494389,171179,983838,494437,3604,940306,963263,854327,337255,802996};
289b0513ba 2014-02-03        kinaba: 	  vector <int> count(count_, count_+sizeof(count_)/sizeof(*count_));
289b0513ba 2014-02-03        kinaba: 	int first_[] = {227399,73015,235546,945352,318629,384458,55809,766035,530600,755410,601579,841014,823193,223692,508381,636658,788171,265961,119515,822571,869554,564235,312051,105107,625704,480200,761095,588825,745857,74091,897771,900844,174101,352520,437181,680487,550423,923744,591847,998330,494389,171179,983838,494437,3604,940306,963263,854327,337255,802996};
289b0513ba 2014-02-03        kinaba: 	  vector <int> first(first_, first_+sizeof(first_)/sizeof(*first_));
289b0513ba 2014-02-03        kinaba: 	int mult_[] = {227399,73015,235546,945352,318629,384458,55809,766035,530600,755410,601579,841014,823193,223692,508381,636658,788171,265961,119515,822571,869554,564235,312051,105107,625704,480200,761095,588825,745857,74091,897771,900844,174101,352520,437181,680487,550423,923744,591847,998330,494389,171179,983838,494437,3604,940306,963263,854327,337255,802996};
289b0513ba 2014-02-03        kinaba: 	  vector <int> mult(mult_, mult_+sizeof(mult_)/sizeof(*mult_));
289b0513ba 2014-02-03        kinaba: 	int add_[] = {227399,73015,235546,945352,318629,384458,55809,766035,530600,755410,601579,841014,823193,223692,508381,636658,788171,265961,119515,822571,869554,564235,312051,105107,625704,480200,761095,588825,745857,74091,897771,900844,174101,352520,437181,680487,550423,923744,591847,998330,494389,171179,983838,494437,3604,940306,963263,854327,337255,802996};
289b0513ba 2014-02-03        kinaba: 	  vector <int> add(add_, add_+sizeof(add_)/sizeof(*add_));
289b0513ba 2014-02-03        kinaba: 	int _ = -1;
289b0513ba 2014-02-03        kinaba: END
289b0513ba 2014-02-03        kinaba: CASE(5)
289b0513ba 2014-02-03        kinaba: 	int M = 1073741824;
289b0513ba 2014-02-03        kinaba: 	int count_[] = {1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000};
289b0513ba 2014-02-03        kinaba: 	  vector <int> count(count_, count_+sizeof(count_)/sizeof(*count_));
289b0513ba 2014-02-03        kinaba: 	int first_[] = {775899,967700,946244,694562,767949,840507,668387,555565,884003,535966,934297,533923,585935,705980,506559,312277,271385,969286,803240,836682,693444,383269,412055,466183,462416,608005,144157,218468,961299,684785,324885,629586,362746,376166,666757,591939,599620,827159,650578,164404,229593,229537,132416,418569,454026,241609,23476,898462,433801,933810};
289b0513ba 2014-02-03        kinaba: 	  vector <int> first(first_, first_+sizeof(first_)/sizeof(*first_));
289b0513ba 2014-02-03        kinaba: 	int mult_[] = {227399,73015,235546,945352,318629,384458,55809,766035,530600,755410,601579,841014,823193,223692,508381,636658,788171,265961,119515,822571,869554,564235,312051,105107,625704,480200,761095,588825,745857,74091,897771,900844,174101,352520,437181,680487,550423,923744,591847,998330,494389,171179,983838,494437,3604,940306,963263,854327,337255,802996};
289b0513ba 2014-02-03        kinaba: 	  vector <int> mult(mult_, mult_+sizeof(mult_)/sizeof(*mult_));
289b0513ba 2014-02-03        kinaba: 	int add_[] = {227399,73015,235546,945352,318629,384458,55809,766035,530600,755410,601579,841014,823193,223692,508381,636658,788171,265961,119515,822571,869554,564235,312051,105107,625704,480200,761095,588825,745857,74091,897771,900844,174101,352520,437181,680487,550423,923744,591847,998330,494389,171179,983838,494437,3604,940306,963263,854327,337255,802996};
289b0513ba 2014-02-03        kinaba: 	  vector <int> add(add_, add_+sizeof(add_)/sizeof(*add_));
289b0513ba 2014-02-03        kinaba: 	int _ = -1;
289b0513ba 2014-02-03        kinaba: END
289b0513ba 2014-02-03        kinaba: /*
289b0513ba 2014-02-03        kinaba: CASE(6)
289b0513ba 2014-02-03        kinaba: 	int M = ;
289b0513ba 2014-02-03        kinaba: 	int count_[] = ;
289b0513ba 2014-02-03        kinaba: 	  vector <int> count(count_, count_+sizeof(count_)/sizeof(*count_));
289b0513ba 2014-02-03        kinaba: 	int first_[] = ;
289b0513ba 2014-02-03        kinaba: 	  vector <int> first(first_, first_+sizeof(first_)/sizeof(*first_));
289b0513ba 2014-02-03        kinaba: 	int mult_[] = ;
289b0513ba 2014-02-03        kinaba: 	  vector <int> mult(mult_, mult_+sizeof(mult_)/sizeof(*mult_));
289b0513ba 2014-02-03        kinaba: 	int add_[] = ;
289b0513ba 2014-02-03        kinaba: 	  vector <int> add(add_, add_+sizeof(add_)/sizeof(*add_));
289b0513ba 2014-02-03        kinaba: 	int _ = ;
289b0513ba 2014-02-03        kinaba: END
289b0513ba 2014-02-03        kinaba: */
289b0513ba 2014-02-03        kinaba: }
289b0513ba 2014-02-03        kinaba: // END CUT HERE