Tài liệu đề thi đáp án thi học sinh giỏi tin lớp 9

PHÒNG GIÁO DỤC–ĐÀO TẠO TRỰC NINH ĐỀ THI CHỌN HỌC SINH GIỎI NĂM HỌC 2009-2010 Môn: TIN HỌC Lớp 9 Thời gian làm bài: 120 phút (không kể thời gian giao đề) ¬ ĐỀ CHÍNH THỨC LËp ch¬ng tr×nh gi¶i c¸c bµi to¸n sau: Bµi 1 (6,0 ®iÓm): D·y sè NhËp vµo mét d·y sè nguyªn, mçi sè n»m trªn mét dßng cho ®Õn khi gÆp sè 0 th× dõng l¹i (sè 0 kh«ng ®îc tÝnh vµo d·y). Yªu cÇu in ra mµn h×nh: - Sè lîng c¸c sè tho¶ m·n trong d·y - Sè lîng c¸c sè nguyªn d¬ng - Sè lîng c¸c sè lµ sè nguyªn tè - Sè lîng c¸c sè chia hÕt cho 3 VÝ dô minh ho¹ mµn h×nh thùc hiÖn ch¬ng tr×nh: Nhap mot day so nguyen vao: 2 3 11 12 6 9 17 -8 2009 0 So cac so thoa man la:9 So cac so nguyen duong la:8 So cac so nguyen to la:4 So cac so chia het cho 3 la:4 Bµi 2 (7,0 ®iÓm): Tr¶ tiÒn Anh Nam ®i chî mua mét mÆt hµng cã gi¸ trÞ lµ N ®ång. Trong tói anh Nam cã nhiÒu tê tiÒn víi mÖnh gi¸ lµ 50 ®ång, 100 ®ång vµ 200 ®ång. Anh Nam cã thÓ cã nhiÒu c¸ch tr¶ tiÒn ®Ó mua mÆt hµng ®ã (anh Nam chØ dïng c¸c tê tiÒn mµ anh cã s½n. Anh kh«ng ®a thõa tiÒn cho ngêi b¸n v× ngêi b¸n kh«ng cã tiÒn tr¶ l¹i). Yªu cÇu: Cho biÕt sè tiÒn N (N nguyªn vµ 10<=N<=30000); ®a ra tÊt c¶ c¸c c¸ch tr¶ tiÒn cña anh Nam tháa m·n. Input: Vào từ file văn bản TRATIEN.INP chứa duy nhất số tự nhiên N (10<= N<=30000) Output: Ghi ra file văn bản TRATIEN.OUT nếu có nhiều cách thì in mỗi cách trên một dòng, nếu không có cách nào thì in ra số -1 VÝ dô minh ho¹ mµn h×nh thùc hiÖn ch¬ng tr×nh: TRATIEN.INP 200 TRATIEN.OUT 0 0 2 4 x x x x 50 50 50 50 + + + + 0 2 1 0 x x x x 100 100 100 100 + + + + 1 0 0 0 x x x x 200 200 200 200 Bài 3. ( 7,0 điểm) Mật khẩu Một nhóm gồm k học sinh góp tiền mua một phần mềm dùng chung. Khi cài đặt phần mềm này, người sử dụng cần phải nhập vào một mật khẩu Khi biết các khách hàng của mình là các học sinh say mê tin học, chủ cửa hàng thay vì đưa mật khẩu đã đưa cho mỗi bạn một con số khác nhau và sau đó nói rằng: Mật khẩu để cài đặt phần mềm là số nguyên dương nhỏ nhất gồm không quá chín chữ số chia hết cho bất cứ số nào trong các số tôi đã đưa cho các bạn. Yêu cầu: Biết tất cả các số mà chủ cửa hàng đã đưa cho các học sinh, hãy tìm mật khẩu để cài đặt phần mềm. Input: Vào từ file văn bản MATKHAU.INP. Dòng đầu tiên chứa số học sinh k (k <20). Dòng thứ hai chứa k số nguyên dương nhỏ hơn 20 mà ông chủ cửa hàng đã đưa cho các học sinh, hai số liên tiếp cách nhau bởi dấu cách. Output: Ghi ra file văn bản MATKHAU.OUT mật khẩu tìm được. Ví dụ về input và output: MATKHAU.INP MATKHAU.OUT 3 12 463 Chú ý: Bài 1 đặt tên là DAYSO.PAS Bài 2 đặt tên là TRATIEN.PAS Bài 3 đặt tên là MATKHAU.PAS ------ Hết ------ HƯỚNG DẪN CHẤM Bµi 1: 6,0 ®iÓm V¨n b¶n ch¬ng tr×nh - Mçi Text ®óng cho (ch¹y ch¬ng tr×nh ®Ó cho ®iÓm) - §a ra khu«n d¹ng kh«ng ®óng yªu cÇu trõ - ThuËt to¸n kh«ng tèi u trõ 2,0 ® 0,5® 0,5® uses crt; var N,dem,demd,dem3,snt,i:longint; Nt:boolean; g:text; begin clrscr; writeln('Nhap mot day so nguyen vao:'); dem:=0;demd:=0;dem3:=0;snt:=0; repeat readln(N);inc(dem); if N>0 then inc(demd); if N>1 then begin Nt:=true; for i:=2 to trunc(sqrt(N)) do if N mod i=0 then NT:=False; if NT then inc(snt); end; if N mod 3=0 then inc(dem3); until N=0; writeln('So cac so thoa man la:',dem-1); writeln('So cac so nguyen duong la:',demd); writeln('So cac so nguyen to la:',snt); writeln('So cac so chia het cho 3 la:',dem3-1); readln; end. Bµi 2: 7,0 ®iÓm - Mçi Text ®óng cho - §a ra khu«n d¹ng kh«ng ®óng yªu cÇu trõ - NÕu dïng 3 vßng for trõ V¨n b¶n ch¬ng tr×nh Var 0,5® 0,5® N,a,b:Integer; f,g:text; kt:boolean; Begin End. 1,0 ® assign(f,'tratien.inp');reset(f); assign(g,'tratien.out');rewrite(g); read(f,N); kt:=true; If N mod 50=0 Then For a:=0 to N div 50 do For b:=0 to (N-50*a) div 100 do If (N-50*a-100*b) mod 200 = 0 then begin Writeln(g,a,' x 50 + ',b,' x 100 + ',(N-50*a-100*b) div 200,' x 200'); kt:=false; end; if kt then write(g,-1); close(f);close(g); TRATIEN.INP TRATIEN.OUT 0 x 50 + 0 x 100 + 1 x 200 0 x 50 + 2 x 100 + 0 x 200 2 x 50 + 1 x 100 + 0 x 200 4 x 50 + 0 x 100 + 0 x 200 0 x 50 + 1 x 100 + 2 x 200 0 x 50 + 3 x 100 + 1 x 200 0 x 50 + 5 x 100 + 0 x 200 2 x 50 + 0 x 100 + 2 x 200 2 x 50 + 2 x 100 + 1 x 200 2 x 50 + 4 x 100 + 0 x 200 4 x 50 + 1 x 100 + 1 x 200 4 x 50 + 3 x 100 + 0 x 200 6 x 50 + 0 x 100 + 1 x 200 6 x 50 + 2 x 100 + 0 x 200 8 x 50 + 1 x 100 + 0 x 200 10 x 50 + 0 x 100 + 0 x 200 -1 200 500 1120 1000 10000 20000 30000 In ra 36 cach In ra 2601 cach In ra 10201 cach In ra 22801 cach Bµi 3: 7,0 ®iÓm - Mçi Text ®óng cho - ThuËt to¸n kh«ng tèi u trõ V¨n b¶n ch¬ng tr×nh 1,0 ® 0,5® var f,g:text; b,a:array[1..19] of Byte; T,kq,du:longint; N,i:Byte; begin assign(f,'matkhau.inp');reset(f); assign(g,'matkhau.out');rewrite(g); readln(f,N); for i:=1 to N do read(f,a[i]): kq:=a[1]; for i:=2 to N do begin T:=kq*a[i]; du:=kq mod a[i]; while du<>0 do begin kq:=a[i]; a[i]:=du; du:=kq mod a[i]; end; kq:=T div a[i]; end; writeln(g,kq); close(f);close(g); end. MATKHAU.INP 3 463 5 MATKHAU.OUT 12 232560 MATKHAU.INP 15 16 17 18 19 5 9 10 11 12 13 10 1 2 3 4 5 6 7 8 9 10 10 10 11 12 13 14 15 16 17 18 19 15 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 19 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 MATKHAU.OUT 25740 2520 232792560 360360 232792560