2. Sử dụng biến “lính canh”

 2. Sử dụng biến “lính canh”
Mọi quốc gia đều có biên giới và lính biên phòng ngày đêm canh gác. Vượt qua biên
giới là sang nước láng giềng.
Tin học cũng “học” đời thường ở cách bố trí lính canh này. Để quản lý phạm vi cần
duyệt, dùng biến canh vị trí đầu và biến canh vị trí cuối của phạm vi này.
Tổ chức hàng đợi (Queue) bằng mảng một chiều là một minh họa điển hình về dùng
biến lính canh. Người ta thường dùng biến first chỉ vào vị trí đầu hàng đợi, biến last chỉ vào
vị trí cuối hàng đợi. Các phần tử trong hàng đợi chờ xử lý chỉ nằm từ vị trí first đến vị trí last.
Biến first còn làm nhiệm vụ định ra vị trí của các phần tử lấy ra khỏi hàng đợi để xử lý; biến
last còn làm nhiệm vụ xác định được vị trí phần tử nạp vào hàng đợi để chờ xử lý.
Ví dụ 1. Dãy con có tổng chia hết cho n
Cho số nguyên dương n và dãy A gồm n số nguyên dương a1, a2, …, an, có thể tạo ra
một dãy con gồm các phần tử liên tiếp của A mà tổng các phần tử chia hết cho n hay không.
Nếu có hãy viết ra dãy con này.
Dữ liệu vào từ tệp input.txt, dòng đầu tiên của mỗi test là số n (1 n 104 ), dòng thứ
hai là các số nguyên dương a1, a2, …, an cách nhau dấu trống.
Kết quả ghi ra tệp output.txt dãy con tìm được hoặc thông báo “No” nếu không tìm
được dãy con nào thỏa mãn. Ví dụ:
Input.txt Output.txt
1
1
3
1 4 2
1
1 2
Phân tích
Giả sử các tổng s1= a1, s2= a1+a2, s3=a1+a2+a3, …, sn=a1+a2+…+an khi chia cho n có các
dư tương ứng là r1, r2, …, rn. Nếu trong chúng có ri=0 thì dãy {a1, a2, …, ai } là dãy con cần tìm.
Do có n số r1, r2, …, rn mà chỉ thuộc n-1 loại dư (từ 0 đến n-1) nên tồn tại ri và rj bằng nhau
(i<j) (theo nguyên l{ Đi-rich-lê). Suy ra sj-si=ai+1+ai+2+…+aj chia hết cho n vậy {ai+1,ai+2,…,aj} là
dãy con cần tìm. Bài toán luôn luôn có nghiệm. Khi lập trình, ta dùng mảng S để lưu lại dãy
{s1, s2, …, sn} và mảng B với { nghĩa B*r+ là vị trí i mà Si chia cho n có dư r. Đồng thời chúng ta
dùng 2 biến “lính canh”: bs và es để đánh dấu vị trí i+1 và j khi gặp sj-si chia hết cho n, đó là
vị trí đầu và cuối của dãy con cần tìm.
Văn bản chương trình
Program Day_con_co_tong_chia_het_cho_n;
const maxn = 10000;
fi = 'input.txt';
fo = 'output.txt';
var f, g : text;
a : array[1..maxn] of longint;
b : array[0..maxn] of longint;
s, r : longint;
n, i, bs, es : longint;
begin
assign(f,fi); reset(f);
assign(g,fo); rewrite(g);
while true do begin
if eof(f) then break;
readln(f,n);
if n=0 then break;
for i:=1 to n do read(f,a[i]);
s := 0;
fillchar(b, sizeof(b),0);
for i:=1 to n do begin
s := s + a[i];
r := s mod n;
if r=0 then begin
bs := 1; es := i;
break;
end
else {r <>0}
if b[r]<>0 then begin
bs := b[r] +1; es := i;
break;
end;
b[r]:=i;
end;
for i:=bs to es do write(g,a[i]:6);
writeln(g);
end;
close(f); close(g);
end.