Kỳ thi học sinh giỏi tỉnh năm học 2011-2012 Đắk Lắk Môn : tin học 12 - THPT

SỞ GIÁO DỤC VÀ ĐÀO TẠO KỲ THI HỌC SINH GIỎI TỈNH NĂM HỌC 2011-2012 ĐẮK LẮK MÔN : TIN HỌC 12 - THPT (Thời gian: 180 phút, không kể thời gian giao đề) Ngày thi: 10/11/2011 Ghi chú : Đề thi này gồm 2 trang. Bài File bài làm Dữ liệu vào Kết quả Bài 1: Tính tổng BAI1.PAS BAI1.INP BAI1.OUT Bài 2: Siêu nguyên tố BAI2.PAS Nhập từ phím Xuất ra màn hình Bài 3: Tô màu BAI3.PAS BAI3.INP BAI3.OUT Bài 1: Tính tổng (5 điểm). Trên một màn hình lớn, người ta lần lượt cho hiện ra các số của một dãy gồm N số nguyên không âm a1, a2, …, aN và cứ lặp đi lặp lại như thế (nghĩa là sau khi ai xuất hiện vài giây đến lượt ai+1 xuất hiện, số xuất hiện sau aN là a1). Yêu cầu: Bạn được đề nghị tính tổng của K số nguyên liên tiếp xuất hiện trên màn hình bắt đầu từ số nguyên thứ B. Dữ liệu vào: Chứa trong file BAI1.INP gồm hai dòng: + Dòng đầu tiên ghi ba số nguyên N, K, và B, 1  N 104; 1  K  2. 104 ; 1  B  109. + Trong N dòng sau, dòng thứ i chứa số ai (ai < 2.109). Dữ liệu ra: Ghi ra file BAI1.OUT một số là tổng tìm được. Ví dụ: BAI1.INP BAI1.OUT 5 7 6 2 3 6 7 9 32 Bài 2(6 điểm) - Siêu nguyên tố Số siêu nguyên tố là số nguyên tố mà khi bỏ một số tuỳ ý các chữ số bên phải của nó thì phần còn lại vẫn tạo thành một số nguyên tố. Ví dụ 7331 là một số siêu nguyên tố có 4 chữ số vì 733, 73, 7 cũng là các số nguyên tố. Viết chương trình nhập dữ liệu vào là một số nguyên N (0< N <10) và đưa ra kết quả là các số siêu nguyên tố có N chữ số cùng số lượng của chúng. Bài 3(9 điểm) -Tô màu Cho một bảng gồm các ô vuông kích thước M x N (M, N 100), trong đó có một số ô đen, còn lại là các ô trắng. Yêu cầu: Hãy tô màu tất cả các ô trắng bằng hai màu xanh và vàng sao cho trên mỗi dòng cũng như trên mỗi cột số các ô màu xanh và vàng lệch nhau không quá 1. ĐỀ CHÍNH THỨC Dữ liệu vào: Được cho trong file văn bản BAI3.INP - Dòng đầu ghi hai số M, N - M dòng tiếp theo mỗi dòng ghi N số, gồm các số 0 hoặc 1 biểu diễn bảng ô vuông, với 0 biểu thị ô trắng, 1 biểu thị ô đen. Kết quả: Ghi ra file văn bản BAI3.OUT gồm M dòng, mỗi dòng gồm N ký tự viết liền nhau biểu diễn trạng thái màu đã tô của bảng với D: màu đen, X: màu xanh, V: màu vàng. Ví dụ: BAI3.INP 6 4 1 0 1 0 1 0 0 0 0 1 0 1 1 1 0 0 0 1 0 1 1 0 1 0 BAI3.OUT DVDX DXXV XDVD DDVX VDXD DXDV ------- Hết -------- Ghi chú: Giám thị coi thi không giải thích gì thêm. SỞ GIÁO DỤC VÀ ĐÀO TẠO KỲ THI HỌC SINH GIỎI TỈNH NĂM HỌC 2011-2012 ĐẮK LẮK MÔN : TIN HỌC 12 - THPT (Thời gian: 180 phút, không kể thời gian giao đề) Ngày thi: 10/11/2011 Ghi chú : Đề thi này gồm 2 trang. Bài File bài làm Dữ liệu vào Kết quả Bài 1: Tính tổng BAI1.PAS BAI1.INP BAI1.OUT Bài 2: Siêu nguyên tố BAI2.PAS Nhập từ phím Xuất ra màn hình Bài 3: Tô màu BAI3.PAS BAI3.INP BAI3.OUT Bài 1: Tính tổng (5 điểm). Trên một màn hình lớn, người ta lần lượt cho hiện ra các số của một dãy gồm N số nguyên không âm a1, a2, …, aN và cứ lặp đi lặp lại như thế (nghĩa là sau khi ai xuất hiện vài giây đến lượt ai+1 xuất hiện, số xuất hiện sau aN là a1). Yêu cầu: Bạn được đề nghị tính tổng của K số nguyên liên tiếp xuất hiện trên màn hình bắt đầu từ số nguyên thứ B. Dữ liệu vào: Chứa trong file BAI1.INP gồm hai dòng: + Dòng đầu tiên ghi ba số nguyên N, K, và B, 1  N 104; 1  K  2. 104 ; 1  B  109. + Trong N dòng sau, dòng thứ i chứa số ai (ai < 2.109). Dữ liệu ra: Ghi ra file BAI1.OUT một số là tổng tìm được. Ví dụ: BAI1.INP BAI1.OUT 5 7 6 2 3 6 7 9 32 Bài 2(6 điểm) - Siêu nguyên tố Số siêu nguyên tố là số nguyên tố mà khi bỏ một số tuỳ ý các chữ số bên phải của nó thì phần còn lại vẫn tạo thành một số nguyên tố. Ví dụ 7331 là một số siêu nguyên tố có 4 chữ số vì 733, 73, 7 cũng là các số nguyên tố. Viết chương trình nhập dữ liệu vào là một số nguyên N (0< N <10) và đưa ra kết quả là các số siêu nguyên tố có N chữ số cùng số lượng của chúng. Bài 3(9 điểm) -Tô màu Cho một bảng gồm các ô vuông kích thước M x N (M, N 100), trong đó có một số ô đen, còn lại là các ô trắng. Yêu cầu: Hãy tô màu tất cả các ô trắng bằng hai màu xanh và vàng sao cho trên mỗi dòng cũng như trên mỗi cột số các ô màu xanh và vàng lệch nhau không quá 1. ĐỀ CHÍNH THỨC Dữ liệu vào: Được cho trong file văn bản BAI3.INP - Dòng đầu ghi hai số M, N - M dòng tiếp theo mỗi dòng ghi N số, gồm các số 0 hoặc 1 biểu diễn bảng ô vuông, với 0 biểu thị ô trắng, 1 biểu thị ô đen. Kết quả: Ghi ra file văn bản BAI3.OUT gồm M dòng, mỗi dòng gồm N ký tự viết liền nhau biểu diễn trạng thái màu đã tô của bảng với D: màu đen, X: màu xanh, V: màu vàng. Ví dụ: BAI3.INP 6 4 1 0 1 0 1 0 0 0 0 1 0 1 1 1 0 0 0 1 0 1 1 0 1 0 BAI3.OUT DVDX DXXV XDVD DDVX VDXD DXDV ------- 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 2011-2012 ĐẮK LẮK MÔN : TIN HỌC 12 - THPT ĐÁP ÁN VÀ HƯỚNG DẪN CHẤM ĐỀ CHÍNH THỨC I. Phần chương trình nguồn Bài 1(5 điểm) - Tính tổng program BAI1; const fi='BAI1.inp'; fo='BAI1.out'; nmax=10003; var a:array[1..nmax]of int64; n,k,b:longint; kq:int64; f,g:text; procedure nhapdulieu; var i:integer; begin assign(f,fi); reset(f); readln(f,n,k,b); for i:=1 to n do readln(f,a[i]); close(f); end; procedure xuly; var i,j:longint; begin kq:=0; for i:=b to b+k-1 do kq:=kq+a[(i-1) mod N +1]; assign(g,fo); rewrite(g); write(g,kq); close(g); end; Begin nhapdulieu; xuly; End. Bài 2(6 điểm) - Siêu nguyên tố var a,b: array [1..100] of longint; N,i,k,ka,kb,cs: byte; Function Prime(N: longint): boolean; Var i: longint; Begin If (N=0) or (N=1) then Prime:=false Else Begin i:=2; While (N mod i 0) and (i <= Sqrt(N)) do Inc(i); If i > Sqrt(N) then Prime:=true Else Prime:=false; End; End; BEGIN Write ('Nhap N: '); Readln (N); ka:=1; a[ka]:=0; For i:=1 to N do Begin Kb:=0; For k:=1 to ka do For cs:=0 to 9 do If Prime(a[k]*10+cs) then Begin Inc(kb); b[kb]:=a[k]*10+cs; end; ka:=kb; For k:=1 to ka do a[k]:=b[k]; end; For k:=1 to ka do Write(a[k]:10); Writeln; Writeln('Co tat ca ',ka,' so sieu nguyen to co ',N,' chu so.'); Readln; END. Bài 3(9 điểm) -Tô màu const tfi = 'BAI3.INP'; tfo = 'BAI3.OUT'; maxN = 101; var fi, fo : text; M,N : integer; a : array[1..maxN,1..maxN] of byte; bac : array[1..2*maxN] of integer; procedure Docdl; var i,j: integer; begin assign(fi,tfi); reset(fi); readln(fi,M,N); for i:=1 to M do begin for j:=1 to N do read(fi,a[i,j]); readln(fi); end; close(fi); end; function DinhBacLe: integer; var i: integer; begin for i:=1 to M+N do if odd(bac[i]) then begin DinhBacLe:=i; exit; end; DinhBacLe:=0; end; function Next(u: integer): integer; var v: integer; begin if u<=M then begin for v:=1 to N do if a[u,v]=0 then begin Next:=v+M; exit; end; end else begin for v:=1 to M do if a[v,u-M]=0 then begin Next:=v; exit; end; end; Next:=0; end; procedure ToMau(xp: integer); var u,v,color: integer; begin color:=2; u:=xp; repeat v:=Next(u); if v>0 then begin if u<=M then a[u,v-M]:=color else a[v,u-M]:=color; bac[u]:=bac[u]-1; bac[v]:=bac[v]-1; u:=v; color:=5-color; end; until v=0; end; function DinhConCanh: integer; var i: integer; begin for i:=1 to M+N do if bac[i]>0 then begin DinhConCanh:=i; exit; end; DinhConCanh:=0; end; procedure Solve; var i,j,u: integer; begin for i:=1 to M do begin bac[i]:=0; for j:=1 to N do bac[i]:=bac[i]+(1-a[i,j]); end; for i:=M+1 to M+N do begin u:=i-M; bac[i]:=0; for j:=1 to M do bac[i]:=bac[i]+(1-a[j,u]); end; {Tim cac duong xuat phat tu dinh le} repeat u:=DinhBacLe; if u>0 then ToMau(u); until u=0; {Tim cac duong xuat phat tu dinh bac chan} repeat u:=DinhConCanh; if u>0 then ToMau(u); until u=0; end; procedure Inkq; var i,j: integer; begin assign(fo,tfo); rewrite(fo); for i:=1 to M do begin for j:=1 to N do case a[i,j] of 1: write(fo,'D'); 2: write(fo,'X'); 3: write(fo,'V'); end; writeln(fo); end; close(fo); end; BEGIN Docdl; Solve; Inkq; END. II. Phần hướng dẫn chấm Bai 1 (5 đ): Test chương trình với 5 dữ liệu nhập khác nhau. Mỗi lần đúng cho 1 điểm. Bai 2 (6 đ): Test chương trình với 5 lần : n=1..5 N=1 có 4 số; N=2 có 9 số; N=3 có 14 số; N=4 có 16 số; N=5 có 15 số. Chú ý trong mỗi trường hợp cần kiểm tra các số tìm được có thỏa mãn là số siêu nguyên tố hay không. Mỗi test đúng cho 1 điểm. Bai 3 (9 đ): Có 9 test ( lưu trong đĩa CD) Mỗi test đúng cho 1 điểm ---- Hết ----