Overview
| SHA1 Hash: | 289b0513bab4fff34914cd78364e88267e1623d6 |
|---|---|
| Date: | 2014-02-03 11:41:42 |
| User: | kinaba |
| Comment: | 606 |
| Timelines: | family | ancestors | descendants | both | trunk |
| Downloads: | Tarball | ZIP archive |
| Other Links: | files | file ages | manifest |
Tags And Properties
- branch=trunk inherited from [9165bd3629]
- sym-trunk inherited from [9165bd3629]
Changes
Added SRM/606-U/1A.cpp version [a5b9eb6ef2e80ed6]
1 +#include <iostream> 2 +#include <sstream> 3 +#include <iomanip> 4 +#include <vector> 5 +#include <string> 6 +#include <map> 7 +#include <set> 8 +#include <algorithm> 9 +#include <numeric> 10 +#include <iterator> 11 +#include <functional> 12 +#include <complex> 13 +#include <queue> 14 +#include <stack> 15 +#include <cmath> 16 +#include <cassert> 17 +#include <tuple> 18 +using namespace std; 19 +typedef long long LL; 20 +typedef complex<double> CMP; 21 + 22 +class EllysNumberGuessing { public: 23 + int getNumber(vector <int> guesses, vector <int> answers) 24 + { 25 + set<int> cand; 26 + for(int i=0; i<guesses.size(); ++ i) { 27 + set<int> c; 28 + int a = guesses[i]+answers[i]; 29 + if(1<=a && a<=1000000000) c.insert(a); 30 + a = guesses[i]-answers[i]; 31 + if(1<=a && a<=1000000000) c.insert(a); 32 + 33 + if(i==0) 34 + cand = c; 35 + else { 36 + set<int> cc; 37 + set_intersection(cand.begin(), cand.end(), c.begin(), c.end(), inserter(cc, cc.begin())); 38 + cand = cc; 39 + } 40 + } 41 + return cand.size()==1 ? *cand.begin() : cand.size()==2 ? -1 : -2; 42 + } 43 +}; 44 + 45 +// BEGIN CUT HERE 46 +#include <ctime> 47 +double start_time; string timer() 48 + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 49 +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 50 + { os << "{ "; 51 + for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 52 + os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 53 +void verify_case(const int& Expected, const int& Received) { 54 + bool ok = (Expected == Received); 55 + if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 56 + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 57 +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 58 +#define END verify_case(_, EllysNumberGuessing().getNumber(guesses, answers));} 59 +int main(){ 60 + 61 +CASE(0) 62 + int guesses_[] = {600, 594}; 63 + vector <int> guesses(guesses_, guesses_+sizeof(guesses_)/sizeof(*guesses_)); 64 + int answers_[] = {6, 12}; 65 + vector <int> answers(answers_, answers_+sizeof(answers_)/sizeof(*answers_)); 66 + int _ = 606; 67 +END 68 +CASE(1) 69 + int guesses_[] = {100, 50, 34, 40}; 70 + vector <int> guesses(guesses_, guesses_+sizeof(guesses_)/sizeof(*guesses_)); 71 + int answers_[] = {58, 8, 8, 2}; 72 + vector <int> answers(answers_, answers_+sizeof(answers_)/sizeof(*answers_)); 73 + int _ = 42; 74 +END 75 +CASE(2) 76 + int guesses_[] = {500000, 600000, 700000}; 77 + vector <int> guesses(guesses_, guesses_+sizeof(guesses_)/sizeof(*guesses_)); 78 + int answers_[] = {120013, 220013, 79987}; 79 + vector <int> answers(answers_, answers_+sizeof(answers_)/sizeof(*answers_)); 80 + int _ = -2; 81 +END 82 +CASE(3) 83 + int guesses_[] = {500000000}; 84 + vector <int> guesses(guesses_, guesses_+sizeof(guesses_)/sizeof(*guesses_)); 85 + int answers_[] = {133742666}; 86 + vector <int> answers(answers_, answers_+sizeof(answers_)/sizeof(*answers_)); 87 + int _ = -1; 88 +END 89 +CASE(4) 90 + int guesses_[] = {76938260, 523164588, 14196746, 296286419, 535893832, 91 + 41243148, 364561227, 270003278, 472017422, 367932361, 92 + 395758413, 301278456, 186276934, 316343129, 336557549, 93 + 52536121, 98343562, 356769915, 89249181, 335191879}; 94 + vector <int> guesses(guesses_, guesses_+sizeof(guesses_)/sizeof(*guesses_)); 95 + int answers_[] = {466274085, 20047757, 529015599, 246925926, 7318513, 96 + 501969197, 178651118, 273209067, 71194923, 175279984, 97 + 147453932, 241933889, 356935411, 226869216, 206654796, 98 + 490676224, 444868783, 186442430, 453963164, 208020466}; 99 + vector <int> answers(answers_, answers_+sizeof(answers_)/sizeof(*answers_)); 100 + int _ = 543212345; 101 +END 102 +CASE(5) 103 + int guesses_[] = {42}; 104 + vector <int> guesses(guesses_, guesses_+sizeof(guesses_)/sizeof(*guesses_)); 105 + int answers_[] = {42}; 106 + vector <int> answers(answers_, answers_+sizeof(answers_)/sizeof(*answers_)); 107 + int _ = 84; 108 +END 109 +CASE(6) 110 + int guesses_[] = {999900000}; 111 + vector <int> guesses(guesses_, guesses_+sizeof(guesses_)/sizeof(*guesses_)); 112 + int answers_[] = {100001}; 113 + vector <int> answers(answers_, answers_+sizeof(answers_)/sizeof(*answers_)); 114 + int _ = 999799999; 115 +END 116 +/* 117 +CASE(7) 118 + int guesses_[] = ; 119 + vector <int> guesses(guesses_, guesses_+sizeof(guesses_)/sizeof(*guesses_)); 120 + int answers_[] = ; 121 + vector <int> answers(answers_, answers_+sizeof(answers_)/sizeof(*answers_)); 122 + int _ = ; 123 +END 124 +CASE(8) 125 + int guesses_[] = ; 126 + vector <int> guesses(guesses_, guesses_+sizeof(guesses_)/sizeof(*guesses_)); 127 + int answers_[] = ; 128 + vector <int> answers(answers_, answers_+sizeof(answers_)/sizeof(*answers_)); 129 + int _ = ; 130 +END 131 +*/ 132 +} 133 +// END CUT HERE
Added SRM/606-U/1B-U.cpp version [ce4d2a0b1b08e640]
1 +#include <iostream> 2 +#include <sstream> 3 +#include <iomanip> 4 +#include <vector> 5 +#include <string> 6 +#include <map> 7 +#include <set> 8 +#include <algorithm> 9 +#include <numeric> 10 +#include <iterator> 11 +#include <functional> 12 +#include <complex> 13 +#include <queue> 14 +#include <stack> 15 +#include <cmath> 16 +#include <cassert> 17 +#include <tuple> 18 +using namespace std; 19 +typedef long long LL; 20 +typedef complex<double> CMP; 21 + 22 +class EllysPairing { public: 23 + int getMax(int M, vector <int> count, vector <int> first, vector <int> mult, vector <int> add) 24 + { 25 + int all = accumulate(count.begin(), count.end(), 0); 26 + int max_cnt = maxFreq(M, 0, M, count, first, mult, add); 27 + 28 + if(max_cnt <= all/2) 29 + return all/2; 30 + else 31 + return all - max_cnt; 32 + } 33 + 34 + int maxFreq(unsigned M, int L, int R, 35 + const vector<int>& count, const vector<int>& first, const vector<int>& mult, const vector<int>& add) 36 + { 37 + static const int Z = 1<<20; 38 + if(R-L <= Z) { 39 + int freq[Z] = {}; 40 + for(int i=0; i<count.size(); ++i) { 41 + unsigned c = count[i]; 42 + unsigned f = first[i]; 43 + unsigned m = mult[i]; 44 + unsigned a = add[i]; 45 + for(unsigned k=0; k<c; ++k) { 46 + if(L<=f && f<R) freq[f-L]++; 47 + f=(f*m+a)&(M-1); 48 + } 49 + } 50 + return *max_element(freq, freq+(R-L)); 51 + } 52 + 53 + int freq[2] = {}, C = L+(R-L)/2; 54 + for(int i=0; i<count.size(); ++i) { 55 + unsigned c = count[i]; 56 + unsigned f = first[i]; 57 + unsigned m = mult[i]; 58 + unsigned a = add[i]; 59 + for(unsigned k=0; k<c; ++k) { 60 + if(L<=f && f<R) 61 + freq[f<C ? 0 : 1]++; 62 + f=(f*m+a)&(M-1); 63 + } 64 + } 65 + if(freq[0] < freq[1]) 66 + return maxFreq(M, C, R, count, first, mult, add); 67 + else 68 + return maxFreq(M, L, C, count, first, mult, add); 69 + } 70 +}; 71 + 72 +// BEGIN CUT HERE 73 +#include <ctime> 74 +double start_time; string timer() 75 + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 76 +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 77 + { os << "{ "; 78 + for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 79 + os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 80 +void verify_case(const int& Expected, const int& Received) { 81 + bool ok = (Expected == Received); 82 + if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 83 + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 84 +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 85 +#define END verify_case(_, EllysPairing().getMax(M, count, first, mult, add));} 86 +int main(){ 87 + 88 +CASE(0) 89 + int M = 16; 90 + int count_[] = {4, 7}; 91 + vector <int> count(count_, count_+sizeof(count_)/sizeof(*count_)); 92 + int first_[] = {5, 3}; 93 + vector <int> first(first_, first_+sizeof(first_)/sizeof(*first_)); 94 + int mult_[] = {2, 3}; 95 + vector <int> mult(mult_, mult_+sizeof(mult_)/sizeof(*mult_)); 96 + int add_[] = {1, 0}; 97 + vector <int> add(add_, add_+sizeof(add_)/sizeof(*add_)); 98 + int _ = 5; 99 +END 100 +CASE(1) 101 + int M = 8; 102 + int count_[] = {6, 4, 3}; 103 + vector <int> count(count_, count_+sizeof(count_)/sizeof(*count_)); 104 + int first_[] = {0, 3, 2}; 105 + vector <int> first(first_, first_+sizeof(first_)/sizeof(*first_)); 106 + int mult_[] = {3, 7, 5}; 107 + vector <int> mult(mult_, mult_+sizeof(mult_)/sizeof(*mult_)); 108 + int add_[] = {0, 3, 2}; 109 + vector <int> add(add_, add_+sizeof(add_)/sizeof(*add_)); 110 + int _ = 5; 111 +END 112 +CASE(2) 113 + int M = 128; 114 + int count_[] = {42, 13, 666, 17, 1337, 42, 1}; 115 + vector <int> count(count_, count_+sizeof(count_)/sizeof(*count_)); 116 + int first_[] = {18, 76, 3, 122, 0, 11, 11}; 117 + vector <int> first(first_, first_+sizeof(first_)/sizeof(*first_)); 118 + int mult_[] = {33, 17, 54, 90, 41, 122, 20}; 119 + vector <int> mult(mult_, mult_+sizeof(mult_)/sizeof(*mult_)); 120 + int add_[] = {66, 15, 10, 121, 122, 1, 30}; 121 + vector <int> add(add_, add_+sizeof(add_)/sizeof(*add_)); 122 + int _ = 1059; 123 +END 124 +CASE(3) 125 + int M = 1048576; 126 + int count_[] = {4242, 42, 9872, 13, 666, 21983, 17, 1337, 42, 1}; 127 + vector <int> count(count_, count_+sizeof(count_)/sizeof(*count_)); 128 + int first_[] = {19, 18, 76, 42, 3, 112, 0, 11, 11, 12}; 129 + vector <int> first(first_, first_+sizeof(first_)/sizeof(*first_)); 130 + int mult_[] = {27, 33, 10, 8, 17, 9362, 90, 41, 122, 20}; 131 + vector <int> mult(mult_, mult_+sizeof(mult_)/sizeof(*mult_)); 132 + int add_[] = {98, 101, 66, 15, 10, 144, 3, 1, 5, 1}; 133 + vector <int> add(add_, add_+sizeof(add_)/sizeof(*add_)); 134 + int _ = 16232; 135 +END 136 +CASE(4) 137 + int M = 1073741824; 138 + int count_[] = {894602, 946569, 887230, 856152, 962583, 949356, 904847, 829100, 842183, 958440, 139 + 811081, 864078, 809209, 938727, 949135, 892809, 816528, 961237, 979142, 890922}; 140 + vector <int> count(count_, count_+sizeof(count_)/sizeof(*count_)); 141 + int first_[] = {844085078, 898937259, 243490172, 887804102, 187696417, 156820442, 237600210, 618812924, 153000239, 912364033, 142 + 254936966, 650298774, 982988140, 649258331, 566444626, 201481721, 492943390, 1061953081, 492672963, 960519711}; 143 + vector <int> first(first_, first_+sizeof(first_)/sizeof(*first_)); 144 + int mult_[] = {1036482037, 583219072, 819168094, 253755052, 548208982, 401830167, 638626082, 43642932, 123607749, 485521178, 145 + 860368129, 30334704, 219771462, 733375600, 130839219, 415503960, 294132484, 1044831462, 256910484, 198852170}; 146 + vector <int> mult(mult_, mult_+sizeof(mult_)/sizeof(*mult_)); 147 + int add_[] = {889169006, 604831366, 967292994, 980686280, 844875791, 1027687492, 357734882, 295879743, 48284748, 421729100, 148 + 1049536313, 327207332, 948053446, 271229570, 664579359, 795815285, 842856528, 876662975, 675611938, 634229925}; 149 + vector <int> add(add_, add_+sizeof(add_)/sizeof(*add_)); 150 + int _ = 8971965; 151 +END 152 +CASE(5) 153 + int M = 1073741824; 154 + 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}; 155 + vector <int> count(count_, count_+sizeof(count_)/sizeof(*count_)); 156 + 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}; 157 + vector <int> first(first_, first_+sizeof(first_)/sizeof(*first_)); 158 + 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}; 159 + vector <int> mult(mult_, mult_+sizeof(mult_)/sizeof(*mult_)); 160 + 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}; 161 + vector <int> add(add_, add_+sizeof(add_)/sizeof(*add_)); 162 + int _ = -1; 163 +END 164 +CASE(5) 165 + int M = 1073741824; 166 + 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}; 167 + vector <int> count(count_, count_+sizeof(count_)/sizeof(*count_)); 168 + 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}; 169 + vector <int> first(first_, first_+sizeof(first_)/sizeof(*first_)); 170 + 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}; 171 + vector <int> mult(mult_, mult_+sizeof(mult_)/sizeof(*mult_)); 172 + 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}; 173 + vector <int> add(add_, add_+sizeof(add_)/sizeof(*add_)); 174 + int _ = -1; 175 +END 176 +/* 177 +CASE(6) 178 + int M = ; 179 + int count_[] = ; 180 + vector <int> count(count_, count_+sizeof(count_)/sizeof(*count_)); 181 + int first_[] = ; 182 + vector <int> first(first_, first_+sizeof(first_)/sizeof(*first_)); 183 + int mult_[] = ; 184 + vector <int> mult(mult_, mult_+sizeof(mult_)/sizeof(*mult_)); 185 + int add_[] = ; 186 + vector <int> add(add_, add_+sizeof(add_)/sizeof(*add_)); 187 + int _ = ; 188 +END 189 +*/ 190 +} 191 +// END CUT HERE