## Editorial for VOI 08 Bài 2 - Lò cò

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

#### Code mẫu của flashmt

var a,d:array[1..1000] of longint;
n:integer;

procedure rf;
var i:integer;
begin
for i:=1 to n do
begin
d[i]:=1;
end;
end;

procedure sort(l,r:integer);
var i,j:integer; x,y:longint;
begin
i:=l; j:=r; x:=a[(i+j) div 2];
repeat
while a[i]<x do i:=i+1;
while x<a[j] do j:=j-1;
if i<=j then
begin
y:=a[i]; a[i]:=a[j]; a[j]:=y;
i:=i+1; j:=j-1;
end;
until i>j;
if i<r then sort(i,r);
if l<j then sort(l,j);
end;

function bs(i,j:integer):integer;
var l,r,m:integer; k:longint;
begin
k:=a[i]-a[j];
l:=1; r:=n;
repeat
m:=(l+r) div 2;
if a[m]=k then
begin
if m=j then l:=m+1
else break;
end
else
begin
if a[m]<k then l:=m+1
else r:=m-1;
end;
until l>r;
if a[m]=k then
begin
if d[j]>d[m] then bs:=d[j]
else bs:=d[m];
end
else bs:=0;
end;

procedure pr;
var i,j,max:integer;
begin
sort(1,n);
for i:=3 to n do
begin
max:=0;
for j:=1 to i-1 do
begin
if (bs(i,j)>max) then
max:=bs(i,j);
end;
d[i]:=d[i]+max;
end;
end;

procedure wf;
var i,max:integer;
begin
max:=0;
for i:=1 to n do
if d[i]>max then max:=d[i];
write(max);
end;

begin
rf;
pr;
wf;
end.


#### Code mẫu của happyboy99x

#include <algorithm>
#include <bitset>
#include <cctype>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;

typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef vector<int> vi;
typedef vector<vi> vvi;

#define sz(a) int((a).size())
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(), (c).end()
#define tr(c,i) for(typeof((c).begin()) i = (c).begin(), _e = (c).end(); it != _e; ++it)
#define present(c,x) ((c).find(x) != (c).end())
#define cpresent(c,x) (find(all(c),x) != (c).end())
#define rep(i,n) for(int i = 0, _n = (n); i < _n; ++i)
#define repd(i,n) for(int i = (n)-1; i >= 0; --i )
#define fo(i,a,b) for(int i = (a), _b = (b); i <= _b; ++i)
#define fod(i,a,b) for(int i = (a), _b = (b); i >= _b; --i)

#define INF 1000000000
#define N 1005

int a[N], f[N], n;

int main() {
//freopen( "input.txt", "r", stdin );
//freopen( "output.txt", "w", stdout );
scanf( "%d", &n ); rep(i, n) scanf( "%d", a+i );
sort(a, a+n); fill(f, f+n, 1);
fo(i, 1, n-1) rep(j, i) {
int v = a[i] - a[j];
if(f[j]+1>f[i] && (binary_search(a, a+j, v) || binary_search(a+j+1, a+n, v))) f[i] = f[j]+1;
}
//rep(i, n) printf( "%d ", f[i] ); putchar(10);
printf( "%d\n", *max_element(f, f+n) );
return 0;
}


program nkjump;
uses    math;
const   fi='';
maxN=1111;
var     a,f:array[1..maxN] of longint;
x:array[1..maxN,1..maxN] of boolean;
n:longint;

procedure input;
var     inp:text;
i:longint;
begin
assign(inp,fi);
reset(inp);
for i:=1 to n do
close(inp);
end;

procedure swap(i,j:longint);
var     t:longint;
begin
t:=a[i];
a[i]:=a[j];
a[j]:=t;
end;

procedure sort(l,r:longint);
var     p,i,j:longint;
begin
if l>=r then exit;
p:=a[random(r-l+1)+l];
i:=l;j:=r;
repeat
while a[i]<p do inc(i);
while a[j]>p do dec(J);
if i<=j then
begin
if i<j then swap(i,j);
inc(i);
dec(j);
end;
until i>j;
sort(l,j);sort(i,r);
end;

function find(l,key:longint):longint;
var     r,m:longint;
begin
r:=n;
while l<=r do
begin
m:=(l+r) shr 1;
if a[m]=key then exit(m);
if a[m]<key then l:=m+1
else r:=m-1;
end;
exit(0);
end;

procedure init;
var     i,j,pos:longint;
begin
for i:=1 to n-2 do
for j:=i+1 to n-1 do
begin
pos:=find(j+1,a[i]+a[j]);
if pos<>0 then
begin
x[i,pos]:=true;
x[j,pos]:=true;
end;
end;
end;

procedure dp;
var     i,j:longint;
begin

for i:=1 to n do f[i]:=1;
for i:=2 to n do
for j:=i-1 downto 1 do
if x[j,i] then
f[i]:=max(f[i],f[j]+1);
end;

procedure output;
var     i,res:longint;
begin
res:=0;
for i:=1 to n do
res:=max(res,f[i]);
write(res);
end;

begin
input;
sort(1,n);
init;
dp;
output;
end.


#### Code mẫu của RR

uses math;
const
hashkey=1000003;

type
list=^node;
node=record
u:longint;
next:list;
end;

var
p:list;
begin
new(p); p^.u:=u;
p^.next:=a; a:=p;
end;

var
h:array[0..hashkey] of list;
i,j,n:longint;
a,f:array[0..1011] of longint;

procedure insert(u:longint);
var
p:list;
begin
p:=h[u mod hashkey];
while p<>nil do
begin
if p^.u=u then exit;
p:=p^.next;
end;
end;

function find(u:longint):boolean;
var
p:list;
begin
p:=h[u mod hashkey];
while p<>nil do
begin
if p^.u=u then exit(true);
p:=p^.next;
end;
exit(false);
end;

procedure swap(var a,b:longint);
var
tmp:longint;
begin
tmp:=a; a:=b; b:=tmp;
end;

procedure sort(l,r:longint);
var
i,j,mid:longint;
begin
i:=l; j:=r; mid:=a[l+random(r-l+1)];
repeat
while a[i]<mid do inc(i);
while a[j]>mid do dec(j);
if i<=j then
begin
swap(a[i],a[j]);
inc(i); dec(j);
end;
until i>j;
if i<r then sort(i,r);
if l<j then sort(l,j);
end;

begin
for i:=1 to n do
begin
insert(a[i]);
end;
sort(1,n);
a[0]:=-1000111000;
a[n+1]:=-a[0];

for i:=1 to n do
begin
f[i]:=1;
for j:=1 to i-1 do
if a[i]-a[j]=a[j] then
begin
if (a[j-1]<>a[j]) and (a[j]<>a[j+1]) then begin end
else f[i]:=max(f[i],f[j]+1);
end
else if find(a[i]-a[j]) then f[i]:=max(f[i],f[j]+1);
end;

j:=0;
for i:=1 to n do
j:=max(j,f[i]);
writeln(j);
end.


#### Code mẫu của hieult

#include <stdio.h>
//#include <conio.h>
void Quicksort(long A[],long x,long y)
{
long t=A[(x+y)/2];
long i=x; long j=y;
while(i<=j)
{
while(A[i]<t) i++;
while(A[j]>t) j--;
if(i<=j)
{
if(A[i]!=A[j])
{
long tg=A[i];
A[i]=A[j];
A[j]=tg;
}
i++;
j--;
}
}
if(j>x)
Quicksort(A,x,j);
if(i<y)
Quicksort(A,i,y);
}
main()
{
long n,a[1001],F[1001],Max=1;
scanf("%ld",&n);
for(long i=1;i<=n;i++)
scanf("%ld",&a[i]);
Quicksort(a,1,n);
//for(long i=1;i<=n;i++)
//printf("%ld ",&a[i]);
F[1]=1;F[2]=1;
for(long i=3;i<=n;i++)
{
F[i]=1;
long u=1;long v=i-1;
while(u<v)
{
if(a[u]+a[v]>a[i])
v--;
else if(a[u]+a[v]<a[i])
u++;
else
{
if(F[i]<F[u]+1)
F[i]=F[u]+1;
if(F[i]<F[v]+1)
F[i]=F[v]+1;
u++;
v--;
}
}
if(Max<F[i])
Max=F[i];
}
printf("%ld",Max);
//getch();
}


#### Code mẫu của ll931110

Program NKJUMP;
Const
input  = '';
output = '';
Var
a,F: array[1..1000] of longint;
c: array[1..1000,1..1000] of boolean;
n: longint;

Procedure init;
Var
fi: text;
i: longint;
Begin
Assign(fi, input);
Reset(fi);

For i:= 1 to n do read(fi, a[i]);

Close(fi);
End;

Procedure BubbleSort;
Var
i,j,t: longint;
Begin
For i:= 1 to n - 1 do
For j:= i + 1 to n do
if a[i] > a[j] then
Begin
t:= a[i];
a[i]:= a[j];
a[j]:= t;
End;
End;

Procedure BuildGraph;
Var
i,j,k,last: longint;
Begin
Fillchar(c, sizeof(c), false);

For i:= 1 to n - 2 do
Begin
last:= i + 2;
For j:= i + 1 to n - 1 do
For k:= last to n do
Begin
If a[i] + a[j] = a[k] then
Begin
c[i,k]:= true;
c[j,k]:= true;
End
else if a[i] + a[j] < a[k] then break;
last:= k;
End;
End;
End;

Procedure Topo;
Var
i,j: longint;
Begin
For i:= 1 to n do
Begin
F[i]:= 1;
For j:= 1 to i - 1 do if c[j,i]
and (F[j] + 1 > F[i]) then F[i]:= F[j] + 1;
End;

End;

Procedure solve;
Var
fo: text;
i,res: longint;
Begin
Assign(fo, output);
Rewrite(fo);

res:= F[1];
For i:= 2 to n do if res < F[i] then res:= F[i];

Writeln(fo, res);
Close(fo);
End;

Begin
init;
BubbleSort;
BuildGraph;
Topo;
solve;
ENd.


#### Code mẫu của khuc_tuan

#include <cstdio>
#include <algorithm>
using namespace std;
int n, aa[1010], na, a[1010], f[1010];
int main() {
int i, j, t, r=0;
scanf("%d",&na);
for(i=0;i<na;++i) scanf("%d",aa+i);
sort(aa,aa+na);
for(i=0;i<na;++i) if(n<2 || aa[i]!=a[n-1] || aa[i]!=a[n-2]) a[n++] = aa[i];
for(i=0;i<n;++i) {
if(f[i]==0) f[i]=1;
t = i+1;
for(j=0;j<i;++j)
for(;t<n && a[t]<=a[i]+a[j];++t) if(a[t]==a[i]+a[j]) f[t]>?= (f[i]>?f[j])+1;
}
printf("%d\n",*max_element(f,f+n));
return 0;
}