Năm học 2002-2003 Bài 1

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.

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

Để 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(N³), 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;

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];

var

n,i,j,l,x,i1,j1,i2,j2,kq: longint;

begin

assign(input,'bang.inp');

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 j1:=1 to n do

begin

l:=0;

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

inc(l);

end;

close(input);

close(output);

end.

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.

SUBSTR.INP		SUBSTR.OUT
ABABCDAC		3 4

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.
  

• 
  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.
  

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

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;

const finp='substr.inp';

fout='substr.out';

var

s:string;

p,i,l,luup: longint;

begin

reset(input);

assign(output,fout);

rewrite(output);

readln(s);

fillchar(b,sizeof(b),0);

p:=1;

for i:=1 to length(s) do

if (b[s[i]]>=p) then

p:=b[s[i]]+1;

b[s[i]]:=i;

if (i-p+1>l) then begin

luup:=p;

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 90⁰ và đi S bước.
  
• 
  L S: Rẽ trái 90⁰ và đi S bước.
  

• 
  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.
  

PATH.INP		PATH.OUT
4 1 F 5 R 7 F 2 L 9		23

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

reset(input);

assign(output,fout);

rewrite(output);

readln(n,d);

for i:=1 to n do begin

readln(c,c,x);

s:=s+x;

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 x_i, y_i, z_i và t_i trong đó (x_­i­, y_i) là vị trí của ô đầu, còn (z_i­, t_i) 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.

• 
  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: x_i, y_i, z_i, t_i.
  

REGIONS.INP		REGIONS.OUT
10 10 2 5 1 5 10 1 5 7 5		3

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.

DIVISORS.INP		DIVISORS.OUT
4		7

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=p₁^a1p₂^a2...p_k^ak thì số ước số của m bằng tích (a₁+1)(a₂+1)...(a_k+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/p²] + [n/p³] + ...

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/p²] là số lượng số từ 1 đến n chia hết cho p²,... 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;

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;

end;

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;

function nguyento(n: longint): boolean;

var i: longint;

begin

for i:=2 to trunc(sqrt(n)) do

if n mod i = 0 then exit;

nguyento:=true;

end;

var

begin

d:=1;

begin

j:=i;

begin

j:=j*i;

d:=d*(a+1);

end;

writeln(d-1);

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ò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.
  

TICHMAX.INP	TICHMAX.OUT
9 3 5 1 7 9 0 9 -3 10	810

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.
  

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

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

...

...

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;

begin

reset(input);

assign(output,fout);

rewrite(output);

max1:=-maxlongint;

max2:=max1;

max3:=max1;

readln(n);

for i:=1 to n do begin

read(x);

begin

max2:=max1;

max1:=x;

end else if (x>=max2) then

begin

max3:=max2;

end else if (x>=max3) then

begin

max3:=x;

if (x<=min1) then

begin

min2:=min1;

end else if (x<=min2) then

min2:=x;

end;

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 S_i gồm i kí tự đầu của xâu S. Người ta cần xác định giá trị K_i cho mỗi xâu S_i là giá trị lớn nhất thỏa mãn điều kiện sau:

Ví dụ, nếu S = ‘acbaca’ thì S₄ = ‘acba’ và vì vậy K₄ = 1, vì khi đó X = Y = ‘a’.

S₆ = ‘acbaca’ và vì vậy K₆ = 2 do khi đó X = Y = ‘ac’.

Yêu cầu: Cho xâu S độ dài N, tìm các số K₁, K₂, …, K_N.

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.
  

DAYK.INP	DAYK.OUT
6 acbaca	1 0 0 1 0 2

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ố K_i theo như yêu cầu của đề bài. Số K_i 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 S_i đều như nhau, nói cách khác trên chuỗi S_i 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ứ K_i bằng ký tự thứ i-K_i.

Để xác định K_i ta dùng vòng lặp while tăng dần giá trị của K_i khi nào điều kiện s[1+k]=s[i-k] còn đúng:

k:=0;

const finp='dayk.inp';

fout='dayk.out';

var n, i, k: longint;

s: string;

begin

reset(input);

assign(output,fout);

rewrite(output);

readln(n);

readln(s);

for i:=1 to n do

begin

while (s[1+k]=s[i-k]) do inc(k);

write(k,' ');

end;

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 a₁, a₂, …, a_N, mỗi số có giá trị tuyệt đối không vượt quá 10⁵.

• 
  Dòng đầu tiên chứa số nguyên dương N (1N10⁵).
  
• 
  N dòng tiếp theo, dòng thứ i chứa số a_i.
  

SOAM.INP		SOAM.OUT
5 -4 3 2 -5 7		-4

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

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

reset(input);

assign(output,fout);

rewrite(output);

co:=false;

readln(n);

kq:=-maxlongint;

for i:=1 to n do

begin

readln(x);

begin

if (x>kq) then kq:=x;

end;

end;

end.