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

Xét dãy số tự nhiên {a_n} đuợc xây dựng theo quy tắc sau:

• 
  Cho trước số a₀ là một số tự nhiên có tối đa 10 chữ số.
  
• 
  Số a_i (i>0) là một số tự nhiên nhận được từ a­_i-1 bằng cách viết thêm vào sau các chữ số của a_i-1 chính a_i-1 nhưng viết theo thứ tự ngược lại.
  

Với a₀ = 123 thì a₁ = 123321, a₂ = 123321123321, a₃ = 123321123321123321123321

Với hai số N và M cho trước, hãy tìm chữ số thứ M trong a_N.

Dữ liệu cho trong file văn bản với tên là CHUSO.INP trong đó dòng đầu chứa số a₀, dòng thứ hai chứa hai số N và M.

Kết quả ghi ra file văn bản với tên là CHUSO.OUT. Trong trường hợp có lời giải, file này sẽ chứa số tìm được, ngược lại file này chứa số -1.

CHUSO.OUT

1

Ví dụ:

CHUSO.INP

123 3 7

Trước tiên ta nhận xét mặc dù đề bài cho a₀ là số tự nhiên, nhưng vì bài toán không sử dụng tính chất của số nên ta có thể xem a₀ như một xâu ký tự.

Gọi L là số ký tự của a₀, ta thấy a₀ có L ký tự, a₁ có 2L ký tự, a₂ có 4L ký tự, ..., a_N có 2^NL ký tự.

Ký hiệu s^R là chuỗi ký tự đảo ngược của chuỗi s. Ví dụ: nếu s="abca" thì s^R ="acba", các chữ cái được viết theo thứ tự ngược lại. Để ý là với hai chuỗi a, b bất kỳ ta có (ab)^R=b^Ra^R. Theo đề bài, ta có a₁ = a₀a₀^R, a₂=a₁a₁^R=a₀a₀^R(a₀a₀^R)^R=a₀a₀^Ra₀a₀^R, ..., a_N= a₀a₀^Ra₀a₀^R... a₀a₀^R, nghĩa là xâu a_N sẽ ghép thành từ các xâu a₀ và a₀^R xen kẽ nhau.

Từ nhận xét này ta có thuật toán sau:

Nếu vị trí M nằm ngoài xâu ký tự a_N, hay nói cách khác nếu M < 1 hoặc M > 2^NL thì in ra -1. Đoạn lệnh sau đây thể hiện điều này:

if (m<1) or (m>l*(1 shl n)) then begin {chú ý: 1 shl n = 2^n}

timchuso:=-1;

exit;

end;

i:=(m-1) mod l+1; {i là vị trí tương ứng với vị trí M trong chuỗi a0}

if ((m-1) div l) mod 2=1 then i:=l-i+1; {nếu vị trí M thuộc xâu đảo ngược a₀^R thì ta đảo ngược vị trí i}

timchuso:=ord(a0[i])-ord('0'); {kết quả bằng chữ số a0[i]}

const

fout='chuso.out';

var

a0: string;

function timchuso(n,m: longint): longint;

var l, i: longint;

begin

if (m<1) or (m>l*(1 shl n)) then begin timchuso:=-1; exit; end;

i:=(m-1) mod l+1;

if ((m-1) div l) mod 2=1 then i:=l-i+1;

timchuso:=ord(a0[i])-ord('0');

end;

assign(input, finp);

reset(input);

assign(output, fout);

rewrite(output);

readln(a0);

readln(n,m);

write(timchuso(n,m));

close(input);

close(output);

end.

Bài 2: TÍNH DIỆN TÍCH tên file chương trình HCN.PAS

Trên mặt phẳng tọa độ cho N (N 10 000) hình chữ nhật với các cạnh song song với các trục tọa độ. Các hình chữ nhật được đánh số từ 1 tới N. Hình chữ nhật thứ i được cho bởi toạ độ đỉnh trái dưới (x_{i1 ,} y_i1) và tọa độ đỉnh phải trên (x_i2, y_i2). Các số x_{i1 ,} y_i1, x_i2, y_i2 là các số nguyên trong phạm vi từ -100 đến 100.

Hãy lập trình tính:

1. 
   Diện tích của phần mặt phẳng mà N hình chữ nhật này phủ.
   
2. 
   Tính diện tích phần chung của N hình chữ nhật này.
   

Kết quả ghi ra file HCN.OUT gồm 2 dòng, trong đó dòng đầu chứa số S₁ là kết quả của câu 1. Dòng thứ hai chứa số S₂ là kết quả của câu 2.

Ví dụ:

	HCN.INP
	2 0 0 1 1 -1 -1 1 1

HCN.OUT

4 1

Trên quảng trường trung tâm của thủ đô Rome có một bảng quảng cáo hình chữ nhật gồm N x M ô vuông. Mỗi ô có một bóng đèn, mỗi bóng đèn có hai trạng thái tắt hoặc sáng. Ứng với mỗi dòng cũng như mỗi cột có một công tắc. Khi tác động đến một công tắc nào đó tất cả các bóng đèn trên dòng hoặc cột tương ứng sẽ đổi sang trạng thái ngược lại (đang sáng thành tắc, đang tắc được bật sáng). Để mừng đội nhà thắng trận trong trận cầu chiều qua người phụ trách bảng quảng cáo muốn bảng có được nhiều bóng đèn sáng nhất.Với trạng thái bảng quảng cáo hiện thời cho trước, người phụ trách nhờ bạn lập trình tìm một phương án tác động lên các công tắc để nhận được trạng thái bảng quảng cáo mong muốn. Bạn hãy giúp nhà phụ trách thực hiện điều đó.

Dữ liệu cho trong file văn bản với tên là QUANGCAO.INP trong đó:

• 
  Dòng đầu chứa hai số N và M (: 1 N 10, 1 M 100).
  
• 
  Dòng thứ i trong N dòng tiếp theo chứa M số 0 hoặc 1. Số thứ j cho biết trạng thái của bóng đèn thứ j trên dòng thứ i của bảng (1 tương ứng với bóng đèn sáng, 0 tương ứng với bóng đèn tắt).
  

• 
  Dòng đầu là số bóng đèn sáng trên bảng tìm được
  
• 
  Dòng thứ hai chứa S là số lần bạn tác động lên các công tắc.
  
• 
  S dòng tiếp theo lần lượt ghi ra S công tắc theo trình tự cần bật. Dòng thứ j trong S dòng này chứa một xâu độ dài không quá 4, ký tự đầu là ‘D’ hoặc ‘C’ tương ứng với tác động thứ i là lên dòng hay cột. Phần còn lại của xâu là chỉ số của dòng hay cột tương ứng.
  

QUANGCAO.INP		QUANGCAO.OUT
4 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1		16 4 C1 C4 D1 D4

Trước hết ta đưa ra hai nhận xét:

• 
  Mỗi công tắc chỉ cần được tác động nhiều nhất một lần: thật vậy, tác động một công tắc 2 lần sẽ cho kết quả giống như khi không tác động lên công tắc.
  
• 
  Thứ tự tác động lên các công tắc là không quan trọng. Nói cách khác, tác động một dãy công tắc theo trình tự nào cũng mang lại kết quả như nhau.
  

for j:=0 to m-1 do begin

dem:=0; {đếm số đèn sáng trên cột j}

for i:=0 to n-1 do

if (b[i,j]=1) then inc(dem);

if (dem

begin {nếu tác động lên công tắc có lợi hơn:}

batcot(b,j); {tác động!}

inc(t); {tăng biến ghi nhận số lần tác động lên một}

cot[j]:=true; {ghi nhớ rằng đã tác động lên cột j}

end;

end;

Về cài đặt chương trình, chú ý sử dụng kỹ thuật xử lý bit khi duyệt qua 2^N khả năng tác động lên các công tắc trên hàng. Dùng kỹ thuật này, chương trình sẽ được viết nhanh và gọn hơn. Câu lệnh sau đây thực hiện điều này:

for s:=0 to (1 shl n)-1 do {biến s là một dãy N bit thể hiện một khả năng}

Do ta muốn có một dãy N bit đến biến s sẽ chạy từ 0 đến 2^N - 1.

Để kiểm tra trong khả năng s, một công tắc nào đó có được tác động hay không ta dùng thủ tục kiểm tra một bit có được bật hay không:

function bitbat(s, i: longint): boolean;

begin

bitbat:=((s shr i) and 1)=1;

const

fout='quangcao.out';

maxn=15; maxm=110;

type bang=array[0..maxn-1, 0..maxm-1] of byte;

var

n, m, kq, sotacdong: longint;

hang, luuhang: array[0..MAXN-1] of boolean;

cot, luucot: array[0..MAXM-1] of boolean;

procedure nhap;

var i, j: longint;

begin

for i:=0 to n-1 do

for j:=0 to m-1 do

read(a[i,j]);

end;

function bitbat(s, i: longint): boolean;

bitbat:=((s shr i) and 1)=1;

end;

procedure batcot(var a: bang; t: longint);

begin

end;

var i: longint;

begin

for i:=0 to m-1 do a[t,i]:=1-a[t,i];

function sodensang(var a: bang): longint;

var i,j,dem: longint;

begin

for i:=0 to n-1 do for j:=0 to m-1 do if (a[i,j]=1) then inc(dem);

sodensang:=dem;

end;

var s,i,j,dem,k,t: longint;

begin

kq:=0;

b:=a;

fillchar(hang,sizeof(hang),false);

fillchar(cot,sizeof(cot),false);

for i:=0 to n-1 do

if (bitbat(s,i)) then begin

bathang(b,i); inc(t); hang[i]:=true;

end;

for j:=0 to m-1 do begin

for i:=0 to n-1 do

if (b[i,j]=1) then inc(dem);

if (dem

end;

k:=sodensang(b);

kq:=k;

luuhang:=hang;

luucot:=cot;

end;

end;

var i: longint;

begin

writeln(kq);

for i:=0 to m-1 do

if (luucot[i]) then writeln('C',i+1);

for i:=0 to n-1 do

if (luuhang[i]) then writeln('D',i+1);

end;

assign(input, finp);

reset(input);

assign(output, fout);

rewrite(output);

nhap;

xuat;

close(output);

end.

Năm học 2003-2004

Bài 1: TỔNG LỚN NHẤT tên chương trình: SUM.PAS

Cho một bảng A gồm N x N số nguyên (N 100), các dòng được đánh số trên xuống dưới bắt đầu từ 1, các cột được đánh số từ trái qua phải cũng bắt đầu từ 1. Mỗi số trong bảng có giá trị tuyệt đối không vượt quá 10000. Đường chéo chính của bảng là đường thẳng nối hai ô (1,1) và (N,N). Như vậy trên bảng có 2N-1 đuờng chéo song song với đường chéo chính.

Bài toán: Hãy tìm đường chéo song song với đường chéo chính có tổng các phần tử trên đường chéo đó là lớn nhất.

Dữ liệu vào cho trong file văn bản SUM.INP trong đó:

Dòng đầu chứa số N.

Dòng thứ i trong N dòng tiếp theo chứa N số nguyên lần lượt ứng với các phần tử nằm trên dòng thứ i của bảng A.

Kết quả ghi ra trong file văn bản SUM.OUT trong đó chứa một số nguyên duy nhất là tổng các phần tử trên đường chéo mà bạn tìm được.

1	2	4	3 Đường chéo
3	4	2	5
2	5	4	3
4	3	2	5

SUM.INP		SUM.OUT
4 1 2 4 3 3 4 2 5 2 5 4 3 4 3 2 5		14

Để giải bài toán này ta cần biết cách duyệt qua các đường chéo song song với đường chéo chính của bảng số một cách nhanh gọn và hiệu quả. Có rất nhiều cách để thực hiện điều này. Sau đây là một cách: để ý rằng trên một đường chéo, hiệu giữa chỉ số hàng và chỉ số cột là không đổi. Hiệu này nhận giá trị từ 1-N (tương ứng với đường chéo gồm 1 ô góc trên phải (1,N)) cho đến N-1 (tương ứng với đường chéo gồm 1 ô góc dưới trái (N,1)). Do đó ta lần lượt xét các giá trị hiệu từ 1-N đến N-1. Ký hiệu giá trị này là T. Với mỗi giá trị T, ta duyệt qua các cột trên đường chéo tương ứng. Nếu T≥0 (tương ứng với các đường chéo ở nửa dưới của bảng) thì cột bắt đầu là 1 còn nếu T<0 thì cột bắt đầu là 1-T.

Đoạn lệnh sau thể hiện cách làm này:

for t:=1-n to n-1 do

if (t>=0) then j:=1 else j:=1-t; {j là biến lưu cột bắt đầu của đường chéo}

s:=0; {tổng các phần tử trên đường chéo}

repeat

s:=s+a[j+t,j]; {cộng giá trị ô hiện thời vào tổng}

until (j+t>n) or (j>n); {vượt quá phạm vi của bảng}

if (s>kq) then kq:=s; {cập nhật kết quả}

end;

const

finp='sum.inp';

fout='sum.out';

var

a: array[1..MAXN, 1..MAXN] of longint;

begin

assign(input, finp);

assign(output, fout);

rewrite(output);

readln(n);

for i:=1 to n do

for j:=1 to n do

read(a[i,j]);

kq:=-maxlongint;

for t:=1-n to n-1 do begin

if (t>=0) then j:=1 else j:=1-t;

s:=0;

repeat

inc(j);

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

end;

writeln(kq);

close(output);

end.

Bài 2: SẮP XẾP Tên chương trình: SORT.PAS

Cho một dãy X gồm N số nguyên trong phạm vi từ -10000 đến 10000 (1 N 100000). Hãy sắp xếp dãy số này theo thứ tự giảm dần.

Dữ liệu vào cho trong file văn bản SORT.INP trong đó dòng đầu chứa số N. Dòng thứ i trong N dòng tiếp theo chứa số thứ i trong dãy X.

Kết quả ghi ra file văn bản với tên SORT.OUT trong đó lần lượt ghi ra các phần tử của dãy X đã được sắp xếp mỗi số trên một dòng.

Ví dụ:

SORT.INP		SORT.OUT
4 3 4 2 5		5 4 3 2

Phương pháp sắp xếp mà chúng ta dùng là sắp xếp đếm (counting sort). Phương pháp này tận dụng việc giới hạn của các số cần sắp xếp có thể lưu đủ trong bộ nhớ, trong bài toán này phạm vi các số là -10000..10000. Ta sẽ dùng mảng dem[-10000..10000] trong đó dem[x] lưu số lần xuất hiện của số x trong dãy số.

Bài toán này được ra với yêu cầu làm trên trình biên dịch Borland Pascal. Với trình biên dịch cũ này, quản lý bộ nhớ là một điều quan trọng do dung lượng bộ nhớ bị hạn chế. Chúng tôi sẽ trình bày lời giải bài toán này trên cơ sở bộ nhớ hạn chế đó.

Do mỗi số có thể xuất hiện đến N ≤ 100 000 lần nên mảng dem phải mang kiểu dữ liệu longint (số nguyên 32 bit) trong Pascal. Trong Borland Pascal, khi khai báo mảng 20000 phần tử longint sẽ bị báo lỗi là không đủ bộ nhớ. Có một cách để giải quyết điều này:

Khai bảo mảng dem với kiểu dữ liệu word (có giới hạn từ 0..65535) như sau:

var dem: array[-10000..10000] of word;

Ta nhận xét chỉ có nhiều nhất một phần tử của mang dem có thể có giá trị lớn hơn hoặc bằng 60000, vì tổng số lượng số nhiều nhất là 100 000. Do đó ta quản lý thêm một biến lưu phần tử đặc biệt có giá trị đếm vượt 60000 này (nếu có). Ta đặt tên biến này là v. Đoạn lệnh dưới đây đọc vào các số và quản lý dữ liệu:

for i:=1 to n do

begin

readln(x); {đọc vào một số x}

if (dem[x]=60000) then {nếu đã có 60000 số x xuất hiện}

begin

v:=x; {lưu lại số x duy nhất này}

end;

Đoạn lệnh dưới đây in ra các số đã sắp xếp theo thứ tự giảm dần:

for i:=-10000 downto 10000 do {duyệt qua phạm vi của các số: [-10000,10000])

begin

writeln(i);

if (v=i) then for j:=1 to 60000 do {nếu i là số đặc biệt thì ta cần in thêm 60000 lần xuất hiện nữa}

writeln(i);

end;

Chương trình:

const finp='sort.inp';

fout='sort.out';

var dem: array[-10000..10000] of word;

n, i, v: longint;

begin

reset(input);

assign(output,fout);

rewrite(output);

fillchar(dem,sizeof(dem),0);

readln(n);

v:=0;

for i:=1 to n do

readln(x);

inc(dem[x]);

if (dem[x]=60000) then

begin

v:=x;

end;

for i:=-10000 downto 10000 do

begin

for j:=1 to dem[i] do

if (v=i) then for j:=1 to 60000 do

writeln(i);

end;

close(output);

end.

Bài 3: HÌNH VUÔNG tên chưong trình: SQUARE.PAS

• 
  Dòng đầu tiên chứa số N.
  
• 
  Dòng thứ i trong N dòng tiếp theo chứa 4 số x_i, y_i, z_i và t_i.
  

SQUARE.INP	SQUARE.OUT
3 1 1 3 3 2 2 5 5 7 1 8 2	1 3