c5054cb313 2011-07-26 kinaba: #include <iostream> c5054cb313 2011-07-26 kinaba: #include <sstream> c5054cb313 2011-07-26 kinaba: #include <iomanip> c5054cb313 2011-07-26 kinaba: #include <vector> c5054cb313 2011-07-26 kinaba: #include <string> c5054cb313 2011-07-26 kinaba: #include <map> c5054cb313 2011-07-26 kinaba: #include <set> c5054cb313 2011-07-26 kinaba: #include <algorithm> c5054cb313 2011-07-26 kinaba: #include <numeric> c5054cb313 2011-07-26 kinaba: #include <iterator> c5054cb313 2011-07-26 kinaba: #include <functional> c5054cb313 2011-07-26 kinaba: #include <complex> c5054cb313 2011-07-26 kinaba: #include <queue> c5054cb313 2011-07-26 kinaba: #include <stack> c5054cb313 2011-07-26 kinaba: #include <cmath> c5054cb313 2011-07-26 kinaba: #include <cassert> c5054cb313 2011-07-26 kinaba: #include <cstring> c5054cb313 2011-07-26 kinaba: using namespace std; c5054cb313 2011-07-26 kinaba: typedef long long LL; c5054cb313 2011-07-26 kinaba: typedef complex<double> CMP; c5054cb313 2011-07-26 kinaba: c5054cb313 2011-07-26 kinaba: class SubFibonacci { public: c5054cb313 2011-07-26 kinaba: vector<LL> fib; c5054cb313 2011-07-26 kinaba: c5054cb313 2011-07-26 kinaba: int maxElements(vector <int> S) c5054cb313 2011-07-26 kinaba: { c5054cb313 2011-07-26 kinaba: fib.assign(100, 0); c5054cb313 2011-07-26 kinaba: fib[0] = 0; c5054cb313 2011-07-26 kinaba: fib[1] = 1; c5054cb313 2011-07-26 kinaba: for(size_t k=2; k<fib.size(); ++k) c5054cb313 2011-07-26 kinaba: fib[k] = fib[k-2] + fib[k-1]; c5054cb313 2011-07-26 kinaba: c5054cb313 2011-07-26 kinaba: sort(S.begin(), S.end()); c5054cb313 2011-07-26 kinaba: int result = 0; c5054cb313 2011-07-26 kinaba: for(int i=0; i<S.size(); ++i) // 50 c5054cb313 2011-07-26 kinaba: result = max(result, longestFib(S,0,i)+longestFib(S,i,S.size())); c5054cb313 2011-07-26 kinaba: return result; c5054cb313 2011-07-26 kinaba: } c5054cb313 2011-07-26 kinaba: c5054cb313 2011-07-26 kinaba: int longestFib(const vector<int>& S, int s, int e) c5054cb313 2011-07-26 kinaba: { c5054cb313 2011-07-26 kinaba: set<int> all(S.begin()+s, S.begin()+e); c5054cb313 2011-07-26 kinaba: int result = min(2, e-s); c5054cb313 2011-07-26 kinaba: for(int i=s; i<e; ++i) // 50 c5054cb313 2011-07-26 kinaba: for(int j=i+1; j<e; ++j) // 50 c5054cb313 2011-07-26 kinaba: { c5054cb313 2011-07-26 kinaba: LL a = S[i]; c5054cb313 2011-07-26 kinaba: LL b = S[j]; c5054cb313 2011-07-26 kinaba: for(int k=1; fib[k-1]*a<=b; ++k) // fib^-1(100000000) c5054cb313 2011-07-26 kinaba: { c5054cb313 2011-07-26 kinaba: LL x = (b-fib[k-1]*a) / fib[k]; c5054cb313 2011-07-26 kinaba: if( x && x!=a && fib[k-1]*a + fib[k]*x == b ) { c5054cb313 2011-07-26 kinaba: LL p = a; c5054cb313 2011-07-26 kinaba: LL q = x; c5054cb313 2011-07-26 kinaba: int len = 2; c5054cb313 2011-07-26 kinaba: for(;;) { c5054cb313 2011-07-26 kinaba: if( q == b ) c5054cb313 2011-07-26 kinaba: break; c5054cb313 2011-07-26 kinaba: if(a<q && all.count(q)) ++len; // if any c5054cb313 2011-07-26 kinaba: LL pp = p; c5054cb313 2011-07-26 kinaba: p = q; c5054cb313 2011-07-26 kinaba: q = pp+q; c5054cb313 2011-07-26 kinaba: } c5054cb313 2011-07-26 kinaba: result = max(result, len); c5054cb313 2011-07-26 kinaba: } c5054cb313 2011-07-26 kinaba: } c5054cb313 2011-07-26 kinaba: } c5054cb313 2011-07-26 kinaba: return result; c5054cb313 2011-07-26 kinaba: } c5054cb313 2011-07-26 kinaba: }; c5054cb313 2011-07-26 kinaba: c5054cb313 2011-07-26 kinaba: // BEGIN CUT HERE c5054cb313 2011-07-26 kinaba: #include <ctime> c5054cb313 2011-07-26 kinaba: double start_time; string timer() c5054cb313 2011-07-26 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } c5054cb313 2011-07-26 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) c5054cb313 2011-07-26 kinaba: { os << "{ "; c5054cb313 2011-07-26 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) c5054cb313 2011-07-26 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } c5054cb313 2011-07-26 kinaba: void verify_case(const int& Expected, const int& Received) { c5054cb313 2011-07-26 kinaba: bool ok = (Expected == Received); c5054cb313 2011-07-26 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; c5054cb313 2011-07-26 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } c5054cb313 2011-07-26 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); c5054cb313 2011-07-26 kinaba: #define END verify_case(_, SubFibonacci().maxElements(S));} c5054cb313 2011-07-26 kinaba: int main(){ c5054cb313 2011-07-26 kinaba: c5054cb313 2011-07-26 kinaba: CASE(0) c5054cb313 2011-07-26 kinaba: int S_[] = {8, 1, 20, 3, 10}; c5054cb313 2011-07-26 kinaba: vector <int> S(S_, S_+sizeof(S_)/sizeof(*S_)); c5054cb313 2011-07-26 kinaba: int _ = 5; c5054cb313 2011-07-26 kinaba: END c5054cb313 2011-07-26 kinaba: CASE(1) c5054cb313 2011-07-26 kinaba: int S_[] = {19, 47, 50, 58, 77, 99}; c5054cb313 2011-07-26 kinaba: vector <int> S(S_, S_+sizeof(S_)/sizeof(*S_)); c5054cb313 2011-07-26 kinaba: int _ = 4; c5054cb313 2011-07-26 kinaba: END c5054cb313 2011-07-26 kinaba: CASE(2) c5054cb313 2011-07-26 kinaba: int S_[] = {512}; c5054cb313 2011-07-26 kinaba: vector <int> S(S_, S_+sizeof(S_)/sizeof(*S_)); c5054cb313 2011-07-26 kinaba: int _ = 1; c5054cb313 2011-07-26 kinaba: END c5054cb313 2011-07-26 kinaba: CASE(3) c5054cb313 2011-07-26 kinaba: int S_[] = {3, 5, 7, 10, 13, 15, 20, 90}; c5054cb313 2011-07-26 kinaba: vector <int> S(S_, S_+sizeof(S_)/sizeof(*S_)); c5054cb313 2011-07-26 kinaba: int _ = 7; c5054cb313 2011-07-26 kinaba: END c5054cb313 2011-07-26 kinaba: CASE(4) c5054cb313 2011-07-26 kinaba: int S_[] = {1, 2, 3, 5, 8, 13, 21, 34, 55, 89}; c5054cb313 2011-07-26 kinaba: vector <int> S(S_, S_+sizeof(S_)/sizeof(*S_)); c5054cb313 2011-07-26 kinaba: int _ = 10; c5054cb313 2011-07-26 kinaba: END c5054cb313 2011-07-26 kinaba: CASE(5) c5054cb313 2011-07-26 kinaba: int S_[] = {1}; c5054cb313 2011-07-26 kinaba: vector <int> S(S_, S_+sizeof(S_)/sizeof(*S_)); c5054cb313 2011-07-26 kinaba: int _ = 1; c5054cb313 2011-07-26 kinaba: END c5054cb313 2011-07-26 kinaba: CASE(6) c5054cb313 2011-07-26 kinaba: int S_[] = {1,2}; c5054cb313 2011-07-26 kinaba: vector <int> S(S_, S_+sizeof(S_)/sizeof(*S_)); c5054cb313 2011-07-26 kinaba: int _ = 2; c5054cb313 2011-07-26 kinaba: END c5054cb313 2011-07-26 kinaba: CASE(7) c5054cb313 2011-07-26 kinaba: int S_[] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50}; c5054cb313 2011-07-26 kinaba: vector <int> S(S_, S_+sizeof(S_)/sizeof(*S_)); c5054cb313 2011-07-26 kinaba: int _ = 11; c5054cb313 2011-07-26 kinaba: END c5054cb313 2011-07-26 kinaba: CASE(8) c5054cb313 2011-07-26 kinaba: int S_[] = {1,3,4,5,61,97,157}; c5054cb313 2011-07-26 kinaba: vector <int> S(S_, S_+sizeof(S_)/sizeof(*S_)); c5054cb313 2011-07-26 kinaba: int _ = 6; c5054cb313 2011-07-26 kinaba: END c5054cb313 2011-07-26 kinaba: CASE(8) c5054cb313 2011-07-26 kinaba: int S_[] = {2,4,6,10,999,1000}; c5054cb313 2011-07-26 kinaba: vector <int> S(S_, S_+sizeof(S_)/sizeof(*S_)); c5054cb313 2011-07-26 kinaba: int _ = 6; c5054cb313 2011-07-26 kinaba: END c5054cb313 2011-07-26 kinaba: } c5054cb313 2011-07-26 kinaba: // END CUT HERE