Nhập vào 1 dãy số gồm n số tự nhiên. Hãy chia mảng ra thành các dãy con có tổng bằng nhau
Yêu cầu: Em hãy chia mảng ra thành những dãy con nào có tổng bằng nhau
Dữ liệu vào: Cho từ tệp văn bản CHIAMANG.INP gồm:
– Hàng 1 là số n là số phần tử trong dãy (1<=n<=10^7)
- Hàng 2 là các phần tử trong mảng (mỗi phần tử cách nhau 1 khoảng trắng)
Kết quả: Ghi ra tệp văn bản CHIAMANG.OUT gồm các dãy con được chia ra có tổng bằng nhau, mỗi dãy ứng với mỗi dòng (nếu không chia được thì in ra số 0)
const fi=”;
nmax=10000;
type data=longint;
var
f:text;
A:array[0..nmax+1] of data;
n,test:data;
function tknp(dau,cuoi,x:data):data;
var giua:data;
begin
while dau<=cuoi do
begin
giua:=(dau+cuoi) div 2;
if a[giua]=x then
exit(giua)
else
if a[giua]>x then
cuoi:=giua-1
else
dau:=giua+1;
end;
exit(0);
end;
function check(X,sl:data):boolean;
var i,j,id,vt:data;
begin
id:=0;
for i:=1 to sl do
begin
vt:=tknp(id,n,a[id]+x);
if vt=0 then exit(false);
id:=vt;
end;
exit(true);
end;
procedure xuli;
var i,j:data;
begin
i:=a[n];
if a[n] mod i = 0 then
if check(a[n] div i, i) then
begin
writeln(test,’ ‘,a[n] div i);
exit;
end;
i:=a[n] div 2;
if a[n] mod i = 0 then
if check(a[n] div i, i) then
begin
writeln(test,’ ‘,a[n] div i);
exit;
end;
for i:=trunc(sqrt(a[n])) downto 2 do
if a[n] mod i = 0 then
if check(a[n] div i, i) then
begin
writeln(test,’ ‘,a[n] div i);
exit;
end;
writeln(test,’ ‘,a[n]);
end;
procedure docfile;
var i,j,sl:data;
begin
assign(f,fi); reset(f);
read(f,sl);
a[0]:=0;
for i:=1 to sl do
begin
read(f,test,n);
for j:=1 to n do
begin
read(f,a[j]);
a[j]:=a[j-1]+a[j];
end;
xuli;
end;
close(f);
end;
begin
docfile;
end.
Chương trình đại khái là vậy , nếu muốn đúng yêu cầu bạn tự sửa lại nha.