Kỳ thi chọn học sinh giỏi lớp 12 Quảng Bình năm học 2006 - 2007 đề chính thức - Môn: Tin học (vòng 2)

sở giáo dục - đào tạo kỳ thi chọn học sinh giỏi lớp 12 Quảng bình năm học 2006-2007 Đề chính thức - môn : tin học (vòng 2) SBD: Thời gian làm bài: 180 phút. Đề ra Câu 1: (3,0 điểm) Chia bánh (tên file bài làm CAKE.PAS) Trong buổi tối trung thu có một cái bánh hình tròn. Bánh được viền quanh bởi N quả dâu và quả sim. Yêu cầu: Tìm cách cắt bánh bằng một nhát dao để được hai phần sao cho số lượng quả dâu ở phần này bằng số lượng quả dâu ở phần kia và số lượng quả sim ở phần này bằng số lượng quả sim ở phần kia. Dữ liệu vào: Cho trong file CAKE.INP có cấu trúc như sau: Dòng 1: Ghi số nguyên dương N là số lượng quả dâu và quả sim ở trên viền bánh (1 N 255). Dòng 2: Ghi dãy gồm N ký tự “D” hoặc “S” ghi liền nhau. Các vị trí gắn quả trên bánh được đánh số từ 1 đến N theo chiều kim đồng hồ bắt đầu từ một vị trí tuỳ ý. Dữ liệu ra: Ghi ra file CAKE.OUT theo cấu trúc như sau: Dòng 1: Nếu tìm được cách chia thì ghi hai số nguyên dương a, b (ab) cho biết các quả ở vị trí a, a+1, ..., b là các quả thuộc cùng một trong hai phần bánh. Nếu không tìm được cách chia thì ghi số 0. Ví dụ: CAKE.INP CAKE.OUT CAKE.INP CAKE.OUT 6 DSSSDS 3 5 5 DSDDS 0 Câu 2: (3,5 điểm) Mã hoá xâu nhị phân (tên file bài làm BINCODE.PAS) Người ta mã hoá một xâu nhị phân gồm các ký tự 0 và 1 như sau : Với một xâu nhị phân S, mã hoá của nó là một mảng T chứa các số nguyên không âm sao cho T[1] bằng 0 hoặc bằng 1 tuỳ theo ký tự đầu tiên của S là 0 hay 1. Nếu T[1]=0 thì tính từ trái sang phải của xâu S, lần lượt T[2] bằng số ký tự 0 liên tiếp, T[3] bằng số ký tự 1 liên tiếp, T[4] bằng số ký tự 0 liên tiếp... cho đến hết xâu S. Yêu cầu: Cho một xâu nhị phân S, hãy xác định mảng T theo cách mã hoá trên. Dữ liệu vào: Cho trong file văn bản BINCODE.INP, có cấu trúc như sau: Dòng 1: Ghi số N là số lượng xâu nhị phân cần mã hoá (1 N 100). N dòng tiếp theo: Mỗi dòng ghi một xâu nhị phân S (1 length(S) 100). Dữ liệu ra: Ghi ra file văn bản BINCODE.OUT, theo cấu trúc như sau: N dòng: Mỗi dòng ghi mảng T là kết quả mã hoá của xâu nhị phân tương ứng. Các số trên cùng một dòng được ghi cách nhau một dấu cách. Ví dụ: BINCODE.INP BINCODE.OUT 2 0001111100111 10001111100111 0 3 5 2 3 1 1 3 5 2 3 Câu 3: (3,5 điểm) Hình chữ nhật (tên file bài làm: HCN.PAS) Cho N hình chữ nhật trên mặt phẳng toạ độ sao cho các cạnh song song với các trục toạ độ. Các hình chữ nhật được đánh số từ 1..N. Hình chữ nhật i được gọi là bao hình chữ nhật j nếu cả bốn đỉnh của hình chữ nhật j đều nằm trong hoặc nằm trên các cạnh của hình chữ nhật i. Yêu cầu: Tìm dãy các hình chữ nhật bao nhau sao cho số lượng các hình bao nhau lớn nhất. Dữ liệu vào: Cho trong file văn bản HCN.INP, có cấu trúc như sau: Dòng 1: Ghi số nguyên N, là số lượng hình chữ nhật (1 N 1000). N dòng tiếp theo: Mỗi dòng ghi bốn số nguyên x1, y1, x2, y2 lần lượt là hoành độ, tung độ của các đỉnh trái trên, phải dưới của một hình chữ nhật (-10000 < x1 , y1, x2, y2 < 10000) Dữ liệu ra: Ghi ra file văn bản HCN.OUT, theo cấu trúc như sau : Dòng 1: Ghi số nguyên k là số lượng các hình chữ nhật bao nhau lớn nhất tìm được. Ví dụ: HCN.INP HCN.OUT 6 1 5 2 2 2 4 3 3 1 5 5 2 4 3 8 1 5 6 8 4 6 6 8 5 2 Hết Hướng dẫn chấm đề thi chính thức học sinh giỏi lớp 12 - vòng 2 năm học 2006-2007 I/ Phương pháp chung - Giám khảo tạo các bộ dữ liệu vào, tính toán kết quả. Chạy chương trình của học sinh và so sánh kết quả. - Giám khảo có thể sử dụng chương trình gợi ý để tính kết quả của dữ liệu vào: CAKE.PAS BINCODE.PAS HCN.PAS - Chương trình học sinh chạy đúng mỗi bộ test, giám khảo cho 0,5 điểm. Như vậy, nếu câu hỏi có 3,0 điểm thì giám khảo phải tạo được 6 bộ test. - Nếu chương trình chạy sai test nào thì giám khảo cho 0 điểm đối với test đó. - Bài toán có thể có nhiều kết quả đúng, nếu kết quả của học sinh khác với đáp án nhưng vẫn đúng thì giám khảo vẫn cho điểm tối đa. II/ Chương trình gợi ý: Câu 1: CAKE.PAS {$r+} Const fi='Cake.INP'; fo='Cake.OUT'; Var A:String; N:Byte; f:Text; Procedure Read_file; Begin Assign(f,fi); Reset(f); Readln(f,n); Read(f,A); Close(f); End; Procedure Xuli; Var i,sd,d,j,n1:Byte; st:String; Begin If n mod 2 = 1 then Begin Writeln(f,0); Close(f); Halt; End; d:=0; For i:=1 to n do If A[i]='D' then Inc(d); If d mod 2 = 1 then Begin Writeln(f,0); Close(f); Halt; End; n1:=n div 2; For i:=1 to n1 do Begin sd:=0; st:=copy(a,i,n1); For j:=1 to n1 do If st[j]='D' then Inc(sd); If sd=(d div 2) then Begin Write(f,i,' ',i+n1-1); Close(f); Halt; End; End; End; Begin Read_file; Assign(f,fo); Rewrite(f); Xuli; Close(f); End. Câu 2 : BINCODE.PAS program bincode; const fi='bincode.inp'; fo='bincode.out'; type mmcs=array[1..100] of string; var f:text; a:mmcs; n:word; procedure doc; var i:word; begin assign(f,fi); reset(f); readln(f,n); for i:=1 to n do readln(f,a[i]); close(f) end; procedure xl; var i,j,x:word; st,s1:string; begin assign(f,fo);rewrite(f); for i:=1 to n do begin st:=a[i]; while st[1]=' ' do delete(st,1,1); while st[length(st)]=' ' do delete(st,length(st),1); write(f,st[1],' '); while st'' do begin if st[1]='1' then begin x:=pos('0',st); if x0 then s1:=copy(st,1,x-1) else begin s1:=st;x:=length(st)+1;end; delete(st,1,x-1); write(f,length(s1),' '); end; if st[1]='0' then begin x:=pos('1',st); if x0 then s1:=copy(st,1,x-1) else begin s1:=st;x:=length(st)+1;end; delete(st,1,x-1); write(f,length(s1),' '); end; end; writeln(f); end; close(f); end; begin doc; xl; end. Câu 3: HCN.PAS {$R+,Q+,S+} const INP ='hcn.inp'; OUT ='hcn.out'; MAX = 1000; var x1,y1,x2,y2,kq :array [1..MAX] of integer; n : integer; fi,fo : text; procedure input; var i : integer; begin assign(fi,INP); reset(fi); read(fi,n); for i := 1 to n do read(fi,x1[i],y1[i],x2[i],y2[i]); close(fi); end; function area(i : integer) : longint; begin area:=longint(abs(x1[i]-x2[i]))*longint(abs(y1[i]-y2[i])); end; procedure qsort(l,r : integer); var i, j, mid, t : integer; begin mid := (1 + r) div 2; i := 1; j:= r; repeat while area(i) < area(mid) do inc(i); while area(j) > area(mid) do dec(j); if i <= j then begin t := x1[i]; x1[i] := x1[j]; x1[j] := t; t := x2[i]; x2[i] := x2[j]; x2[j] := t; t := y1[i]; y1[i] := y1[j]; y1[j] :=t; t := y2[i]; y2[i] := y2[j]; y2[j] :=t; inc(i); dec(j); end; until i > j; if i < r then qsort(1,j); end; function bao(i,j : integer) : integer; begin if (x1[i]= y1[j])and(x2[i]>= x2[j])and (y2[i] <= y2[j]) then bao := 1 else bao := 0; End; procedure progress; var i, j : integer; begin for i := 1 to n do kq[i] := 1; for i := 2 to n do for j := 1 to i-1 do if (bao(i,j) = 1) then kq[i] := kq[j] + 1; end; procedure output; var i, tmp : integer; begin tmp := 0; for i := 1 to n do if kq[i] > tmp then tmp := kq[i]; {if tmp = 1 then tmp := -1;} assign(fo,OUT); rewrite(fo); writeln(fo,tmp); close(fo); end; begin input; qsort(1,n); progress; output; end. Hết