S GIÁO D C & ĐÀO T OỞ Ụ Ạ
H I D NGẢ ƯƠ KÌ THI CH N H C SINH GI I T NH Ọ Ọ Ỏ Ỉ
L P 12 THPT NĂM H C 2012 - 2013Ớ Ọ
MÔN THI: TIN H CỌ
Th i gian làm bài: 180 phútờ
(Đ g m 03 trangề ồ )
T NG QUAN V CÁC BÀI THI TRONG ĐỔ Ề Ề
Bài
Tên file
ch ngươ
trình
D li uữ ệ
nh pậ
D li uữ ệ
xu tấ
Đi m c aể ủ
bài
Gi i h nớ ạ
th i gianờ
ch y 1 testạ
1 BAI1.* bàn phím màn hình 2,0 đi mể1 giây
2 BAI2.* bàn phím màn hình 2,5 đi mể1 giây
3 BAI3.* bàn phím màn hình 2,0 đi mể1 giây
4 BAI4.* VNMODEL.INP VNMODEL.OUT 2,0 đi mể1 giây
5 BAI5.* GEN.INP GEN.OUT 1,5 đi mể1 giây
Yêu c u các thí sinh đc k ph n h ng d n d i đây:ầ ọ ỹ ầ ướ ẫ ướ
D u (*) trong tên file ch ng trình đc thay th b ng PAS ho c CPP tu theo thí sinhấ ươ ượ ế ằ ặ ỳ
vi t ch ng trình b ng ngôn ng Pascal ho c C++. Ví d , n u h c sinh vi t b ng ngônế ươ ằ ữ ặ ụ ế ọ ế ằ
ng Pascal thì tên các bài l n l t là BAI1.PAS, BAI2.PAS, BAI3.PAS, BAI4.PAS,ữ ầ ượ
BAI5.PAS
V i bài 4 và bài 5 tên file d li u nh p và d li u xu t đt đúng nh ph n t ng quan ớ ữ ệ ậ ữ ệ ấ ặ ư ầ ổ ở
trên (không có đng d n kèm theo)ườ ẫ
HÃY L P TRÌNH GI I CÁC BÀI TOÁN SAU:Ậ Ả
Bài 1: Trong d p ngh hè, bé Mai đc b m cho đi t m bi n. Trên b bi n bé nh t đcị ỉ ượ ố ẹ ắ ể ờ ể ặ ượ
N viên đá cu i r t đp m t. Mai quy t đnh v trên cát m t l i hình ch nh t kích th cộ ấ ẹ ắ ế ị ẽ ộ ướ ữ ậ ướ
a x b (a, b nguyên d ng) đc chia thành a x b ô vuông b ng các đng ngang d c saoươ ượ ằ ườ ọ
cho có th r i N hòn s i này vào các ô vuông sao cho m i ô vuông có nhi u nh t m t viênể ả ỏ ỗ ề ấ ộ
s i.ỏ
Hãy giúp bé Mai ch n kích th c c a hình ch nh t sao cho chu vi c a nó là nhọ ướ ủ ữ ậ ủ ỏ
nh t. In ra màn hình giá tr chu vi này.ấ ị
D li u:ữ ệ Nh p vào t bàn phím s nguyên d ng N (N ≤ 10ậ ừ ố ươ 9).
K t qu :ế ả Ghi ra màn hình chu vi c a hình ch nh t tìm đcủ ữ ậ ượ
Ví d :ụ
D li u nh p vào: 15ữ ệ ậ
K t qu in ra: 16ế ả
Gi i thích:ả Hình ch nh t tìm đc có kích th c 4 x 4ữ ậ ượ ướ
Bài 2: Xét m t s N có 4 ch s và không ph i t t c các ch s đu gi ng nhau. Phépộ ố ữ ố ả ấ ả ữ ố ề ố
tính đ l ch đc th c hi n nh sau:ộ ệ ượ ự ệ ư
T o s th nh t N1 b ng cách x p các ch s theo trình t gi m d nạ ố ứ ấ ằ ế ữ ố ự ả ầ
T o s th hai N2 b ng cách x p các ch s theo trình t tăng d n (n u có ch s 0ạ ố ứ ằ ế ữ ố ự ầ ế ữ ố
đu thì N2 s không ph i là s có 4 ch s )ở ầ ẽ ả ố ữ ố
Tính hi u N1-N2 và gán l i cho Nệ ạ
Các b c trên đc th c hi n cho đn khi nh n đc s N là 6174 ho c 0ướ ượ ự ệ ế ậ ượ ố ặ
Ví d : N u N=1023 ụ ế
Trang: 1
Đ CHÍNH TH CỀ Ứ
b c 1: N1=3210, N2=123, N=N1-N2=3087Ở ướ
b c 2: N1=8730, N2=378, N=N1-N2=8352Ở ướ
b c 3: N1=8532, N2=2358, N=N1-N2=6174Ở ướ
V y ta c n th c hi n 3 l n bi n điậ ầ ự ệ ầ ế ổ
Yêu c u: Hãy xác đnh s l n bi n đi th c hi n theo yêu c u trên.ầ ị ố ầ ế ổ ự ệ ầ
D li u:ữ ệ Nh p t bàn phím s nguyên d ng N (N đm b o có 4 ch s , khôngậ ừ ố ươ ả ả ữ ố
ph i t t c các ch s đu gi ng nhau và N khác 6174. Không c n ki m tra d li u nh p)ả ấ ả ữ ố ề ố ầ ể ữ ệ ậ
K t qu :ế ả Ghi ra màn hình s l n bi n đi t ng ng v i s Nố ầ ế ổ ươ ứ ớ ố
Ví d :ụ
D li u nh p: 5364ữ ệ ậ
K t qu in ra: 3ế ả
Bài 3: S siêu nguyên tố ố
S siêu nguyên t là s nguyên t mà khi xoá b d n các ch s bên ph i c a nó thìố ố ố ố ỏ ầ ữ ố ả ủ
ph n còn l i v n là s nguyên t . Ví d : 2333 là s siêu nguyên t vì 2333, 233, 23, 2 đuầ ạ ẫ ố ố ụ ố ố ề
là các s nguyên t .ố ố
Yêu v u: Cho s nguyên d ng M (M≤30000). Hãy tìm s siêu nguyên t g n v iầ ố ươ ố ố ầ ớ
M nh t, t c là tr tuy t đi c a hi u gi a s tìm đc v i M là nh nh t)ấ ứ ị ệ ố ủ ệ ữ ố ượ ớ ỏ ấ
D li u:ữ ệ Nh p vào t bàn phím s nguyên d ng M (không c n ki m tra d li uậ ừ ố ươ ầ ể ữ ệ
nh p)ậ
K t qu :ế ả Ghi ra màn hình các s nguyên t g n M nh t, m i s m t dòng theo thố ố ầ ấ ỗ ố ộ ứ
t s nh h n ghi tr c.ự ố ỏ ơ ướ
Ví d :ụ
D li u nh p: 30ữ ệ ậ
K t qu in ra trên 2 dòng:ế ả
29
31
Bài 4: Bình ch n qua đi n tho iọ ệ ạ
Trong vòng chung k t cu c thi “Vietnam Next Top Model” trên VTV3 các thí sinhế ộ
đc đánh s báo danh là m t s nguyên d ng có giá tr không v t quá 1000. Khán giượ ố ộ ố ươ ị ượ ả
xem truy n hình có th bình ch n cho thí sinh mình yêu thích b ng cách nh n tin qua đi nề ể ọ ằ ắ ệ
tho i di đng.ạ ộ
Ban t ch c nh n đc tin nh n h p l c a N khán gi (các khán gi đc đánh sổ ứ ậ ượ ắ ợ ệ ủ ả ả ượ ố
t 1 đn N), khán gi th ừ ế ả ứ i bình ch n cho thí sinh mang s báo danh ọ ố ai.
Hãy li t kê s báo danh c a nh ng thí sinh đc nhi u khán gi bình ch n nh tệ ố ủ ữ ượ ề ả ọ ấ
theo th t tăng d n.ứ ự ầ
D li u:ữ ệ Vào t file văn b n VNMODEL.INPừ ả
Dòng đu tiên ghi s nguyên d ng N là s l ng khán gi có tin nh n bình ch nầ ố ươ ố ượ ả ắ ọ
h p l (N≤10ợ ệ 6)
N dòng ti p theo, dòng th ế ứ i ghi s nguyên d ng ố ươ ai là s báo danh c a thí sinh màố ủ
khán gi th ả ứ i bình ch n.ọ
K t qu :ế ả Ghi ra file văn b n VNMODEL.OUTả
Danh sách các thí sinh đc nhi u khán gi bình ch n nh t theo th t s báo danh tăngượ ề ả ọ ấ ứ ự ố
d nầ
Trang: 2
Ví d :ụ
VNMODEL.INP VNMODEL.OUT
5
3
1
3
2
2
2
3
Ghi chú: Có ít nh t 50% s đi m c a bài t ng ng v i các test có N≤1000.ấ ố ể ủ ươ ứ ớ
Bài 5: Quan h huy t th ngệ ế ố
Trung tâm nghiêm c u gen thu th p N m u gen c a N cá th trong cùng m t loài. Nứ ậ ẫ ủ ể ộ
gen này đc mã hoá thành dãy N s nguyên d ng ượ ố ươ a1, a2, …, aN. B ph n phân tích sauộ ậ
khi xem xét đã đa ra đc k t lu n sau: ư ượ ế ậ
Hai cá th là có quan h huy t th ng g n khi và ch khi mã gen c a chúng bi uể ệ ế ố ầ ỉ ủ ể
di n trong c s 2 gi ng nhau ho c khác nhau đúng 1 bitễ ơ ố ố ặ
Ví d : Hai cá th có mã gen 7 (bi u di n trong c s 2 là 111) và 5 (bi u di n trongụ ể ể ễ ơ ố ể ễ
c s 2 là 101) là có quan h huy t th ng g n.ơ ố ệ ế ố ầ
Hãy đm xem trong s m u gen c a N cá th thu th p đc có bao nhiêu c p cá thế ố ẫ ủ ể ậ ượ ặ ể
có quan h huy t th ng g n.ệ ế ố ầ
D li u:ữ ệ Vào t file văn b n GEN.INPừ ả
Dòng đu tiên ghi s nguyên d ng N (N≤10ầ ố ươ 5)
N dòng ti p theo, dòng th i ghi mã gen c a cá th th i là m t s nguyên d ngế ứ ủ ể ứ ộ ố ươ
trong ph m vi t 1 đn 1000)ạ ừ ế
K t qu :ế ả Ghi ra file văn b n GEN.OUT m t s nguyên duy nh t là s c p có quan hả ộ ố ấ ố ặ ệ
huy t th ng g n đã tìm đc.ế ố ầ ượ
Ví d :ụ
GEN.INP GEN.OUT
5
1
2
3
4
5
4
3
10
10
10
3
Gi i thích ví d th nh t:ả ụ ứ ấ
Các s 1, 2, 3, 4, 5 bi u di n trong c s 2 l n l t là 001, 010, 011, 100, 101. Có 4ố ể ễ ơ ố ầ ượ
c p có quan h huy t th ng g n là:ặ ệ ế ố ầ
1 và 3, 1 và 5, 2 và 3, 4 và 5
Ghi chú: Có ít nh t 50% s đi m ng v i các test có N≤1000ấ ố ể ứ ớ
---------------------H T---------------------Ế
Trang: 3
H tên thí sinh:ọ...................................................................................S báo danh:ố........................
Giám th s 1:ị ố .........................................................................................................................................
Giám th s 2:ị ố ..........................................................................................................................................
Trang: 4
S GIÁO D C & ĐÀO T OỞ Ụ Ạ
H I D NGẢ ƯƠ KÌ THI CH N H C SINH GI I T NH Ọ Ọ Ỏ Ỉ
L P 12 THPT NĂM H C 2012 - 2013Ớ Ọ
MÔN THI: TIN H CỌ
T NG QUAN V CÁC BÀI THI TRONG ĐỔ Ề Ề
Bài
Tên file
ch ngươ
trình
D li uữ ệ
nh pậ
D li uữ ệ
xu tấ
Đi m c aể ủ
bài
Gi i h nớ ạ
th i gianờ
ch y 1 testạ
1 BAI1.* bàn phím màn hình 2,0 đi mể1 giây
2 BAI2.* bàn phím màn hình 2,5 đi mể1 giây
3 BAI3.* bàn phím màn hình 2,0 đi mể1 giây
4 BAI4.* VNMODEL.INP VNMODEL.OUT 2,0 đi mể1 giây
5 BAI5.* GEN.INP GEN.OUT 1,5 đi mể1 giây
CODE GI I CÁC BÀI TOÁN:Ả
Bài 1: Trong d p ngh hè, bé Mai đc b m cho đi t m bi n. Trên b bi n bé nh t đcị ỉ ượ ố ẹ ắ ể ờ ể ặ ượ
N viên đá cu i r t đp m t. Mai quy t đnh v trên cát m t l i hình ch nh t kích th cộ ấ ẹ ắ ế ị ẽ ộ ướ ữ ậ ướ
a x b (a, b nguyên d ng) đc chia thành a x b ô vuông b ng các đng ngang d c saoươ ượ ằ ườ ọ
cho có th r i N hòn s i này vào các ô vuông sao cho m i ô vuông có nhi u nh t m t viênể ả ỏ ỗ ề ấ ộ
s i.ỏ
Hãy giúp bé Mai ch n kích th c c a hình ch nh t sao cho chu vi c a nó là nhọ ướ ủ ữ ậ ủ ỏ
nh t. In ra màn hình giá tr chu vi này.ấ ị
D li u:ữ ệ Nh p vào t bàn phím s nguyên d ng N (N ≤ 10ậ ừ ố ươ 9).
K t qu :ế ả Ghi ra màn hình chu vi c a hình ch nh t tìm đcủ ữ ậ ượ
Ví d :ụ
D li u nh p vào: 15ữ ệ ậ
K t qu in ra: 16ế ả
Gi i thích:ả Hình ch nh t tìm đc có kích th c 4 x 4ữ ậ ượ ướ
Đáp án:
program BAI1;
var n, a, b, ds: longint;
BEGIN
read(n);
ds:=1000000001;
a:=0;
repeat
inc(a);
b:=n div a;
if n mod a<>0 then inc(b);
if ds>2*(a+b) then ds:=2*(a+b);
until b<a;
writeln(ds);
END.
Trang: 5
ĐÁP ÁN