Tài liệu Các thuật toán

bản ENCODE.INP gồm nhiều dòng, mỗi dòng chứa một từ. Tương ứng với mỗi từ W trên một dòng, hãy mã hoá và ghi vào file văn bản ENCODE.OUT hai dòng là mã công khai của từ đó: dòng 1 ghi từ W', dòng 2 ghi số k.
Yêu cầu 2: 
Viết một chương trình khác đọc file văn bản DECODE.INP gồm nhiều cặp dòng: Cứ hai dòng liên tiếp chứa một mã công khai: dòng 1 chứa từ W' và dòng 2 ghi số k. Tương ứng với mỗi cặp dòng đó, hãy giải mã và ghi vào file văn bản DECODE.OUT một dòng chứa từ W là từ đã giải mã ra được.
Hai yêu cầu trên phải được thực hiện độc lập trên hai file chương trình khác nhau. 
Ràng buộc dữ liệu: Các từ được cho luôn khác rỗng, chỉ gồm các chữ cái in thường và có độ dài không quá 10000.
Ví dụ:
ENCODE.INP
ENCODE.OUT
DECODE.INP
DECODE.OUT
qua
gi
ma
to
to
nhat
uaq
2
ig
1
ma
2
to
2
to
2
hnta
3
xin
3
utah
3
rnag
4
uaq
2
dta
2
xin
thua
rang
qua
dat
091. BAO LỒI
Trên mặt phẳng với hệ toạ độ Decattes vuông góc, cho n điểm không đồng thời thẳng hàng. Điểm thứ i có toạ độ là (xi, yi). 
(Số n và các toạ độ xi, yi đều là số nguyên: 3 £ n £ 1000; -300 £ xi £ 300;-200 £ yi £ 200).
Hãy tìm một đa giác lồi có diện tích nhỏ nhất mà miền đóng giới hạn bởi biên đa giác chứa tất cả những điểm đã cho.
Dữ liệu: Vào từ file văn bản BOUND.INP
Dòng 1: Chứa số n
n dòng tiếp theo, dòng thứ i ghi hai số xi, yi
Kết quả: Ghi ra file văn bản BOUND.OUT
Dòng 1: Ghi số m là số đỉnh của đa giác
m dòng tiếp theo, mỗi dòng ghi hai số nguyên theo thứ tự là hoành độ và tung độ của một đỉnh đa giác. Các đỉnh của đa giác không được phép có ba điểm thẳng hàng và chúng phải được liệt kê theo đúng thứ tự lập thành đa giác.
Vẽ hình mô tả kết quả tìm được trên màn hình đồ hoạ.
Các số trên một dòng của Input / Output file ghi cách nhau ít nhất một dấu cách
Ví dụ:
BOUND.INP
BOUND.OUT
10
0 -1
1 0
1 -3
2 4
3 -3
4 1
4 2
5 -1
6 -2
7 -1
6
1 -3
3 -3
6 -2
7 -1
2 4
0 -1
092. GIAI THỪA
Giai thừa của một số tự nhiên k, ký hiệu k! được định nghĩa quy nạp như sau:
0! = 1
k! = (k - 1)!.k ("k ³ 1)
Vấn đề đặt ra là cho trước hai số tự nhiên m, n. (1 £ m £ n£ 106). Hãy tìm hai số tự nhiên a và b để với mọi số tự nhiên k ( [a, b] thì k! có không ít hơn m chữ số và không nhiều hơn n chữ số. Những số tự nhiên khác nằm ngoài đoạn [a, b] không có tính chất này.
Dữ liệu: Vào từ file văn bản FDIGIT.INP gồm một dòng chứa hai số m, n cách nhau một dấu cách.
Kết quả: Ghi ra file văn bản FDIGIT.OUT gồm một dòng ghi hai số a, b cách nhau một dấu cách. Trong trường hợp không có số k nào thoả mãn yêu cầu đề ra thì ghi hai giá trị bất kỳ a > b.
Ví dụ:
FDIGIT.INP
FDIGIT.OUT
FDIGIT.INP
FDIGIT.OUT
FDIGIT.INP
FDIGIT.OUT
2 4
4 7
12 12
15 14
3 9
5 12
093. PHỦ SÓNG
Dự kiến xây dựng mạng lưới phát thanh, truyền hình ở một địa phương nọ có một đài phát và n trạm tiếp sóng đánh số từ 1 tới n (n £ 1000). Trạm thứ i đã được xây dựng ở toạ độ (xi, yi). (Các toạ độ là số thực, -10000 £ xi, yi £ 10000). Để đảm bảo tính trung thực của các nguồn tin, các trạm tiếp sóng chỉ có thể nhận tín hiệu trực tiếp từ đài phát. Và như vậy có nghĩa là để phát sóng đến tất cả các trạm thu, bán kính phủ sóng của đài phát phải đủ lớn để phủ hết các trạm tiếp sóng. (Giả sử vùng phủ sóng là hình tròn có tâm là đài phát).
Yêu cầu: 
Hãy tìm vị trí đặt đài phát sao cho khoảng cách từ trạm xa nhất tới đài phát là ngắn nhất. Cho biết bán kính phủ sóng trong phương án tìm được tối thiểu phải là bao nhiêu.
Dữ liệu: Vào từ file văn bản TELECOM.INP
Dòng 1: Chứa số n
n dòng tiếp theo, dòng thứ i chứa hai số xi, yi cách nhau ít nhất một dấu cách.
Kết quả: Ghi ra file văn bản TELECOM.OUT
Ghi ba số thực x, y, r. Ở đây (x, y) là toạ độ đặt đài phát và r là bán kính phủ sóng của đài phát (Đài phát có thể đặt trùng toạ độ với một trạm thu nào đó). Các số thực này phải được lấy tới 6 chữ số sau dấu chấm thập phân và phải ghi cách nhau ít nhất một dấu cách hoặc dấu xuống dòng
Ví dụ
TELECOM.INP
TELECOM.OUT
8
0 0
200 300
200 0
200 200
0 200
100 300
300 100
100 0
121.428571 135.714286
182.107840
094. DÃY NGHỊCH THẾ
Cho x = (x1, x2, ..., xn) là một hoán vị của dãy số (1, 2, ..., n).
Dãy t = (t1, t2, ..., tn) được gọi là dãy nghịch thế của dãy hoán vị x nếu nó được xây dựng như sau:
ti := số phần tử đứng trước giá trị i mà lớn hơn i trong dãy x. (1 £ i £ n).
Ví dụ: Với n = 6
Dãy x = (3, 2, 1, 6, 4, 5) thì dãy nghịch thế của nó là (2, 1, 0, 1, 1, 0)
Dãy x = (1, 2, 3, 4, 5, 6) thì dãy nghịch thế của nó là (0, 0, 0, 0, 0, 0)
Dãy x = (6, 5, 4, 3, 2, 1) thì dãy nghịch thế của nó là (5, 4, 3, 2, 1, 0)
Vấn đề đặt ra là cho trước dãy t, hãy cho biết dãy hoán vị x nhận t làm dãy nghịch thế của nó.
Dữ liệu: Vào từ file văn bản RECOVER.INP
Dòng 1: Chứa số nguyên dương n (n £ 5000).
Dòng 2: Chứa các số t1, t2, ..., tn theo đúng thứ tự đó cách nhau ít nhất một dấu cách.
Kết quả: Ghi ra file văn bản RECOVER.OUT
Chỉ gồm một dòng ghi các số x1, x2, ..., xn cách nhau ít nhất một dấu cách theo đúng thứ tự đó.
Dữ liệu vào được cho luôn luôn đúng đắn để có thể tìm ra nghiệm
Ví dụ:
RECOVER.INP
RECOVER.OUT
6
2 1 0 1 1 0
3 2 1 6 4 5
095. MUA HÀNG
Một công ty muốn mua m máy tính. Sau khi lấy thông tin tại n cửa hàng (1 £ n £ 10000), người ta biết được rằng cửa hàng thứ i có bán ai máy tính và với giá mỗi máy tính là bi. (ai, bi là những số nguyên dương: ai £ 100; bi £ 2000).
Giả sử rằng các cửa hàng có đủ máy để bán cho công ty. Hãy tìm cách mua rẻ nhất.
Dữ liệu: Vào từ file văn bản BUY.INP
Dòng 1: Chứa hai số m, n cách nhau ít nhất một dấu cách.
n dòng tiếp theo, dòng thứ i chứa hai số ai, bi cách nhau ít nhất một dấu cách.
Kết quả: Ghi ra file văn bản BUY.OUT
Dòng 1: Ghi tổng số tiền phải trả.
n dòng tiếp theo, dòng thứ i ghi số máy tính mua ở cửa hàng thứ i.
Ví dụ:
BUY.INP
BUY.OUT
22 5
3 30
5 10
6 8
10 5
2 20
168
0
5
6
10
1
096. XÂU CON CHUNG DÀI NHẤT
Xâu ký tự X được gọi là xâu con của xâu ký tự Y nếu ta có thể xoá đi một số ký tự trong xâu Y để được xâu X.
Cho biết hai xâu ký tự A và B, hãy tìm xâu ký tự C có độ dài lớn nhất và là con của cả A và B.
Dữ liệu: Vào từ file văn bản STR.INP
Dòng 1: chứa xâu A
Dòng 2: chứa xâu B
Kết quả: Ghi ra file văn bản STR.OUT
Chỉ gồm một dòng ghi xâu C tìm được
Ví dụ:
STR.INP
STR.OUT
abc1def2ghi3
abcdefghi123
abcdefghi3
097. DÃY CON NGẮN NHẤT
Cho số nguyên dương n £ 1000 và n số tự nhiên a1, a2, ..., an. ("i: ai £ 10000).
Yêu cầu:
Cho số nguyên dương m £ 10000, hãy cho biết một dãy con của dãy a có tổng bằng m chứa ít phần tử nhất.
Dữ liệu: Vào từ file văn bản SUBSEQ.INP
Dòng 1: Chứa hai số n, m
Dòng 2: Chứa n số a1, a2, ..., an theo đúng thứ tự đó.
Kết quả: Ghi ra file văn bản SUBSEQ.OUT
Dòng 1: Ghi số k là số phần tử của dãy con chọn ra được, nếu không tồn tại dãy con có tổng bằng m thì ghi số -1.
Nếu có phương án chọn dãy con, thì dòng 2 ghi chỉ số của k phần tử được chọn (ghi theo thứ tự tuỳ thích).
Các số trên một dòng của Input/Output file được ghi cách nhau ít nhất một dấu cách.
Ví dụ:
SUBSEQ.INP
SUBSEQ.OUT
10 220
10 30 50 70 90 20 40 60 80 100
3
8 5 4 
098. BIẾN ĐỔI DÃY SỐ
Cho dãy số nguyên dương a = (a1, a2, ..., an) (1 £ n £ 100; với "i: 1 £ ai £ 100). Xét hai loại phép biến đổi:
Phép biến đổi +i: Tăng ai lên 1 đơn vị
Phép biến đổi -i: Giảm ai đi 1 đơn vị.
Yêu cầu:
Hãy tìm một cách sử dụng ít phép biến đổi nhất để biến dãy a trở thành dãy thoả mãn:
1 £ a1 < a2 < ... < an £ 100
Dữ liệu: Vào từ file văn bản SEQ.INP
Dòng 1: Chứa số n
Dòng 2: Chứa n số a1, a2, ..., an theo đúng thứ tự đó cách nhau ít nhất một dấu cách.
Kết quả: Ghi ra file văn bản SEQ.OUT
Dòng 1: Ghi số m là số phép biến đổi tìm được
m dòng tiếp theo, mỗi dòng ghi một phép biến đổi
Ví dụ:
SEQ.INP
SEQ.OUT
SEQ.INP
SEQ.OUT
5
4 1 6 7 4
8
+5
+5
+5
+5
+2
-1
-1
-1
4
98 99 100 96
7
+4
+4
+4
+4
-3
-2
-1
099. GIÁ TRỊ NHỎ NHẤT
Một số nguyên dương x gọi là con của số nguyên dương y nếu ta có thể xoá bớt một số chữ số của y để được x.
Cho hai số nguyên dương a và b hãy tìm số c nhận cả a và b là con, sao cho giá trị của c là lớn nhất có thể.
Ràng buộc: 1 £ a, b £ 10100; 
Dữ liệu: Vào từ file văn bản NUMBER.INP
Dòng thứ nhất chứa số a
Dòng thứ hai chứa số b
Kết quả: Ghi ra file văn bản NUMBER.OUT
Ghi ra trên một dòng số c.
Ví dụ:
NUMBER.INP
NUMBER.OUT
NUMBER.INP
NUMBER.OUT
111999111
999111999
111999111999
567812345678
123456781234
1234567812345678
100. NỐI DÂY
Cho hai đường thẳng song song nằm ngang d1 và d2. Trên mỗi đường thẳng, người ta chọn lấy n điểm phân biệt và gán cho mỗi điểm một số nguyên dương là nhãn của điểm đó:
Trên đường thẳng d1, điểm thứ i (theo thứ tự từ trái qua phải) được gán nhãn là ai.
Trên đường thẳng d2, điểm thứ j (theo thứ tự từ trái qua phải) được gán nhãn là bj.
Ở đây (a1, a2, ..., an) và (b1, b2, ..., bn) là những hoán vị của dãy số (1, 2, ..., n)
Yêu cầu: Hãy chỉ ra một số tối đa các đoạn thẳng thoả mãn:
Mỗi đoạn thẳng phải nối hai điểm có cùng một nhãn: một điểm trên đường thẳng d1 và một điểm trên đường thẳng d2.
Các đoạn thẳng đôi một không có điểm chung
Dữ liệu: Vào từ file văn bản LINES.INP
Dòng 1: Chứa số nguyên dương n £ 5000
Dòng 2: Chứa n số của dãy hoán vị a1, a2, ..., an.
Dòng 3: Chứa n số của dãy hoán vị b1, b2, ..., bn.
Kết quả: Ghi ra file văn bản LINES.OUT
Dòng 1: Ghi số k là số đoạn thẳng nối được.
Dòng 2: Ghi k nhãn của các đoạn thẳng được chọn (nhãn của mỗi đoạn thẳng là nhãn của điểm đầu mút)
Các số trên một dòng của Input / Output file ghi cách nhau ít nhất một dấu cách.
Ví dụ:
LINES.INP
LINES.OUT
LINES.INP
LINES.OUT
6
2 3 1 5 6 4
3 2 5 6 1 4
4
4 6 5 3 
7
1 2 3 4 5 6 7
1 2 6 7 3 4 5
5
1 2 3 4 5
Cách cho điểm: Chấm theo 10 Test, điểm tối đa cho mỗi Test là 1.
Đối với mỗi một Test:
Nếu chương trình chạy gặp lỗi, hoặc ghi sai khuôn dạng Output, hoặc cho phương án nối dây không hợp lệ (có hai đoạn thẳng cắt nhau), hoặc chạy quá 10 giây: 0 điểm.
Nếu không, điểm cho test đó sẽ là: (Số dây nối tìm được / số dây nối của đáp án)2.