HomeBài tập 20_9
Thứ Ba, 20 tháng 9, 2016
Hãy lập
trình giải các bài toán sau:
Bài 1. Đếm điểm trên lưới. (4 điểm) points.pas
Một ngày nọ, Bờm đố Cuội một trò “đơn giản” như
sau: Cho một hình vuông có kích thước bất kỳ, ban đầu Bờm có bốn điểm là bốn
đỉnh của hình vuông. Ở lần thứ nhất, Bờm thực hiện hai thao tác như sau:
- Thêm một
điểm vào mỗi vị trí trung điểm của mỗi cạnh của hình vuông.
- Thêm một
điểm vào giao điểm của hai đường chéo của hình vuông.
Sau hai thao tác thực hiện trên, Bờm đã có bốn hình vuông mới. Ở lần thứ
hai, Bờm lại thực hiện hai thao tác trên với mỗi hình vuông có được.
Bờm đố Cuội rằng, sau lần thực hiện thứ N, trên
hình vuông ban đầu sẽ có tất cả bao nhiêu điểm?
Dữ liệu vào: points.inp Một dòng duy nhất chứa số nguyên N (0 ≤ N ≤ 25)
Dữ liệu ra: points.out Một dòng duy nhất ghi số điểm tìm được.
Ví dụ:
|
||||||||
Input
|
Output
|
Input
|
Output
|
Input
|
Output
|
|||
1
|
9
|
2
|
25
|
4
|
289
|
|||
Chú ý: Có 60% số test ứng với 60% tổng điểm có N ≤ 13
Bài 2: Mã hóa Caesar. (6 điểm)
Đồng dư có nhiều ứng dụng trong toán học và trong
Tin học, một trong những ứng dụng của phép đồng dư liên quan đến là mật mã học,
một lĩnh vực nghiên cứu các thư tín bí mật. Một trong số những người sử dụng
mật mã được biết sớm nhất là Julius Caesar. Ông đã làm cho các bức thư trở nên
bí mật bằng cách dịch mỗi chữ cái đi ba chữ cái về phía trước trong bảng chữ
cái (và ba chữ cái cuối cùng thành ba chữ cái đầu tiên). Ví dụ, theo sơ đồ đó,
chữ B được chuyển thành chữ E và chữ X được chuyển thành chữ A. Để biểu diễn
quá trình mã hóa của Caesar một cách toán học: Trước hết thay mỗi chữ cái bằng
một số nguyên từ 0 đến 25, dựa vào vị trí của nó trong bảng chữ cái. Ví dụ: A
thay bằng 0, K bằng 10 và Z bằng 25. Phương pháp này
có thể được biểu diễn bởi hàm f,
hàm này gán cho số nguyên không âm p, p ≤ 25, số nguyên f(p) trong tập {0, 1,
2, …, 25} sao cho f(p)=(p+3) mod 26. Như vậy, trong phiên bản mã hóa của bức
thư, chữ cái được biểu diễn bởi p sẽ được thay bằng chữ cái biểu diễn bởi (p +
3) mod 26.
Ví dụ: Chuyển nội dung “DO NOT PASS GO” thành bức
thư bí mật. Thay các chữ cái trong nội dung trên thành số, ta được:
D
|
O
|
N
|
O
|
T
|
P
|
A
|
S
|
S
|
G
|
O
|
|||
3
|
14
|
13
|
14
|
19
|
15
|
0
|
18
|
18
|
6
|
14
|
Bây giờ,
thay các số p đó bằng f(p) = (p + 3) mod 26 ta được:
D
|
O
|
N
|
O
|
T
|
P
|
A
|
S
|
S
|
G
|
O
|
|||
3
|
14
|
13
|
14
|
19
|
15
|
0
|
18
|
18
|
6
|
14
|
|||
6
|
17
|
16
|
17
|
22
|
18
|
3
|
21
|
21
|
9
|
17
|
|||
Dịch
ngược trở lại các chữ cái, ta được nội dung đã mã hóa:
|
|||||||||||||
D
|
O
|
N
|
O
|
T
|
P
|
A
|
S
|
S
|
G
|
O
|
|||
3
|
14
|
13
|
14
|
19
|
15
|
0
|
18
|
18
|
6
|
14
|
|||
6
|
17
|
16
|
17
|
22
|
18
|
3
|
21
|
21
|
9
|
17
|
|||
G
|
R
|
Q
|
R
|
W
|
S
|
D
|
V
|
V
|
J
|
R
|
|||
Tuy nhiên, trong thực tế, mã hóa
Caesar không có độ an toàn cao, có nhiều cách để nâng cao độ an toàn của phương
pháp này. Một trong những phương pháp đó là dùng hàm có dạng f(p) = (ap+k) mod
26, trong đó, a và k nguyên.
Yêu cầu: Dùng mã hóa Caesar để
mã hóa nội dung bức thư chỉ gồm dấu cách và các chữ cái in hoa thành bức thư có nội dung bí mật.
Dữ liệu vào: Dòng đầu ghi hai số a (1 ≤ a ≤ 1000000) và k (1 ≤ k ≤ 1000000), dòng hai ghi một xâu chỉ bao gồm các chữ cái và dấu cách là nội
dung bức thư cần mã hóa.
Dữ liệu ra: Một dòng duy nhất chứa nội dung
đã được mã hóa.
Ví dụ:
Input
|
Output
|
1 3
|
GR QRW SDVV JR
|
DO NOT PASS
GO
|
Câu 2: (3,5 điểm)
Giải nén UNZIP.PAS
Để tiết
kiệm chi phí trong việc gửi và nhận dữ liệu thông qua các kênh truyền,
các file văn bản trước khi được gửi đi đều được nén lại để giảm dung
lượng bộ nhớ. Sau khi nhận được các file văn bản gửi đến, muốn đọc được nội
dung thì các file vừa nhận phải được giải nén.
Việc nén một xâu văn bản chỉ chứa
các kí tự chữ cái in hoa được thực hiện như sau: Một đoạn liên tiếp các kí tự
chữ cái giống nhau được thay bằng một đoạn kí tự mới gồm các kí tự chữ số thể
hiện số lượng của chữ cái và tiếp theo sau là kí tự chữ cái đó (AAAAAAA được
thay bằng 7A), nếu chỉ có một kí tự chữ cái thì giữ nguyên kí tự đó. Ví dụ:
AAAAAABBBCDDD sẽ được nén lại là 6A3BC3D.
Việc giải nén là chuyển một xâu đã
được nén trở về xâu gốc ban đầu trước khi nó được nén. Ví dụ: 6A3BC3D được
chuyển thành AAAAAABBBCDDD.
Cho một file văn bản gồm nhiều dòng,
mỗi dòng chứa một xâu văn bản đã được nén, file chỉ chứa tối đa 100 dòng (Mỗi
xâu văn bản gốc trước khi nén có tối đa
255 kí tự).
Yêu cầu: Hãy thực hiện giải nén các xâu văn bản
trên mỗi dòng trong file đã cho chuyển thành các xâu gốc ban đầu.
Dữ liệu vào: Ghi trong file
văn bản UNZIP.INP có cấu trúc như sau:
- Dòng 1: Ghi số nguyên dương N là số lượng xâu
trong file văn bản.
- Dòng thứ i trong N dòng tiếp theo: Mỗi dòng
ghi một xâu đã được nén.
Dữ liệu
ra: Ghi ra file văn bản UNZIP.OUT theo cấu trúc như
sau:
Dữ liệu được ghi trên N dòng, dòng thứ i ghi xâu đã
được giải nén tương ứng với xâu đã được nén trong file dữ liệu vào.
Ví dụ:
UNZIP.INP
|
UNZIP.OUT
|
||
2
|
AAAAAABBBCDDD
|
||
6A3BC3D
|
AAAAABC
|
||
5ABC
|
Bài liên quan
Comments[ 0 ]
Đăng nhận xét