Kỳ thi học sinh giỏi tỉnh năm học 2007-2008 môn : tin học 12 - thpt (180 phút, không kể thời gian giao đề)

SỞ GIÁO DỤC & ĐÀO TẠO KỲ THI HỌC SINH GIỎI TỈNH NĂM HỌC 2007-2008
 ĐẮK LẮK	 MÔN : TIN HỌC 12 - THPT	
ĐỀ CHÍNH THỨC
	(180 phút, không kể thời gian giao đề)	
Ghi chú : Đề thi này gồm 2 trang.
BÀI 1: ( 6 điểm) - Mật mã
 Trong ngôn ngữ mật mã, Ciphertex dùng để chỉ một thông điệp đã mã hóa với một Key riêng biệt, Plaintext dùng để chỉ văn bản gốc cũng có nghĩa là văn bản đã được giải mã. Trong bài toán này Ciphertex và Key là những xâu ký tự gồm chỉ các ký tự in hoa, có thể có cả dấu cách. Ciphertext được tạo ra bằng cách ‘cộng’ tương ứng các ký tự của Plaintext với các ký tự trong Key với nhau. Nếu như Plaintext ngắn hơn Key thì chỉ một phần của Key được sử dụng. Một cách tương tự nếu Plaintext dài hơn Key thì Key sẽ được sử dụng nhiều lần.
Ví dụ : Mã hóa xâu gốc ‘HELLO’ với khóa (key) là ‘CAT’
 Xâu gốc : HELLO , Khóa sử dụng: CATCA
	 Xâu đã được mã hóa: KFFOP
Để cộng hai ký tự với nhau, sử dụng quy tắc sau: A=1, B=2, ..., Z=26. Nếu tổng của hai ký tự lớn hơn 26, hãy lấy tổng trừ đi 26. Ví dụ : A + E = 1+5 = 6 = F, và D + X = 4+24 = 28 = 2 = B.
Cho trước một cặp xâu ký tự đã được mã hóa và khóa. Bạn hãy viết chương trình xác định xâu gốc.
Dữ liệu vào : File văn bản Matma.inp chứa hai dòng, dòng đầu tiên chứa xâu đã được mã hóa, dòng thứ hai chứa khóa. Cả hai chỉ gồm các ký tự in hoa (có thể có dấu cách).
Dữ liệu ra: File văn bản Matma.out chứa xâu gốc.
Ví dụ 1:
MATMA.INP
MATMA.OUT
KFFOP
CAT
HELLO
Ví dụ 2:
MATMA.INP
MATMA.OUT
DJCP DCO
ABBA
CHAO BAN
BÀI 2: ( 7 điểm) - Bảng đèn quảng cáo
Trên quảng trường thành phố 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ắt, đang tắt thành sáng). Với trạng thái bảng quảng cáo cho trước, bạn hãy lập trình tìm một phương án tác động lên các công tắc để bảng quảng cáo có được nhiều bóng đèn sáng nhất.
Dữ liệu vào : File QUANGCAO.INP, trong đó:
Dòng đầu tiên 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 số 1 ( 1: chỉ bóng đèn sáng, 0: chỉ bóng đèn tắt)
Các số trên một dòng được ghi cách nhau ít nhất một dấu cách và không cần kiểm tra dữ liệu.
Dữ liệu ra: File QUANGCAO.OUT . Trong đó: Dòng đầu là tổng số bóng đèn sáng trên bảng, 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ứ i 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 lên 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 4	16
	1 0 0 1	4
	0 1 1 0	C1
	0 1 1 0	C4
	1 0 0 1	D1
	D4
BÀI 3: ( 7 điểm) – Robot gặp nhau.
Trên một lưới ô vuông kích thước M x N (M dòng, N cột, £ 100), người ta đặt hai robot A và B. Robot A được đặt ở góc trên bên trái, còn robot B đươc đặt ở góc dưới bên phải. Mỗi ô của lưới có thể có một vật cản hoặc không. Tại mỗi bước, mỗi robot chỉ có thể di chuyển theo các hướng lên, xuống, trái, phải vào các ô kề cạnh không có vật cản. Hai robot gặp nhau khi chúng cùng đứng trong một ô. Hai robot bắt đầu di chuyển đồng thời và mỗi lượt cả hai đều phải thực hiện việc di chuyển ( nghĩa là không cho phép một robot dừng lại một ô nào đó trong khi robot kia thực hiện bước di chuyển). Bài toán đặt ra là tìm số bước di chuyển ít nhất mà hai robot phải thực hiện để có thể gặp nhau. Chú ý rằng tùy trạng thái của lưới, hai robot có thể không khi nào gặp được nhau.	
Dữ liệu vào cho bởi file văn bản ROBOT.INP, cấu trúc như sau:
Dòng đầu tiên chứa hai số M, N.
M dòng tiếp theo, mỗi dòng ghi N số gồm 0 và 1 mô tả trạng thái dòng tương ứng của lưới, trong đó mỗi số mô tả một ô với quy ước: 0 – không có vật cản, 1 – có vật cản. Các số trên cùng một dòng của file dữ liệu được ghi cách nhau ít nhất một dấu cách.
Dữ liệu ra : Ghi lên file văn bản ROBOT.OUT, trong đó:
Nếu hai robot không thể gặp nhau thì ghi một dòng : ‘Hai Robot khong the gap nhau’.
Trái lại ghi hai dòng, mỗi dòng là một dãy các ký tự viết liền nhau mô tả các bước đi của robot: U- lên trên, D- xuống dưới, L- sang trái, R- sang phải. Dòng dầu là các bước đi của robot A và dòng sau là các bước đi của robot B.
Ví dụ: ROBOT.INP	ROBOT.OUT
	4 6	DRRR
	0 1 1 0 0 0	LUUL	
	0 0 0 0 0 1
	0 0 1 0 0 1
	0 1 0 1 0 0	
------- Hết --------
Ghi chú: Giám thị coi thi không giải thích gì thêm.
SỞ GIÁO DỤC & ĐÀO TẠO KỲ THI HỌC SINH GIỎI TỈNH NĂM HỌC 2007-2008
 ĐẮK LẮK	 MÔN : TIN HỌC 12 - THPT	
ĐÁP ÁN VÀ HƯỚNG DẪN CHẤM ĐỀ CHÍNH THỨC
Bài 1. Mật mã (6 điểm)
Thuật toán :
 Ta lấy kí tự tương ứng ở xâu đã mã hóa trừ đi kí tự tương ứng ở xâu khoá(key). Cách trừ là dùng hàm ORD(kt). Gọi dec=ORD(Xaumahoa[i] – ORD(key[i]). Nếu dec0 thì giữ nguyên dec (chú ý dec luôn khác 0). Dec sẽ là độ lệch giữa 2 kí tự xaumahoa[i] và key[i].
Xây dựng mảng một chiều KT, trong đó KT[1] = ‘A’, KT[2] = ‘B’, ...KT[26]=’Z’. KT[dec] sẽ cho kí tự tương ứng trong xâu gốc.
Cần chú ý trường hợp số kí tự của key nhỏ hơn số kí tự của xâu đã mã hóa (Xaumahoa), khi đó cần phải chuẩn hóa lại xâu key theo yêu cầu đề bài.
program matma;
const
 fi = 'matma.inp';
 fo = 'matma.out';
kt: array[1..26] of char = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ';
var
 xaumahoa,xaugoc,key:string;
 l1,l2:integer;
 f:text;
procedure readfile;
begin
 assign(f,fi); reset(f);
 readln(f,xaumahoa);
 readln(f,key);
 close(f);
 assign(f,fo); rewrite(f);
 l1:=length(xaumahoa);
 l2:=length(key);
end;
procedure khoa;
var i,j:integer;
begin
 if l1>l2 then
 begin
 j:=1;
 for i:=l2+1 to l1 do
 begin
 key:=key+key[j];
 inc(j);
 end;
 end;
end;
procedure xuly;
var i,dec :integer;
begin
 khoa;
 xaugoc:='';
 for i:=1 to l1 do
 begin
 dec:=ord(xaumahoa[i]) - ord(key[i]);
 if dec<0 then dec:=dec+26;
 xaugoc:=xaugoc+kt[dec];
 end;
 writeln(f,xaugoc);
 close(f);
end;
BEGIN
 readfile;
 xuly;
END.
Bài 2. Bảng đèn quảng cáo (7 điểm)
Thuật toán :
Duyệt các cách mà ta có thể thay đổi ở các dòng. 
Với mỗi cách thay đổi ở các dòng, tìm cách thay đổi ở các cột để đạt số ô bóng đèn sáng lớn nhất. Nếu trên một cột số ô sáng dc[j] £ (N-1) div 2 thì ta thay đổi trạng thái của tất cả các ô trong cột j. Đếm tổng số ô sáng của cách thay đổi này. nếu nó lớn hơn Max thì ta giữ lại.
PROGRAM BANGDEN;
uses crt;
const
fi='QUANGCAO.INP';
fo='QUANGCAO.OUT';
maxn=10; maxm=100;
var
a : array[1..maxn,1..maxm] of byte;
d,kqd : array[1..maxn] of byte;
c,kqc,dc: array[1..maxm] of byte;
n,m,max,k: integer;
f: text;
procedure init;
var i,j :integer;
begin
 clrscr;
 max:=0;
 assign(f,fi); reset(f);
 readln(f,n,m);
 for i:=1 to n do
 begin
 for j:=1 to m do read(f,a[i,j]);
 readln(f);
 end;
 close(f);
end;
procedure update;
var i,j,dem: integer;
begin
 for j:=1 to m do dc[j]:=0;
 for j:=1 to m do c[j]:=0;
 for i:=1 to n do
 for j:=1 to m do dc[j]:=dc[j]+a[i,j];
 dem:=0;
 for j:=1 to m do
 if dc[j] <= (n-1) div 2 then
 begin
 c[j]:=1;
 dem:=dem+n-dc[j];
 end
 else dem:=dem+dc[j];
 if dem>max then
 begin
 max:=dem;
 kqd:=d;
 kqc:=c;
 end;
end;
procedure try(i:integer);
var j:integer;
begin
 for j:=0 to 1 do
 begin
 d[i]:=j;
 if j=1 then
 for k:=1 to m do a[i,k]:=1-a[i,k];
 if i=n then update else try(i+1);
 if j=1 then
 for k:=1 to m do a[i,k]:=1-a[i,k];
 end;
end;
procedure result;
var s:integer;
begin
 assign(f,fo);
 rewrite(f);
 writeln(f,max);
 s:=0;
 for k:=1 to n do s:=s+kqd[k];
 for k:=1 to m do s:=s+kqc[k];
 writeln(f,s);
 for k:=1 to n do
 if kqd[k]=1 then writeln(f,'D',k);
 for k:=1 to m do
 if kqc[k]=1 then writeln(f,'C',k);
 close(f);
end;
BEGIN
 init;
 try(1);
 result;
END.
Bài 3. Robot gặp nhau (7 điểm)
thuat toan loang de quy
program gapnhau;
{$M 65000,0,655360} {$B-}
uses crt;
type
mang= array[1..100,1..100] of integer;
const
fi= 'robot.inp';
fo='robot.out';
var
m,n: byte;
a: array[1..100,1..100] of 0..1;
b1, b2: mang;
max:integer;
f: text; dk: boolean; ts: longint;
procedure doc;
var i,j: byte;
begin
 clrscr;
 assign(f,fi); reset(f);
 readln(f,m,n);
 for i:=1 to m do
 begin
 for j:=1 to n do read(f,a[j,i]);
 readln(f);
 end;
 close(f);
end;
procedure loang1(i,j:byte; var b1:mang);
begin
 if (i>1) and ((b1[i-1,j]>b1[i,j]+1) or (b1[i-1,j]=0)) and (a[i-1,j]=0)
 then begin
 b1[i-1,j]:=b1[i,j]+1;
 loang1(i-1,j,b1);
 end;
 if (ib1[i,j]+1) or (b1[i+1,j]=0)) and (a[i+1,j]=0) then
 begin
 b1[i+1,j]:=b1[i,j]+1;
 loang1(i+1,j,b1);
 end;
 if (j>1) and ((b1[i,j-1]>b1[i,j]+1) or (b1[i,j-1]=0)) and (a[i,j-1]=0) then
 begin
 b1[i,j-1]:=b1[i,j]+1;
 loang1(i,j-1,b1);
 end;
 if (jb1[i,j]+1) or (b1[i,j+1]=0)) and (a[i,j+1]=0) then
 begin
 b1[i,j+1]:=b1[i,j]+1;
 loang1(i,j+1,b1);
 end;
end;
procedure xdbang;
var i,j:byte;
begin
 fillchar(b1,sizeof(b1),0);
 b1[1,1]:=1; loang1(1,1,b1);
 fillchar(b2,sizeof(b2),0);
 b2[n,m]:=1; loang1(n,m,b2);
end;
procedure goi(gi,gj:byte;var b:mang);
var i,k:integer;
 d:array[1..2000] of char;
begin
 k:=0;
 for i:=max-1 downto 1 do
 begin
 if b[gi-1,gj]=i then
 begin
 dec(gi); inc(k); d[k]:='R';
 end
 else if b[gi,gj-1] = i then
 begin
 dec(gj); inc(k); d[k]:='D';
 end else if b[gi+1,gj]=i then
 begin
 inc(gi);inc(k);d[k]:='L';
 end
 else if b[gi,gj+1]=i then
 begin
 inc(gj);inc(k);d[k]:='U';
 end;
 end;
 for i:=k downto 1 do write(f,d[i]);
end;
procedure xuly;
var i,j,gi,gj: byte;
begin
 max:=maxint;
 for i:=1 to n do
 for j:=1 to m do
 if (b1[i,j]= b2[i,j]) and (b1[i,j]0) then
 begin
 if max>b1[i,j] then
 begin
 max:=b1[i,j] ; gi:=i; gj:=j;
 end;
 end;
 assign(f,fo); rewrite(f);
 if maxmaxint then
 begin
 i:=gi; j:=gj;
 goi(gi,gj,b1);
 writeln(f);
 goi(i,j,b2);
 end else write(f,'Hai robot khong the gap nhau');
 close(f);
end;
BEGIN
 doc; xdbang; xuly;
END.
-----------------------------------------------------------------------------
HƯỚNG DẪN CHẤM :
Chạy chương trình với các bộ dữ liệu ( bộ test). Ra được kết quả đúng, cho điểm trên mỗi test.
Bài 1.(6 đ) 
TEST 1(3 đ)
MATMA.INP
MATMA.OUT
KFFOP
CAT
HELLO
TEST 2:(3 đ)	
MATMA.INP
MATMA.OUT
DJCP DCO
ABBA
CHAO BAN
Bài 2.(7 đ) ( Có thể kết quả trên file * .out của thí sinh có khác với đáp án. Giám khảo cần xem xét khả năng thực tế của phương án tìm được để cho điểm )
TEST 1:(3 đ)
QUANGCAO.INP QUANGCAO.OUT
 4 4	16
	1 0 0 1	4
	0 1 1 0	D2
	0 1 1 0	D3
	1 0 0 1	C2
	C3
TEST 2:(4 đ)
QUANGCAO.INP QUANGCAO.OUT
 4 4	14
	1 0 0 1	4
	0 1 1 0	D2
	0 1 1 1	D3
	1 0 1 1	C2
	C3
Bài 3 :(7 đ)
TEST 1:(1 đ)
 ROBOT.INP	ROBOT.OUT
	4 6	DRRR
	0 1 1 0 0 0	LUUL	
	0 0 0 0 0 1
	0 0 1 0 0 1
	0 1 0 1 0 0	
TEST 2:(1 đ)	
 ROBOT.INP	ROBOT.OUT
	4 6	HAI ROBOT KHONG THE GAP NHAU
	0 1 1 0 0 0	
	0 0 0 0 0 1
	0 0 1 0 0 1
	0 1 0 1 1 0	
TEST 3:(2 đ) ROBOT.INP	ROBOT.OUT
	4 6	DRRRU
	0 1 1 0 0 0	UUULL	
	0 0 0 0 1 0
	0 0 1 0 1 0
	0 1 0 1 1 0	
TEST 4:(3 đ) ROBOT.INP	ROBOT.OUT
	5 6	HAI ROBOT KHONG THE GAP NHAU
	0 1 1 0 0 0	
	0 0 0 0 1 0
	0 0 1 0 1 0
	1 0 1 0 0 0
	0 1 0 1 1 0