Nguồn đề bài: http://www.spoj.com/PTIT/problems/BCSEQ1/
1. Đề bài BCSEQ1 spoj
Một đoạn số có tổng bằng nhau trong một dãy số là một nhóm các số theo đúng thứ tự ban đầu trong dãy mà nếu nhóm với nhau thì sẽ cho ra cùng một giá trị tổng. Ví dụ với dãy: 2 5 1 3 3 7 thì ta có thể nhóm thành: (2 5) (1 3 3) (7) cùng cho giá trị tổng là 7.
Chú ý: đoạn đặc biệt chứa tất cả các phần tử của dãy cũng được coi là một đoạn có tổng bằng nhau với chính giá trị tổng các số của dãy đó.
Yêu cầu: viết chương trình nhận vào các dãy số nguyên dương và trả về giá trị tổng nhỏ nhất có thể của một đoạn tổng bằng nhau trong dãy.
Dữ liệu vào
Dòng đầu tiên chứa một số nguyên 1 ≤ t ≤ 1000 là số lượng bộ test. Mỗi bộ test bao gồm:
- Dòng đầu tiên chứa thứ tự bộ test và số M (1≤ M ≤ 10000) là số phần tử của dãy.
- Các dòng tiếp theo mỗi dòng ghi 10 số của dãy phân cách bởi 1 dấu cách. Dòng cuối cùng có thể có ít hơn 10 số. (Các số trong dãy đều nhỏ hơn 20000).
Dữ liệu ra
Với mỗi bộ test, in ra trên một dòng gồm số thứ tự bộ test và tổng nhỏ nhất có thể đạt được của các đoạn số có tổng bằng nhau.
Example
| INPUT | OUTPUT | |
| 31 6 2 5 1 3 3 7 2 6 1 2 3 4 5 6 3 20 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 | 1 72 21 3 2 |
2. Hướng dẫn BCSEQ1 spoj
– Đầu tiên xây dựng mảng A, với A[i] là tổng của A[1]..A[i] tức là A[i]:=a[i-1]+a[i].
– Ta nhận xét, nếu N là số phần tử thì ta chỉ có thể chia tối ta [1..n] nhóm. Vậy chỉ có thể chia thành X nhóm thì tổng của mảng A chia hết cho X. từ đó ta sẽ thử các trường hợp đó.
– việc còn lại là xây dựng hàm kiểm tra, có thể chia thành X nhóm hay không. Để xử lí được vấn đề này. như ở bước đầu, mình đề nghị xây dựng mảng A, chỉ cần dùng Tìm kiếm nhị phân để kiểm tra là được.
+ đầu tiên đứng ở vị trí 0 (gọi là H), chặt NP tìm vị trí ( gọi là k ) mà a[k]-a[H]=tổng đoạn con được chia, rồi từ vị trí đó cứ tiếp tục tìm như vậy. nếu tìm có đủ X lần ( số lượng đoạn dc chia) thì hàm trả về KQ TRUE, còn không thì thoát ngay hàm và trả về FALSE. phần xây dựng hàm kiểm tra mình giải thích hơi khó hiểu nên các bạn có thể xem code.
3. Code Tham khảo BCSEQ1 spoj
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.
