Bài 4: Bảng vuông
Cho một bảng vuông các số nguyên kích thước NxN (2 < N< 100) mà mỗi phần tử là một số nguyên không âm và giá trị không vượt quá 100.
Yêu cầu: hãy tìm một bảng vuônmg con của bảng đã cho mà các phần tử của nó chứa toàn số dương và tổng các phần tử thuộc bảng con này có giá trị lớn nhất.
Dữ liệu chop trong file văn bản có tên BANG.INP:
Dòng đầu chứa số N.
Dòng thứ I trong N dòng tiếp theo chứa N số nguyên dương ứng với dòng thứ i của bảng.
Kết quả xuất ra file văn bản BANG.OUT chứa 1 số nguyên duy nhất chứa giá trọ tổng lớn nhất tìm được.
Ví dụ:
-
BANG . INP
|
|
BANG . OUT
|
3
1 1 0
1 2 1
1 1 2
|
|
6
|
Lời giải
Để giải quyết bài toán này, ta dùng một phương pháp thường gặp khi xử lý các phép tính tổng trên bảng số: dùng bảng lưu tổng bộ phận. Cụ thể là, ta sẽ dùng bảng s với ý nghĩa: s[i,j] là tổng các số trên bảng từ ô (1,1) đến ô (i,j). Mỗi khi đọc phần tử (i, j), bảng s sẽ được cập nhật theo công thức
s[i,j]:=s[i-1,j]+s[i,j-1]-s[i-1,j-1]+a[i,j];
Và để tính tổng các số trong hình chữ nhật (i1,j1) đến (i2,j2) ta dùng công thức:
s[i2,j2]-s[i1-1,j2]-s[i2,j1-1]+s[i1-1,j1-1]
Để xử lý điều kiện bảng số chứa toàn số dương, ta dùng thêm bảng c theo kỹ thuật tương tự bảng s với ý nghĩa: c[i,j] là số số 0 trên bảng ban đầu trong hình chữ nhật từ ô (1,1) đến ô (i,j). Để xét xem một vùng hình chữ nhật có gồm toàn số dương hay không, ta dùng công thức tính tổng như trên và xem kết quả có bằng 0 hay không.
Để duyệt qua các hình vuông con trên bảng số, ta xét tất cả các đỉnh trên trái (i,j) và độ dài cạnh hình vuông L. Tổng các số trong hình vuông và điều kiện chứa toàn số dương được tính theo công thức như trình bày ở trên. Thời gian thực hiện của thuật toán là O(N3), hoàn toàn khả thi với giới hạn N ≤ 100.
Chương trình mẫu
const MAXN=105;
finp='bang.inp';
fout='bang.out';
type bang=array[0..MAXN, 0..MAXN] of longint;
function max(a,b:longint): longint;
begin
if a>b then max:=a else max:=b;
end;
function sum(a: bang; i1,j1,i2,j2: longint): longint;
begin
sum:=a[i2,j2]-a[i1-1,j2]-a[i2,j1-1]+a[i1-1,j1-1];
end;
var
c, s: bang;
n,i,j,l,x,i1,j1,i2,j2,kq: longint;
begin
assign(input,'bang.inp');
reset(input);
assign(output,'bang.out');
rewrite(output);
fillchar(s,sizeof(s),0);
fillchar(c,sizeof(c),0);
readln(n);
for i:=1 to n do
for j:=1 to n do begin
read(x);
s[i,j]:=s[i-1,j]+s[i,j-1]-s[i-1,j-1]+x;
c[i,j]:=c[i-1,j]+c[i,j-1]-c[i-1,j-1];
if (x=0) then inc(c[i,j]);
end;
kq:=0;
for i1:=1 to n do
for j1:=1 to n do
begin
l:=0;
repeat
i2:=i1+l;
j2:=j1+l;
if sum(c,i1,j1,i2,j2)=0 then
kq:=max(kq,sum(s,i1,j1,i2,j2))
else
break;
inc(l);
until (i2>n) or (j2>n);
end;
writeln(kq);
close(input);
close(output);
end.
Năm học 2006-2007
ĐOẠN CON DÀI NHẤT
(Bài 1 – Tuyển sinh 2006 - 2007)
Cho chuỗi kí tự S gồm toàn các chữ cái in hoa (A…Z) với độ dài không vượt quá 255. Hãy tìm đoạn con các kí tự liên tiếp dài nhất sao cho không có kí tự nào xuất hiện nhiều hơn một lần. Trong trường hợp có nhiều hơn một đoạn con có cùng chiều dài dài nhất, hãy chỉ ra đoạn xuất hiện đầu tiên trong chuỗi S.
Dữ liệu: Vào từ văn bản SUBSTR.INP gồm một dòng duy nhất chứa chuỗi S.
Kết quả: Ghi ra file văn bản SUBSTR.OUT hai số nguyên P và L tương ứng là vị trí và chiều dài của đoạn con dài nhất tìm được (kí tự đầu tiên trong chuỗi có vị trí là 1).
Ví dụ:
-
SUBSTR.INP
|
|
SUBSTR.OUT
|
ABABCDAC
|
|
3 4
|
Lời giải
Ta duyệt qua lần lượt các ký tự của chuỗi. Khi duyệt qua ký tự thứ i, ta sẽ tìm cách xây dựng chuỗi dài nhất không có ký tự nào xuất hiện hai lần và kết thúc tại vị trí i. Để xây dựng được chuỗi này, ta cần lưu trữ các thông tin sau đây:
-
Vị trí bắt đầu của chuỗi dài nhất mà không có ký tự nào xuất hiện hai lần, ta ký hiệu là p.
-
Mảng b['A'..'Z'] trong đó với ký tự c thì b[c] lưu vị trí xuất hiện cuối cùng của ký tự c.
Khi duyệt qua ký tự thứ i (ký hiệu là s[i]):
-
Nếu vị trí xuất hiện cuối cùng của ký tự này không nhỏ hơn p, nghĩa là ký tự này sẽ xuất hiện 2 lần và làm cho chuỗi đang xét trở nên không hợp lệ. Khi đó ta cập nhật lại vị trí bắt đầu p bằng b[s[i]]+1.
-
Ta cập nhật lại giá trị i cho b[s[i]] để đảm bảo ý nghĩa của mảng b
-
Chuỗi đang xét sẽ bắt đầu từ vị trí p và kết thúc tại vị trí i, do đó chuỗi này có độ dài là i-p+1, ta dùng giá trị này so sánh với kết quả để tìm ra chuỗi dài nhất.
Đoạn chương trình sau đây thể hiện thuật toán:
p:=1; {gán giá trị khởi tạo cho p: vị trí bắt đầu là 1}
for i:=1 to length(s) do {duyệt qua từng ký tự của chuỗi}
begin
if (b[s[i]]>=p) then {ký tự s[i] xuất hiện hai lần trong chuỗi đang xét!}
p:=b[s[i]]+1; {cập nhật lại vị trí bắt đầu mới}
b[s[i]]:=i; {cập nhật lại vị trí xuất hiện của ký tự s[i]}
if (i-p+1>l) then begin {i-p+1 là độ dài của chuỗi đang xét}
{so sánh với độ dài lớn nhất l}
luup:=p; {lưu lại vị trí bắt đầu}
l:=i-p+1; {cập nhật lại độ dài lớn nhất}
end;
end;
Chương trình:
const finp='substr.inp';
fout='substr.out';
var
b:array['A'..'Z'] of longint;
s:string;
p,i,l,luup: longint;
begin
assign(input,finp);
reset(input);
assign(output,fout);
rewrite(output);
readln(s);
fillchar(b,sizeof(b),0);
p:=1;
for i:=1 to length(s) do
begin
if (b[s[i]]>=p) then
p:=b[s[i]]+1;
b[s[i]]:=i;
if (i-p+1>l) then begin
luup:=p;
l:=i-p+1;
end;
end;
writeln(luup,' ',l);
close(input);
close(output);
end.
ĐƯỜNG ĐI
(Bài 2 – Tuyển sinh 2006 - 2007)
Một con robot di chuyển theo một chương trình định sẵn trên mặt phẳng toạ độ. Chương trình này được thể hiện dưới dạng một dãy N lệnh (1N3000). Các lệnh thuộc một trong các dạng sau:
-
F S: Đi thẳng theo hướng hiện tại S bước.
-
R S: Rẽ phải 900 và đi S bước.
-
L S: Rẽ trái 900 và đi S bước.
Yêu cầu: Cho một chương trình điều khiển robot, hãy xác định chiều dài T đoạn đường mà con robot đã đi được, biết mỗi bước của nó dài d(cm). Ban đầu con robot đứng tại vị trí (0,0) và hướng theo chiều dương của trục hoành.
Dữ liệu: Vào từ file văn bản PATH.INP:
-
Dòng đầu tiên chứa 2 số nguyên dương N và d.
-
N dòng tiếp theo, mỗi dòng chứa một lệnh theo quy cách nêu trên.
Kết quả: Ghi ra file PATH.OUT chứa chiều dài T tìm được.
Ví dụ:
-
PATH.INP
|
|
PATH.OUT
|
4 1
F 5
R 7
F 2
L 9
|
|
23
|
Lời giải:
Kết quả của bài toán này bằng tích của d và tổng của độ dài các bước đi. Các lệnh F, R, L không ảnh hưởng đến kết quả của bài toán và chỉ được đưa ra để kiểm tra thí sinh có thuần thục trong việc đọc dữ liệu hay không.
Mỗi câu lệnh sẽ gồm hai ký tự (một chữ cái chỉ lệnh và một khoảng trắng) và một số, do đó ta đọc vào hai biến kiểu ký tự và một biến kiểu số nguyên:
readln(c,c,x);
Ta sẽ sử dụng biến x, còn c chỉ là biến tạm không được dùng đến.
Chương trình mẫu
const finp='path.inp';
fout='path.out';
var i, n, d, x, s: longint;
c: char;
begin
assign(input,finp);
reset(input);
assign(output,fout);
rewrite(output);
readln(n,d);
for i:=1 to n do begin
readln(c,c,x);
s:=s+x;
end;
writeln(x);
close(input);
close(output);
end.
ĐẾM VÙNG
(Bài 3 – Tuyển sinh 2006 - 2007)
Một khu vườn hình chữ nhật được chia thành ô đơn vị. Các dòng đánh số từ 1 tới M từ trên xuống dưới, các cột đánh số từ 1 đến N từ trái sang phải. Ô nằm ở hàng i, cột j được gọi là ô (i,j). Người ta có đắp K lối đi trên mảnh vườn đó, lối đi thứ i là một dãy các ô liên tiếp nhau theo đường ngang hoặc đường dọc, và được cho bởi 4 số nguyên dương xi, yi, zi và ti trong đó (xi, yi) là vị trí của ô đầu, còn (zi, ti) là vị trí của ô cuối của lối đi. Các lối đi chia khu vườn thành các miền. Mỗi miền là một tập tất cả các ô không thuộc các lối đi sao cho hai ô bất kì trong đó có thể đi tới bằng cách di chuyển qua các ô chung cạnh và không phải là ô thuộc lối đi.
Yêu cầu: Hãy xác định số miền S mà các lối đi chia khu vườn.
Dữ liệu: Vào từ file văn bản REGIONS.INP trong đó:
-
Dòng đầu chứa 3 số M, N, K.
-
Dòng thứ i trong K dòng tiếp theo chứa 4 số xác định lối đi thứ i: xi, yi, zi, ti.
Kết quả: Ghi ra file văn bản REGIONS.OUT số S tìm được.
Ví dụ:
-
REGIONS.INP
|
|
REGIONS.OUT
|
10 10 2
5 1 5 10
1 5 7 5
|
|
3
|
SỐ ƯỚC
(Bài 4 – Tuyển sinh 2006 - 2007)
Cho số nguyên dương N. Giai thừa của N, kí hiệu là N!, là tích của các số tự nhiên từ 1 đến N. Gọi T là số lượng ước lớn hơn 1 của N!. Ví dụ với N = 4, ta có 4! = 24. Như vậy 4! có 7 ước lớn hơn 1 là: 2, 3, 4, 6, 8, 12, 24.
Yêu cầu: Cho N, hãy xác định T.
Dữ liệu: Vào từ file văn bản DIVISORS.INP trong đó chứa duy nhất số N (N20, trong đó 50% số test có N10).
Kết quả: Ghi ra file văn bản DIVISORS.OUT số T tìm được.
Ví dụ:
-
DIVISORS.INP
|
|
DIVISORS.OUT
|
4
|
|
7
|
Lời Giải
Nếu một số nguyên m được phân tích ra thừa số nguyên tố dưới dạng m=p1a1p2a2...pkak thì số ước số của m bằng tích (a1+1)(a2+1)...(ak+1). Ta sẽ tìm cách phân tích n! ra thừa số nguyên tố. Các ước số nguyên tố của n! chỉ nằm trong phạm vi từ 2 đến n, do đó ta duyệt qua tất cả các số nguyên tố trong phạm vi này. Với số nguyên tố p, số mũ của nó trong biểu diễn nguyên tố của n! bằng:
[n/p] + [n/p2] + [n/p3] + ...
Trong đó [n/p] ký hiệu phần nguyên của n/p, nói cách khác trong ngôn ngữ Pascal [n/p] bằng n div p. Công thức trên được giải thích như sau: [n/p] là số lượng số từ 1 đến n chia hết cho p, [n/p2] là số lượng số từ 1 đến n chia hết cho p2,... mỗi số này đều đóng góp một thừa số nguyên tố p phân biệt cho n!.
Đoạn chương trình sau đây thể hiện thuật toán:
for i:=2 to n do if nguyento(i) then {duyệt qua các số nguyên tố từ 2 đến n}
begin
a:=0;
j:=i; {biến j sẽ duyệt qua các số mũ của i là i, i2, i3,...}
while (j<=n) do {đến khi j>n thì dừng lại vì khi đó [n/j] sẽ luôn bằng 0}
begin
a:=a+n div j;
j:=j*i;
end;
{đến đây a=[n/i]+[n/i2]+... chính là số thừa số i
trong biểu diễn nguyên tố của n!}
d:=d*(a+1); {nhân thêm (a+1) vào số ước, theo công thức tính số ước nêu trên}
end;
Chương trình:
function nguyento(n: longint): boolean;
var i: longint;
begin
nguyento:=false;
for i:=2 to trunc(sqrt(n)) do
if n mod i = 0 then exit;
nguyento:=true;
end;
var
n,i,j,a,d: longint;
begin
readln(n);
d:=1;
for i:=2 to n do if nguyento(i) then
begin
a:=0;
j:=i;
while (j<=n) do
begin
a:=a+n div j;
j:=j*i;
end;
d:=d*(a+1);
end;
writeln(d-1);
end.
Năm học 2007-2008
TÍCH LỚN NHẤT
(Bài 1 – Tuyển sinh 2007 - 2008)
Cho một dãy gồm N số nguyên. Hãy tìm 3 số trong dãy với tích T của chúng là lớn nhất.
Dữ liệu: Vào từ file văn bản TICHMAX.INP:
-
Dòng đầu ghi số N (3N10000).
-
Dòng thứ hai chứa N số nguyên có giá trị tuyệt đối không vượt quá 30000.
Kết quả: Ghi ra file văn bản TICHMAX.OUT một số duy nhất T.
Ví dụ:
-
TICHMAX.INP
|
TICHMAX.OUT
|
9
3 5 1 7 9 0 9 -3 10
|
810
|
Lời giải
Nếu tích lớn nhất của 3 phần tử bao gồm:
-
Ba số dương: ba số này phải lần lượt là số lớn nhất, nhì, ba trong dãy
-
Một số âm và hai số dương: dãy phải gồm đúng hai số dương, vì nếu không ta có thể lấy tích ba số dương để đạt giá trị lớn hơn. Ta cũng suy ra ba số này phải là ba số lớn nhất, nhì, ba trong dãy.
-
Hai số âm và một số dương: số dương phải là số lớn nhất và hai số âm phải là hai số nhỏ nhất, nhì trong dãy.
-
Ba số âm: dãy phải gồm toàn số âm, vì nếu có một số dương ta cũng có thể lấy tích của số dương đó và hai số âm để thu được tích dương. Ta cũng suy ra được ba số cần tìm phải là ba số lớn nhất, nhì, ba của dãy.
Vậy suy ra, T=max(max1*max2*max3,min1*min2*max1), với max1, max2, max3, min1, min2 lần lượt là số lớn nhất, nhì, ba và số nhỏ nhất, nhì của dãy.
Ta có thể đọc qua lần lượt các số của dãy và cập nhật max1, max2, max3, min1, min2 mà không cần lưu lại dãy số. Đoạn lệnh dưới đây cập nhật min1, min2 khi đọc vào một số mới x:
if (x<=min1) then
begin
min2:=min1; {min1 giờ trở thành số bé thứ hai}
min1:=x; {số bé nhất là x}
end else if (x<=min2) then
min2:=x; {số bé thứ hai là x}
Việc cập nhật max1, max2, max3 được thực hiện hoàn toàn tương tự.
Chú ý vì kết quả có thể vượt quá kiểu số nguyên 32 bit nên ta cần khai báo với kiểu số nguyên 64 bit (trình biên dịch Free Pascal hỗ trợ kiểu số nguyên 64 bit với tên gọi int64):
var
...
kq:int64;
...
kq:=max(max1*max2*max3,min1*min2*max1);
Chương trình:
const finp='tichmax.inp';
fout='tichmax.out';
var max1,max2,max3,min1,min2,x,i,n:longint;
kq:int64;
function max(a,b:longint):longint;
begin
if a>b then max:=a else max:=b;
end;
begin
assign(input,finp);
reset(input);
assign(output,fout);
rewrite(output);
max1:=-maxlongint;
max2:=max1;
max3:=max1;
readln(n);
for i:=1 to n do begin
read(x);
if (x>=max1) then
begin
max3:=max2;
max2:=max1;
max1:=x;
end else if (x>=max2) then
begin
max3:=max2;
max2:=x;
end else if (x>=max3) then
begin
max3:=x;
end;
if (x<=min1) then
begin
min2:=min1;
min1:=x;
end else if (x<=min2) then
min2:=x;
end;
kq:=max(max1*max2*max3,min1*min2*max1);
writeln(kq);
close(input);
close(output);
end.
TÌM DÃY K
(Bài 2 – Tuyển sinh 2007 - 2008)
Cho một xâu S có độ dài N. Với mỗi số nguyên i (1iN), xét xâu con Si gồm i kí tự đầu của xâu S. Người ta cần xác định giá trị Ki cho mỗi xâu Si là giá trị lớn nhất thỏa mãn điều kiện sau:
Nếu xâu X là xâu con gồm Ki kí tự đầu của xâu Si và tạo xâu Y bằng cách viết Ki kí tự cuối cùng của xâu Si theo thứ tự ngược từ cuối lên đầu ta có X = Y.
Ví dụ, nếu S = ‘acbaca’ thì S4 = ‘acba’ và vì vậy K4 = 1, vì khi đó X = Y = ‘a’.
S6 = ‘acbaca’ và vì vậy K6 = 2 do khi đó X = Y = ‘ac’.
Yêu cầu: Cho xâu S độ dài N, tìm các số K1, K2, …, KN.
Dữ liệu: Vào từ file văn bản DAYK.INP:
-
Dòng đầu tiên chứa số nguyên dương N (N255).
-
Dòng thứ hai chứa xâu S độ dài N.
Kết quả: Ghi ra file văn bản DAYK.OUT trên một dòng duy nhất dãy số K1, K2, …, KN.
Ví dụ:
-
DAYK.INP
|
DAYK.OUT
|
6
acbaca
|
1 0 0 1 0 2
|
Lời giải
Ta dùng vòng lặp i từ 1 đến N, với mỗi giá trị i ta tìm cách xác định số Ki theo như yêu cầu của đề bài. Số Ki chính là phần dài nhất mà khi nhìn từ trái sang phải và từ phải sang trái của chuỗi Si đều như nhau, nói cách khác trên chuỗi Si ký tự đầu tiên bằng ký tự cuối, ký tự thứ hai bằng ký tự kề cuối, ..., ký tự thứ Ki bằng ký tự thứ i-Ki.
Để xác định Ki ta dùng vòng lặp while tăng dần giá trị của Ki khi nào điều kiện s[1+k]=s[i-k] còn đúng:
k:=0;
while (s[1+k]=s[i-k]) do inc(k);
Chương trình:
const finp='dayk.inp';
fout='dayk.out';
var n, i, k: longint;
s: string;
begin
assign(input,finp);
reset(input);
assign(output,fout);
rewrite(output);
readln(n);
readln(s);
for i:=1 to n do
begin
k:=0;
while (s[1+k]=s[i-k]) do inc(k);
write(k,' ');
end;
close(input);
close(output);
end.
TÌM SỐ ÂM LỚN NHẤT
(Bài 3 – Tuyển sinh 2007 - 2008)
Cho một dãy gồm N số nguyên a1, a2, …, aN, mỗi số có giá trị tuyệt đối không vượt quá 105.
Yêu cầu: Hãy tìm số âm lớn nhất X trong dãy.
Dữ liệu: Vào từ file văn bản SOAM.INP:
-
Dòng đầu tiên chứa số nguyên dương N (1N105).
-
N dòng tiếp theo, dòng thứ i chứa số ai.
Kết quả: Ghi ra file văn bản SOAM.OUT trên một dòng duy nhất số X tìm được. Trong trường hợp không có lời giải, ghi ra số 0.
Ví dụ:
-
SOAM.INP
|
|
SOAM.OUT
|
5
-4
3
2
-5
7
|
|
-4
|
Lời giải:
Ta đọc qua các số của dãy và tìm số lớn nhất, tuy nhiên chỉ các số âm mới được xét đến. Ta dùng thêm một cờ để kiểm tra trong dãy có tồn tại số âm hay không.
if (x<0) then {chỉ xét số âm}
begin
co:=true; {đánh dấu cờ là có tồn tại số âm}
if (x>kq) then kq:=x; {cập nhật với kết quả lớn nhất}
end;
Chương trình:
const finp='soam.inp';
fout='soam.out';
var n, kq, i, x: longint;
co: boolean;
begin
assign(input,finp);
reset(input);
assign(output,fout);
rewrite(output);
co:=false;
readln(n);
kq:=-maxlongint;
for i:=1 to n do
begin
readln(x);
if (x<0) then
begin
co:=true;
if (x>kq) then kq:=x;
end;
end;
if co then writeln(kq) else writeln(0);
end.
Chia sẻ với bạn bè của bạn: |