De+Dan de nghi olp 09 - lop 10

Trường THPT Chuyên Nguyễn Du-Bmt
Đề thi đề nghị OLP 2009-Môn Tin học -Lớp 10.
Bài 1: Bạn An thực hiện 1 mã hóa đơn giản như sau: Đổi toàn bộ chuỗi thành chữ in hoa, sau đó với mỗi ký tự trong chuỗi, mã hóa thành ký tự kế tiếp nó trong bảng chữ cái La tinh, trường hợp nếu ký tự là Z thì mã hóa nó thành A, một lượt áp dụng phép mã hóa trên tất cả các ký tự của chuỗi sẽ cho ta 1 chuỗi mới, việc mã hóa được làm liên tiếp K lượt. Với K khá lớn An nghĩ là từ chuỗi kết quả khó tìm lại được chuỗi ban đầu và cố gắng nghĩ cách viết 1 chương trình giải mã để tìm lại chuỗi ban đầu.
Yêu cầu: Cho biết số K và chuỗi kết quả mã hóa, hãy giúp Bạn An tìm lại chuỗi ban đầu.
Dữ liệu vào: File CH.IN có dòng đầu là số K, 0Kết quả ra: File CH.OUT gồm 1 dòng ghi chuỗi ban đầu.
Ví dụ:
CH.IN

CH.OUT

100000000000000000
XMRL XLER ZYSX OLS


TINH THAN VUOT KHO




Bài 2:Cho 2 dãy số: A có n phần tử, B có m phần tử, các phần tử là các số nguyên x
Tính số lượng giá trị trong A mà có mặt trong B.
Yêu cầu : viết ra số lượng tìm được.
Dữ liệu vào: File AB.IN có dòng đầu là 2 số n,m
Từ dòng thứ 2 lần lượt là các số của A sau đó là các số của B.
0Kết quả ra: File AB.OUT gồm 1 dòng ghi số lượng tìm được.
Ví dụ:
AB.IN

AB.OUT

3 4
2 5 6 7 5 5 6

2


Bài 3: Cho n địa điểm đánh số từ 1 đến n, người ta chọn ra 1 địa điểm X để lập trường học, .Để tạo điều kiện cho học sinh đi học,người ta tiến hành rải nhựa 1 số tuyến đường sao cho đảm bảo các học sinh đều đi đến trường bằng con đường ngắn nhất và đều đi trên đường nhựa và tổng số độ dài các quãng đường phải rải nhựa là nhỏ nhất.Yêu cầu hãy tính ra m tổng số độ dài các quãng đường phải rải nhựa
Dữ liệu vào: file DD.IN có dòng đầu là n,X, 0Kết quả ra: file DD.OUT gồm 1 số m .
Ví dụ:
DD.IN

DD.OUT

4 2
2 1 15
2 3 8
2 4 20
3 4 6

29




Đáp án và hướng dẫn chấm:
Mỗi bài có 5 test, mỗi test 2 điểm.
Bài 1:(10 điểm) có 2 test với k thuộc longint, 3 test với k lớn. nhièu chữ số
Bài 2:(10 điểm) có 2 test với m,n<1000, 3 test với m,n lớn dến giới hạn gần 10^6.
Bài 3:(10 điểm) có 2 test với n<100, 3 test với m,n lớn dến 500..

Lời giải :
Bài 1:
GT: tính chu kỳ T = số ít nhất lần biến đổi để có lại chuỗi ban đầu (tất cả các ký tự đều cho lại ký tự ban đầu), tính m=k mod T (chia số lớn cho 1 số nhỏ),thực hiện biến dổi tiếp t-m lần nữa ta có lại chuỗi ban đầu.
{ma hoa thanh ky tu ke tiep,cho so lan ma hoa tim laichuoi ban dau}
const
fin=`CH.IN`;
fout=`CH.OUT`;
var s,k:string;
f:text;
n,i:byte;
procedure nhap;
begin
assign(f,fin);reset(f);
readln(f,k);readln(f,s);
for i:=1 to length(s) do s[i]:=upcase(s[i]);
close(f);

end;
procedure vietkq;
begin
assign(f,fout);rewrite(f);
writeln(f,s);
close(f);

end;
function mmod(k:string;p:byte):integer;
var so:integer;s1