Manthan, Codefest 16 D. Fibonacci-ish

D. Fibonacci-ish

time limit per test

3 seconds

memory limit per test

512 megabytes

input

standard input

output

standard output

Yash has recently learnt about the Fibonacci sequence and is very excited about it. He calls a sequence Fibonacci-ish if

the sequence consists of at least two elements
f0 and f1 are arbitrary
fn + 2 = fn + 1 + fn for all n ≥ 0.

You are given some sequence of integers a1, a2, ..., an. Your task is rearrange elements of this sequence in such a way that its longest possible prefix is Fibonacci-ish sequence.

Input

The first line of the input contains a single integer n (2 ≤ n ≤ 1000) — the length of the sequence ai.

The second line contains n integers a1, a2, ..., an (|ai| ≤ 109).

Output

Print the length of the longest possible Fibonacci-ish prefix of the given sequence after rearrangement.

Examples

input

3
1 2 -1

output

input

5
28 35 7 14 21

output

Note

In the first sample, if we rearrange elements of the sequence as - 1, 2, 1, the whole sequence ai would be Fibonacci-ish.

In the second sample, the optimal way to rearrange elements is , , , , 28.

思路：直接暴力枚举前两个元素，然后先离散化下，并用map一一对应下数值，开个数组记录各个值的个数，然后根据斐波那契数列依次推下个数字

在数组中查找，其中开始为0，0需要特判否则复杂度n³；

 1 #include<stdio.h>

 2 #include<algorithm>

 3 #include<iostream>

 4 #include<string.h>

 5 #include<math.h>

 6 #include<queue>

 7 #include<map>

 8 using namespace std;

 9 const long long N=1e9+7;

10 typedef long long LL;

11 LL vv[25];

12 LL MM[1005];

13 int NN[1005];

14 int KK[1005];

15 map<LL,LL>my;

16 LL quickmi(long long  a,long long  b);

17 int main(void)

18 {

19     int i,j,k;

20     while(scanf("%d",&k)!=EOF)

21     {memset(NN,0,sizeof(NN));

22         for(i=0; i<k; i++)

23         {

24             scanf("%I64d",&MM[i]);

25         }

26         int cnt=1;sort(MM,MM+k);my[MM[0]]=1;

27         NN[1]++;

28         for(i=1; i<k; i++)

29         {

30             if(MM[i]!=MM[i-1])

31                 cnt++;

32             NN[cnt]++;

33             my[MM[i]]=cnt;

34         }int maxx=2;

35         for(i=0; i<k; i++)

36         {

37             for(j=0; j<k; j++)

38             {int sum=2;

39                 if(i!=j)

40                 {int KK[1005]={0};LL p=MM[i];LL q=MM[j];

41                 if(p==0&&q==0)

42                 {

43                     sum=NN[my[0]];

44                 }

45                 else {KK[my[p]]++;KK[my[q]]++;

46                  while(true)

47                  {

48                      LL ans=p+q;

49                      KK[my[ans]]++;

50                      if(KK[my[ans]]<=NN[my[ans]])

51                      sum++;

52                      else break;

53                      p=q;q=ans;

54                  }}

55                  if(sum>maxx)

56                     maxx=sum;}

57             }

58         }printf("%d\n",maxx);

59     }

60     return 0;

61 }

62

63 LL quickmi(long long  a,long long  b)

64 {

65     LL sum=1;

66     while(b)

67     {

68         if(b&1)

69             sum=(sum*a)%(N);

70         a=(a*a)%N;

71         b/=2;

72     }

73     return sum;

74 }

巴特西

Manthan, Codefest 16 D. Fibonacci-ish

最新文章

热门文章