Số đẹp (Beauty)

[hoasentrang_cm]

Cho một dãy A gồm N số nguyên. Chúng ta gọi số thứ i trong dãy là số đẹp nếu nó bằng tổng của 3 số có vị trí nhỏ hơn i trong dãy A (mỗi số có thể sử dụng nhiều lần trong tổng)
Yêu cầu: xác định dãy số A có bao nhiêu số đẹp.

[chienphuninh]

Có phải là: Ví dụ: Ai: 1 2 3 4 5 6 7 8 9 16. số 6; 8; hiển nhiên là số đẹp theo định nghĩa của bạn. Vậy số 16 có được gọi là số đẹp không?? vì 16 = 1 + 9 + 6; 3 + 5 + 8; 3 + 6 + 7

[chienphuninh]

const a:array[1..10] of int64 = (1,2,3,4,5,6,7,8,9,16);
var i,j,k,n,h:integer; b:array[1..10] of int64;
begin
n:=10;
for i:=n downto 4 do
for j:=i-1 downto 3 do
for k:=j-1 downto 2 do
for h:=k-1 downto 1 do
if a[i]=a[j]+a[k]+ a[h] then b[i]:=1;
for i:=4 to n do if b[i] =1 then Write(a[i],' ');

readln
end.

[hoasentrang_cm]

const a:array[1..10] of int64 = (1,2,3,4,5,6,7,8,9,16);
var i,j,k,n,h:integer; b:array[1..10] of int64;
begin
n:=10;
for i:=n downto 4 do
for j:=i-1 downto 3 do
for k:=j-1 downto 2 do
for h:=k-1 downto 1 do
if a[i]=a[j]+a[k]+ a[h] then b[i]:=1;
for i:=4 to n do if b[i] =1 then Write(a[i],' ');

readln
end.

Ví dụ mình nhập dãy:
1 2 3 5 7 10 thì kết quả có 4 số đẹp.
Đây là một đề thi HSG
Sub 1: duyệt tất cả các phần tử ai sao cho ai=aj+ak+ah
Độ phức tạp O(n4)
Sub 2: nhận xét từ điều kiện ai=aj+ak+ah => ai-aj-ak=ah. Kiểm tra ah mất O(1), sử dụng mảng tính trước.
Độ phức tạp O(n3)
Sub 3: Từ điều kiện ai=aj+ak+ah => ai-aj= ak+ah. Ta tính trước tổng ak+ah
Độ phức tạp O(n2)
Dựa trên ý tưởng đó, bạn phác họa chương trình dùm mình nhé