DÃY HÌNH CHỮ NHẬT LỒNG NHAU

Trên mặt phẳng tọa độ cho N hình chữ nhật với các cạnh song song với hệ 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 4 số nguyên dương x_i1, y­_i1, x_i2, y_i2, trong đó (x_i1, y­_i1) là tọa độ đỉnh trái dưới, còn (x_i2, y­_i2) là tọa độ đỉnh phải trên. Ta nói rằng hình chữ nhật thứ I nằm trong hình chữ nhật thứ j nếu trên mặt phẳng tọa độ, mọi điểm của hình chữ nhật i đều thuộc hình chữ nhật j.

• 
  Dòng đầu tiên chứa số nguyên dương N (1N100).
  
• 
  N dòng tiếp theo, dòng thứ i chứa 4 số nguyên dương x_i1, y­_i1, x_i2, y_i2.
  

HCN.INP		HCN.OUT
3 1 1 7 4 3 1 6 6 2 2 5 4		2

Bước 1, ta sắp xếp các hình chữ nhật theo thứ tự giảm dần của diện tích. Điều này đảm bảo một hình chữ nhật chỉ có thể bị bao bởi một hình chữ nhật xuất hiện phía trước nó. Đoạn chương trình sau thực hiện việc sắp xếp:

for i:=1 to n-1 do

for j:=i+1 to n do

if (dientich(h[i])

begin

end;

f[i]:=1; {khởi tạo giá trị ban đầu cho f[i]}

for j:=i-1 downto 1 do

if bao(h[j],h[i]) then {j là vị trí lớn nhất mà hình chữ nhật

h[j] bao hình chữ nhật h[i]}

begin

break; {thoát khỏi vòng lặp}

end;

if (f[i]>kq) then kq:=f[i]; {cập nhật lại kết qủa}

const

fout='hcn.out';

MAXN=105;

type hcn=record x1,y1,x2,y2: longint; end;

var

h: array[1..MAXN] of hcn;

i,j,n,kq: longint;

tam:hcn;

function dientich(a:hcn):longint;

begin

with a do dientich:=(x2-x1)*(y2-y1);

function bao(a,b:hcn):boolean;

begin

bao:=(a.x1<=b.x1) and (b.x2<=a.x2) and

end;

assign(input,finp);

reset(input);

assign(output,fout);

rewrite(output);

readln(n);

for i:=1 to n do

with h[i] do

readln(x1,y1,x2,y2);

for i:=1 to n-1 do

for j:=i+1 to n do

if (dientich(h[i])

begin

tam:=h[i];h[i]:=h[j];h[j]:=tam;

kq:=0;

begin

for j:=i-1 downto 1 do

if bao(h[j],h[i]) then

begin

break;

if (f[i]>kq) then kq:=f[i];

end;

writeln(kq);

close(output);

end.

Năm học 2008-2009

Bài 1: Mã hoá

Để quản lý tốt các hồ sơ trong kỳ thi tuyển sinh, hội đồng tuyển sinh trường PTNK đã quyết định đánh số các hồ sơ theo một phương pháp khoa học. Mã hồ sơ của thí sinh là một chuỗi gồm 10 chữ số. Tuy nhiên không phải bất kỳ chuỗi 10 chữ số nào cũng là mã hồ sơ hợp lệ bởi vì hội đồng tuyển sinh đưa ra một quy định ràng buộc chặt chẽ cho các chữ số đó. Nếu M=a₁a₂..a₁₀ là một mã hồ sơ thì M phải thỏa mãn ràng buộc:

Nếu đặt S(M)=1a₁+2a₂+3a₃+…+10a₁₀ thì S(M) phải là một số chia hết cho 11.

Nhờ quy định này, trong những trường hợp do sơ xuất có một chữ số trong mã hồ sơ bị mờ, không đọc được thì ta vẫn có thể xác định được giá trị của nó. Ví dụ như: (quy ước ? là chữ số bị mờ):

• 
  Với M=00000000?1 thì có thể suy ra chữ số bị mờ là 5 vì theo ràng buộc, để S(M) là một số chia hết cho 11 nó chỉ có thể có giá trị là 55.
  
• 
  Tương tự với M=00000001?1 thì có thể suy ra chữ số bị mờ là 9.
  
• 
  Tương tự với M=00722?0858 thì có thể suy ra chữ số bị mờ là 6.
  

Ví dụ:

00000000?1

ENCODE.OUT

5

00000001?1

00722?0858

6

Lời giải:

Ta thử thay từng chữ số từ 0 đến 9 vào vị trí "?" và tính xem điều kiện S(M) chia hết cho 11 có được thoả mãn hay không như đoạn chương trình sau đây:

for i:=1 to 10 do

{r là tổng các số hạng của S(M) trừ vị trí có dấu ‘?’}

if (s[i]<>'?') then r:=(r+i*(ord(s[i])-ord('0'))) mod 11;

i:=pos('?',s); {i là vị trí của dấu ‘?’}

for d:=0 to 9 do {duyệt qua tất cả các chữ số từ 0 đến 9}

if (r+i*d) mod 11 = 0 then {kiểm tra xem S(M) có chia hết cho 11}

begin

writeln(d); {d chính là chữ số cần tìm}

end;

const

fout='encode.out';

var

s: string;

c: char;

assign(input,finp);

reset(input);

assign(output,fout);

rewrite(output);

readln(s);

for i:=1 to 10 do

if (s[i]<>'?') then r:=(r+i*(ord(s[i])-ord('0'))) mod 11;

i:=pos('?',s);

for d:=0 to 9 do

if (r+i*d) mod 11 = 0 then

begin

break;

close(input);

close(output);

end.

Cho dãy các số nguyên khác nhau đôi một a gồm n số a₁, a₂, ..., a_n và dãy số nguyên b gồm n số b₁, b₂, ..., b_n. Trên dãy số a ta có thể áp dụng phép biến đổi T(i) thực hiện phép hoán vị giá trị hai phần tử a_i và a_i+1 (0i1, T_i2, …, T_ik sao cho khi áp dụng, dãy a ban đầu sẽ biến thành dãy b.

Ví dụ nếu dãy a là 1, 3, 2, 4 và dãy b là 2, 1, 3, 4 thì ta có thẻ sử dụng dãy 2 phép biến đổi T(2) và T(1) để biến đổi a thành b.

Yêu cầu: Cho hai dãy số a, b . Hãy chỉ ra một dãy các phép biến đổi a thành b hoặc cho biết không tồn tại dãy biến đổi như vậy.

Dữ liệu: Vào từ file văn bản EXARRAY.INP gồm 3 dòng:

• 
  Dòng đầu tiên chứa số nguyên n là số lượng phần tử của mỗi dãy số (n<=100).
  
• 
  Dòng thứ hai chứa n số nguyên đôi một khác nhau ứng với các phần tử của dãy số a.
  
• 
  Dòng cuối cùng chứa n số nguyên ứng với các phần tử của dãy số b.
  

• 
  Nếu không thể biến đổi a thành b, file chứa số duy nhất số -1.
  
• 
  Trong trường hợp ngựoc lại, file sẽ gồm 2 dòng:
  
  • 
    Dòng đầu tiên chứa số nguyên k là số lượng phép biến đổi cần áp dụng.
    
  • 
    Dòng thứ hai chứa k số nguyên duơng i₁, i₂, …, i_k ứng với các phép biến đổi T_i1, T_i2, …, T_ik tìm được.
    

EXARRAY.INP

4

1 3 2 4

EXARRAY.OUT

2

2 1

1

5

EXARRAY.OUT

-1

Lời giải:

Thuật toán của ta đơn giản như sau: tìm b[1] trong dãy a rồi di chuyển lên đầu dãy a, sau đó lại tìm b[2] rồi di chuyển lên vị trí thứ hai của dãy a, ... Nếu tại một bước ta không tìm thấy số tương ứng trong dãy a thì in ra -1.

Đoạn chương trình sau thể hiện thuật toán:

for i:=1 to n do {duyệt qua tất cả các phần tử của dãy b}

begin

vt[i]:=0; {vt[i] là vị trí xuất hiện của b[i] trong dãy a}

if (a[j]=b[i]) then {tìm đặt b[i]}

begin

vt[i]:=j; {cập nhật lại vt[i]}

end;

begin

để đưa số từ vị trí vt[i] về vị trí i}

for j:=vt[i]-1 downto i do trao(j) {thực hiện biến đổi!}

end

begin {nếu không tìm được số b[i]}

writeln(-1); {in ra -1}

exit; {thoát khỏi thủ tục}

end;

end;

const MAXN=102;

finp='exarray.inp';

fout='exarray.out';

var n: longint;

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

procedure nhap;

var i: longint;

begin

readln(n);

for i:=1 to n do read(b[i]);

end;

var kq: longint;

procedure trao(i: longint);

var tam: longint;

begin

end;

var i, j, tam: longint;

begin

for i:=1 to n do

vt[i]:=0;

for j:=i to n do

if (a[j]=b[i]) then

begin

vt[i]:=j;

end;

begin

for j:=vt[i]-1 downto i do trao(j)

end

else

writeln(-1);

exit;

end;

writeln(kq);

for i:=1 to n do

for j:=vt[i]-1 downto i do

write(j,' ');

end;

assign(input,finp);

reset(input);

assign(output,fout);

rewrite(output);

nhap;

close(input);

close(output);

end.

Xét bảng vuông gồm n dòng và n cột. Các dòng được đánh số từ 1 đến n từ trên xuống dưới. Các cột được đánh số từ 1 đến n từ trái sang phải. Ô nằm ở vị trí dòng i và cột j của bảng được gọi là ô (i,j). Trên bảng A đã cho, khoảng cách từ ô (i,j) đến ô (p,q) được tính bằng |i-p|+|j-q|. Tại ô (i,j) của bảng A ghi số nguyên không âm a_ij, i=1,2,…,n; j=1,2,..,n. Dựa vào các số được ghi trên bảng A, người ta cần xây dựng một bảng B cùng kích thước với A mà trên đó ô (i,j) của bảng B sẽ được ghi số b_ij xác định như sau:

• 
  Nếu a_ij > 0 thì b_ij = a_ij
  
• 
  Nếu a_ij = 0 thì b_ij có giá trị bằng giá trị a_pq của ô (p,q) gần ô (i,j) nhất trong số các ô có giá trị khác không trên dòng i và cột j của bảng A. Trong truờng hợp có nhiều ô khác không có cùng khoảng cách nhỏ nhất đến (i,j) thì ô (p,q) đựoc chọn là ô chứa số lớn nhất trong chúng. Nếu tất cả các phần tử của dòng i và cột j đều có giá trị 0 thì b_ij = 0.
  

• 
  Dòng đầu tiên ghi số nguyên dương n (n ≤ 50)
  
• 
  Dòng thứ i trong số n dòng tiếp theo ghi n số nguyên không âm a_i1, a_i2, …, a_in là các số trên dòng thứ i của bảng, i=1,2,…,n; a_ij ≤ 10000.
  

Hai số liên tiếp trên cùng một dòng được ghi cách nhau bởi một dấu cách.

NZTABLE.INP

4

1 0 3 0

0 0 6 0

NZTABLE.OUT

1 3 3 5

4 4 6 5

4 0 6 5

Ta xây dựng mảng b giống như định nghĩa của đề bài như đoạn chương trình sau:

if (a[i,j]>0) then b:=a[i,j] else {biển b chỉ phần tử b_ij. Nếu a_ij > 0 thì b_ij = a_ij}

begin

kc:=maxlongint; {kc là biến lưu khoảng cách, gán bằng ∞

vì ta cần giá trị nhỏ nhất}

for p:=1 to n do {duyệt qua các ô trên cột j}

if (a[p,j]<>0) then {chỉ xét các ô có giá trị khác 0}

if ((abs(i-p)

((abs(i-p)=kc) and (a[p,j]>b))) {có khoảng cách bằng nhưng giá trị lớn hơn}

then

kc:=abs(i-p); {cập nhật lại khoảng cách}

b:=a[p,j]; {cập nhật lại b_ij}

end;

... {thực hiện tương tự}

if (kc=maxlongint) then b:=0; {nếu tất cả các phần tử của dòng i, cột j

đều bằng 0 thì b_ij=0}

end;

write(b,' '); {in b_ij ra màn hình}

const MAXN=55;

finp='NZTABLE.INP';

fout='NZTABLE.OUT';

var i, j, b, n, kc, p: longint;

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

for i:=1 to n do

begin

for j:=1 to n do

if (a[i,j]>0) then b:=a[i,j] else

begin

b:=-maxlongint;

for p:=1 to n do

if (a[p,j]<>0) then

if ((abs(i-p)b))) then

begin

kc:=abs(i-p);

end;

if (a[i,p]<>0) then

if ((abs(j-p)b))) then

begin

b:=a[i,p];

end;

if (kc=maxlongint) then b:=0;

write(b,' ');

end;

writeln;

close(input);

close(output);

end.

Việc bảo vệ máy tính của mình để hạn chế người khác thâm nhập vào là một vấn đề đặt ra cho mọi nguời sử dụng máy tính. Để tăng tính an toàn trong lưu trữ, một nguời đã quyết định dấu mật khẩu truy cập máy tính của mình vào một xâu T với một quy ước sao cho khi cần anh ta có thể lấy lại đuợc mật khẩu từ T như sau.

Là một người yêu thích số học anh ta thường chọn mật khẩu P là một số nguyên tố và đem dấu vào một xâu ký tự T sao cho P chính là số nguyên tố có giá trị lớn nhất trong số các số nguyên tố tạo được từ các xâu con của T (xâu con của một xâu ký tự T là một chuỗi liên tiếp các ký tự trong T).

Ví dụ: xâu T=”Test1234#password5426” chứa mật khẩu là 23 vì T chứa các xâu con ứng với các số nguyên tố 2,3,23 và 5.

PASSWORD.INP

Test1234#password5426

PASSWORD.OUT

23

Lời giải:

Ta duyệt qua tất cả các xâu con của xâu T mà có thể tạo thành một số và kiểm tra số đó có phải số nguyên tố hay không.

Để duyệt qua các xâu con, ta duyệt qua vị trí đầu:

for i:=1 to length(t) do {i là vị trí đầu của xâu con}

Với mỗi vị trí đầu i, ta duyệt qua vị trí cuối của xâu con:

j:=i;

begin

inc(j);

Có hai điều kiện để ta dừng quá trình duyệt một xâu con với vị trí đầu là i:

• 
  Gặp một ký tự không phải chữ số:
  

• 
  Số tạo thành lớn hơn hoặc bằng 10⁵, vì đề bài đã nêu rõ P có giá trị nhỏ hơn 10⁵:
  

Khi đọc được một chữ số mới, ta nhân số hiện tại với 10 rồi cộng thêm chữ số mới:

v:=v*10+ord(t[j])-ord('0');

Nếu số thu được là số nguyên tố và lớn hơn kết quả tốt nhất tìm được thì cập nhật kết quả:

if nguyento(v) then

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

const finp='password.inp';

fout='password.out';

function nguyento(n: longint): boolean;

var i: longint;

begin

if n<2 then exit;

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

if (n mod i = 0) then

exit;

nguyento:=true;

var t: string;

i, kq, v, j: longint;

begin

reset(input);

assign(output,fout);

rewrite(output);

readln(t);

kq:=-1;

begin

j:=i;

begin

v:=v*10+ord(t[j])-ord('0');

if v>=100000 then break;

writeln(v);

if nguyento(v) then

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

inc(j);

end;

writeln(kq);

close(input);

close(output);