303270: CF633D. Fibonacci-ish

Memory Limit:512 MB Time Limit:3 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Fibonacci-ish

题意翻译

Yash最近迷上了fibonacci数列,他定义了一种数列叫fibonacccccci数列: 1. 这个数列包含至少2个元素; 2. f[0]和f[1]是任意选取的; 3. f[n+2]=f[n+1]+f[n] (n>=0); 现在,给出一个数列a[1..n],你可以改变数列元素的顺序,使得a[1..m] 满足fibonacccccci数列的条件,请求出最大的m。 【输入数据】 第一行1个数n,表示数列长度

题目描述

Yash has recently learnt about the Fibonacci sequence and is very excited about it. He calls a sequence Fibonacci-ish if 1. the sequence consists of at least two elements 2. $ f_{0} $ and $ f_{1} $ are arbitrary 3. $ f_{n+2}=f_{n+1}+f_{n} $ for all $ n>=0 $ . You are given some sequence of integers $ a_{1},a_{2},...,a_{n} $ . Your task is rearrange elements of this sequence in such a way that its longest possible prefix is Fibonacci-ish sequence.

输入输出格式

输入格式


The first line of the input contains a single integer $ n $ ( $ 2<=n<=1000 $ ) — the length of the sequence $ a_{i} $ . The second line contains $ n $ integers $ a_{1},a_{2},...,a_{n} $ ( $ |a_{i}|<=10^{9} $ ).

输出格式


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

输入输出样例

输入样例 #1

3
1 2 -1

输出样例 #1

3

输入样例 #2

5
28 35 7 14 21

输出样例 #2

4

说明

In the first sample, if we rearrange elements of the sequence as $ -1 $ , $ 2 $ , $ 1 $ , the whole sequence $ a_{i} $ would be Fibonacci-ish. In the second sample, the optimal way to rearrange elements is ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF633D/d3ff4ea2c12e52c9ca4c15e14139f2b01f478bed.png), ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF633D/67db7509088e9e5340d450cc0af986d1466ce169.png), ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF633D/7be78903e0b1130fefbb3533b84d31cf4efaa940.png), ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF633D/0d98505f3f5d3d9cd5c06747ea4bb30d03a8d1e8.png), $ 28 $ .

Input

题意翻译

Yash最近迷上了fibonacci数列,他定义了一种数列叫fibonacccccci数列: 1. 这个数列包含至少2个元素; 2. f[0]和f[1]是任意选取的; 3. f[n+2]=f[n+1]+f[n] (n>=0); 现在,给出一个数列a[1..n],你可以改变数列元素的顺序,使得a[1..m] 满足fibonacccccci数列的条件,请求出最大的m。 【输入数据】 第一行1个数n,表示数列长度

加入题单

上一题 下一题 算法标签: