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



tải về 440.12 Kb.
trang1/4
Chuyển đổi dữ liệu23.07.2016
Kích440.12 Kb.
  1   2   3   4
Năm học 2002-2003

Bài 1: CHỮ SỐ tên file chương trình CHUSO.PAS

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



  • Cho trước số a0 là một số tự nhiên có tối đa 10 chữ số.

  • Số ai (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 ai-1 chính ai-1 nhưng viết theo thứ tự ngược lại.

Ví dụ:

Với a0 = 123 thì a1 = 123321, a2 = 123321123321, a3 = 123321123321123321123321

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

Dữ liệu cho trong file văn bản với tên là CHUSO.INP trong đó dòng đầu chứa số a0, 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


Giới hạn: 1 N 25, 1 M 1 000 000 000.

Lời giải:

Trước tiên ta nhận xét mặc dù đề bài cho a0 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 a0 như một xâu ký tự.

Gọi L là số ký tự của a0, ta thấy a0 có L ký tự, a1 có 2L ký tự, a2 có 4L ký tự, ..., aN có 2NL ký tự.

Ký hiệu sR là chuỗi ký tự đảo ngược của chuỗi s. Ví dụ: nếu s="abca" thì sR ="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=bRaR. Theo đề bài, ta có a1 = a0a0R, a2=a1a1R=a0a0R(a0a0R)R=a0a0Ra0a0R, ..., aN= a0a0Ra0a0R... a0a0R, nghĩa là xâu aN sẽ ghép thành từ các xâu a0 và a0R 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ự aN, hay nói cách khác nếu M < 1 hoặc M > 2NL 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;


Còn nếu không, ta xem vị trí M sẽ thuộc về một xâu a0 hay một xâu đảo ngược a0R, điều này được chỉ ra bởi giá trị của biểu thức ((M-1) div L) mod 2 bằng 0 hay 1. Biết được điều này, sử dụng phép lấy số dư, ta sẽ tìm được vị trí của ký tự cần tìm trong chuỗi a0:

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 a0R thì ta đảo ngược vị trí i}

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



Chương trình:

const


finp='chuso.inp';

fout='chuso.out';

var

a0: string;



n, m: longint;

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

var l, i: longint;

begin


l:=length(a0);

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;


begin

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 (xi1 , yi1) và tọa độ đỉnh phải trên (xi2, yi2). Các số xi1 , yi1, xi2, yi2 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.

Dữ liệu cho trong file HCN.INP trong đó dòng đầu chứa số N. Dòng thứ i trong N dòng tiếp theo chứa 4 số số xi1 , yi1, xi2, yi2.

Kết quả ghi ra file HCN.OUT gồm 2 dòng, trong đó dòng đầu chứa số S1 là kết quả của câu 1. Dòng thứ hai chứa số S2 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



Bài 3: BẢNG QUẢNG CÁO Tên file chương trình QUANGCAO.PAS

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

Kết quả ghi ra trong file QUANGCAO.OUT trong đó:

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

Ví dụ:

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



Lời giải:

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.

Từ hai nhận xét trên, ta thấy mỗi công tắc sẽ có hai khả năng: tác động hoặc không tác động. Có tất cả M+N công tắc, vậy số khả năng là 2M+N. Theo giới hạn đề bài ra, con số này có thể rất lớn. Tuy nhiên để tìm số bóng đèn sáng nhiều nhất, ta chỉ cần duyệt qua 2N ≤ 210 = 1024 khả năng tác động lên các công tắc trên các hàng của bảng. Với mỗi khả năng này, đối với mỗi cột ta khẳng định được ngay có cần phải tác động lên công tắc của cột đó hay không: nếu tác động lên công tắc cột mà số đèn sáng trên cột đó nhiều hơn thì ta sẽ tác động. Đoạn lệnh sau đây thể hiện điều này. Chú ý trong chương trình dưới đây, ta đánh số cột, hàng bắt đầu từ 0.

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;


Trong 2N khả năng này, ta sẽ chọn ra khả năng cho số bóng đèn sáng nhiều nhất.

Về cài đặt chương trình, chú ý sử dụng kỹ thuật xử lý bit khi duyệt qua 2N 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 2N - 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;



end;

Chương trình:

const


finp='quangcao.inp';

fout='quangcao.out';

maxn=15; maxm=110;

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

var

n, m, kq, sotacdong: longint;



a, b: bang;

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

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

procedure nhap;

var i, j: longint;

begin


readln(n,m);

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;



begin

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

end;

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



var i: longint;

begin


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

end;


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

var i: longint;

begin

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



end;

function sodensang(var a: bang): longint;

var i,j,dem: longint;

begin


dem:=0;

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;


procedure xuly;

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

begin

kq:=0;


for s:=0 to (1 shl n)-1 do begin

b:=a;


t:=0;

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



dem:=0;

for i:=0 to n-1 do

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

if (dem

end;

k:=sodensang(b);



if (k>kq) then begin

kq:=k;


sotacdong:=t;

luuhang:=hang;

luucot:=cot;

end;


end;

end;


procedure xuat;

var i: longint;

begin

writeln(kq);



writeln(sotacdong);

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;


begin

assign(input, finp);

reset(input);

assign(output, fout);

rewrite(output);

nhap;


xuly;

xuat;


close(input);

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

Ví dụ: với bảng A như hình vẽ, đường chéo chính chính là đường chéo có tổng lớn nhất (bằng 14), các file dữ liệu vào/ra lần lượt có nội dung như sau:

SUM.INP




SUM.OUT

4

1 2 4 3


3 4 2 5

2 5 4 3


4 3 2 5




14

Lời giải

Để 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}



inc(j); {sang cột mới}

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;


Chương trình:

const


MAXN=105;

finp='sum.inp';

fout='sum.out';

var


n, i, j, t, s, kq: longint;

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

begin

assign(input, finp);



reset(input);

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


s:=s+a[j+t,j];

inc(j);


until (j+t>n) or (j>n);

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

end;

writeln(kq);



close(input);

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

Lời giải:

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}



inc(dem[x]); {tăng biến đếm số lần xuất hiện của 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}



dem[x]:=0; {gán lại biến đếm bằng 0 để tránh tràn số}

end;


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


for j:=1 to dem[i] do {in ra số i với số lần là dem[i]}

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


assign(input,finp);

reset(input);

assign(output,fout);

rewrite(output);

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

readln(n);

v:=0;

for i:=1 to n do



begin

readln(x);

inc(dem[x]);

if (dem[x]=60000) then

begin

v:=x;


dem[x]:=0;

end;


end;

for i:=-10000 downto 10000 do

begin

for j:=1 to dem[i] do



writeln(i);

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

writeln(i);

end;


close(input);

close(output);

end.

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



Trên mặt phẳng cho N hình vuông với các cạnh song song với hệ trục toạ độ được đánh số từ 1 đến N (1N2000). Hình vuông thứ i được cho bởi toạ độ góc dưới trái (xi, yi) và toạ độ đỉnh phải trên là (zi, ti). Toạ độ của các đỉnh là các số nguyên trong phạm vi -10000 đến 10000. Khoảng cách giữa hai hình vuông A và B được định nghĩa là độ dài đoạn thẳng ngắn nhất trong số các đoạn thẳng mà một đầu mút thuộc hình vuông A và đầu mút kia thuộc hình vuông B.

Yêu cầu: Tìm hai hình vuông xa nhau nhất trong số N hình vuông cho trước.

Dữ liệu: Vào từ file văn bản SQUARE.INP:

  • Dòng đầu tiên chứa số N.

  • Dòng thứ i trong N dòng tiếp theo chứa 4 số xi, yi, zi và ti.

Kết quả: Ghi ra file văn bản SQUARE.OUT trong đó chứa chỉ số của hai hình vuông xa nhau nhất mà bạn tìm được.

Ví dụ:

SQUARE.INP

SQUARE.OUT

3

1 1 3 3


2 2 5 5

7 1 8 2


1 3
  1   2   3   4


Cơ sở dữ liệu được bảo vệ bởi bản quyền ©hocday.com 2016
được sử dụng cho việc quản lý

    Quê hương