Artifact Content
Not logged in

Artifact 44710d18d6a7b1732f0618d8767e3801bf284499


#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <iterator>
#include <functional>
#include <complex>
#include <queue>
#include <stack>
#include <cmath>
#include <cassert>
#include <cstring>
using namespace std;
typedef long long LL;
typedef complex<double> CMP;

class SubFibonacci { public:
	vector<LL> fib;

	int maxElements(vector <int> S) 
	{
		fib.assign(100, 0);
		fib[0] = 0;
		fib[1] = 1;
		for(size_t k=2; k<fib.size(); ++k)
			fib[k] = fib[k-2] + fib[k-1];

		sort(S.begin(), S.end());
		int result = 0;
		for(int i=0; i<S.size(); ++i) // 50
			result = max(result, longestFib(S,0,i)+longestFib(S,i,S.size()));
		return result;
	}

	int longestFib(const vector<int>& S, int s, int e)
	{
		set<int> all(S.begin()+s, S.begin()+e);
		int result = min(2, e-s);
		for(int i=s; i<e; ++i) // 50
			for(int j=i+1; j<e; ++j) // 50
			{
				LL a = S[i];
				LL b = S[j];
				for(int k=1; fib[k-1]*a<=b; ++k) // fib^-1(100000000)
				{
					LL x = (b-fib[k-1]*a) / fib[k];
					if( x && x!=a && fib[k-1]*a + fib[k]*x == b ) {
						LL p = a;
						LL q = x;
						int len = 2;
						for(;;) {
							if( q == b )
								break;
							if(a<q && all.count(q)) ++len; // if any
							LL pp = p;
							p = q;
							q = pp+q;
						}
						result = max(result, len);
					}
				}
			}
		return result;
	}
};

// BEGIN CUT HERE
#include <ctime>
double start_time; string timer()
 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
 { os << "{ ";
   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
void verify_case(const int& Expected, const int& Received) {
 bool ok = (Expected == Received);
 if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
#define END	 verify_case(_, SubFibonacci().maxElements(S));}
int main(){

CASE(0)
	int S_[] = {8, 1, 20, 3, 10};
	  vector <int> S(S_, S_+sizeof(S_)/sizeof(*S_)); 
	int _ = 5; 
END
CASE(1)
	int S_[] = {19, 47, 50, 58, 77, 99};
	  vector <int> S(S_, S_+sizeof(S_)/sizeof(*S_)); 
	int _ = 4; 
END
CASE(2)
	int S_[] = {512};
	  vector <int> S(S_, S_+sizeof(S_)/sizeof(*S_)); 
	int _ = 1; 
END
CASE(3)
	int S_[] = {3, 5, 7, 10, 13, 15, 20, 90};
	  vector <int> S(S_, S_+sizeof(S_)/sizeof(*S_)); 
	int _ = 7; 
END
CASE(4)
	int S_[] = {1, 2, 3, 5, 8, 13, 21, 34, 55, 89};
	  vector <int> S(S_, S_+sizeof(S_)/sizeof(*S_)); 
	int _ = 10; 
END
CASE(5)
	int S_[] = {1};
	  vector <int> S(S_, S_+sizeof(S_)/sizeof(*S_)); 
	int _ = 1; 
END
CASE(6)
	int S_[] = {1,2};
	  vector <int> S(S_, S_+sizeof(S_)/sizeof(*S_)); 
	int _ = 2; 
END
CASE(7)
	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};
	  vector <int> S(S_, S_+sizeof(S_)/sizeof(*S_)); 
	int _ = 11; 
END
CASE(8)
	int S_[] = {1,3,4,5,61,97,157};
	  vector <int> S(S_, S_+sizeof(S_)/sizeof(*S_)); 
	int _ = 6;
END
CASE(8)
	int S_[] = {2,4,6,10,999,1000};
	  vector <int> S(S_, S_+sizeof(S_)/sizeof(*S_)); 
	int _ = 6;
END
}
// END CUT HERE