S GIÁO D C – ĐÀO T O Ở Ụ Ạ KỲ THI CH N H C SINH GI I L P 12 C PỌ Ọ Ỏ Ớ Ấ
T NH Ỉ
TH A THIÊN HU Ừ Ế NĂM H C 2005 – 2006Ọ
Đ chính th cề ứ Môn thi: TIN H C, vòng 1Ọ
S báo danh: ốTh i gian: 150 phút (không k th i gian giao đ )ờ ể ờ ề
H C SINH L P TRÌNH GI I HAI BÀI TOÁN SAUỌ Ậ Ả :
(đ thi có 3 trangề)
T ng quan v các file:ổ ề
Tên bài Tên file ngu nồTên file văn b n ch a d li u vào,ả ứ ữ ệ
ra
Vào Ra
Bài toán cổTOANCO.PAS TOANCO.INP TOANCO.OUT
Kim t thápựTUTHAP.PAS TUTHAP.INP TUTHAP.OUT
BÀI 1: BÀI TOÁN C . Ổ
T ng truy n r ng, ngày x a có m t m u sĩ th y dân chúng quáươ ề ằ ư ộ ư ấ
nghèo kh nên ông ta đã đ n thách đ đánh c cùng nhà vua nh m l yổ ế ố ờ ằ ấ
thóc trong kho đem phân phát cho dân nghèo. Nhà vua ra đi u ki n n uề ệ ế
đánh thua nhà vua thì m u sĩ s b chém đ u, ng c l i m u sĩ s đ cư ẽ ị ầ ượ ạ ư ẽ ượ
tr ng th ng b ng v t ch t. N u đánh th ng c v i nhà vua, m u sĩ chọ ưở ằ ậ ấ ế ắ ờ ớ ư ỉ
xin m t đi u đó là trong m i ô c g m 8x8 ô thì l n l t b vào ô th 1: 1ộ ề ỗ ờ ồ ầ ượ ỏ ứ
h t thóc, ô th 2: 1x2 h t thóc, ô th 3: 1x2x3 h t thóc,… cho đ n ô cu iạ ứ ạ ứ ạ ế ố
cùng. Nhà vua nghe qua r t khoái chí và đ ng ý ngay. Sau l n đ u c đóấ ồ ầ ấ ờ
nhà vua đã m t r t nhi u kho l ng th c cho dân nghèo. ấ ấ ề ươ ự
Do b n tính hi u th ng c a nhà vua, ông v n ti p t c thách đ u v iả ế ắ ủ ẫ ế ụ ấ ớ
nh ng tay cao th c khác trong thiên h nh ng bây gi rút kinh nghi mữ ủ ờ ạ ư ờ ệ
ông ch xu t trong kho ra bây gi không ph i là thóc n a mà là vàng.ỉ ấ ờ ả ữ
Nguyên t c đ nh n đ c vàng sau khi đánh th ng nhà vua nh sau:ắ ể ậ ượ ắ ư
1. M i ô trong bàn c có m t s . Con s này đ c gán vào nh sau:ỗ ờ ộ ố ố ượ ư
- Ô s 1: ố 1
- Ô s 2: ố 1x2 = 2
- Ô s 3: ố 1x2x3 = 6
… …
- Ô s 10 1x2x3x….x10 = 3 628 800 ố
… …
- Ô s 21 1x2x3x….x21 = 51 090 942 171 709 440 000ố
1
… …
2. S vàng nh n đ c chính là con s khác không đ u tiên k tố ậ ượ ố ầ ể ừ
hàng đ n v lên phía tr c c a ô mà đ i th s ch n. Ví d ,ơ ị ướ ủ ố ủ ẽ ọ ụ
ch n ô s 10 thì s đ c 8 l ng vàng, ô s 21 s đ c 4 l ngọ ố ẽ ượ ạ ố ẽ ượ ạ
vàng,…
3. Đ i th ch đ c ch n m i l n m t ô đ nh n vàng. Khôngố ủ ỉ ượ ọ ỗ ầ ộ ể ậ
đ c phép ch n các ô bé h n 6.ượ ọ ơ
4. Bàn c dùng thi đ u là bàn c 8x8, nh ng bàn c đ ch n vàngờ ấ ờ ư ờ ể ọ
là NxN (1 ≤ N ≤10 000), các ô đ c đánh s liên t c t 1đ n N. ượ ố ụ ừ ế
Yêu c u:ầ Em hãy vi t ch ng trình đ giúp đ u th n nh n đ cế ươ ể ấ ủ ọ ậ ượ
vàng theo các yêu c u nói trên.ầ
D li u vào:ữ ệ có nhi u dòng liên ti p nhau, trên m i dòng ch a m tề ế ỗ ứ ộ
s nguyên không âm, đó là th t ô mà đ u th đó ch n. ố ứ ự ấ ủ ọ
D li u ra:ữ ệ có s dòng b ng s dòng t ng ng v i d li u vào.ố ằ ố ươ ứ ớ ữ ệ
Trên m i dòng có n i dung: ch s đ u tiên là ô s mà đ u th n ch n,ỗ ộ ữ ố ầ ố ấ ủ ọ ọ
ti p theo là m t mũi tên “->” và cu i cùng là ch s khác không cu i cùngế ộ ố ữ ố ố
c a ô s đó (theo các nguyên t c trên). ủ ố ắ
Ví d :ụ
D li u vàoữ ệ D li u raữ ệ
26 26 -> 4
125 125 -> 8
3125 3125 -> 2
9999 9999 -> 8
BÀI 2: KIM T THÁP. Ự
Các nhà khoa h c l ch s mu n tìm m t khu đ t đ xây d ng m tọ ị ử ố ộ ấ ể ự ộ
ki n trúc mang hình kim t tháp. V i ý t ng là ngôi v n mà công trìnhế ự ớ ưở ườ
ki n trúc đ c xây d ng cũng ph i có hình tam giác. Chính quy n đ aế ượ ự ả ề ị
ph ng nhi u n i đã tìm ki m r t v t v , cu i cùng cũng ch n ra đ cươ ề ơ ế ấ ấ ả ố ọ ượ
m t s khu v n nh th . D i đây là m t trong các khu v n có hìnhộ ố ườ ư ế ướ ộ ườ
dáng c n tìm:ầ
2
Tuy nhiên trên các khuôn viên l i có m t s công trình, cây c i, …ạ ộ ố ố
đã có tr c đây c n ph i duy trì. H ph i l i b t đ u tính toán đ tìm raướ ầ ả ọ ả ạ ắ ầ ể
đ c m t ô đ t cũng có hình tam giác mà di n tích c a nó là l n nh t.ượ ộ ấ ệ ủ ớ ấ
Hình v trên cho ta th y các ô có màu đen chính là các công trình đã có; cácẽ ấ
ô tr ng là đ t tr ng và đ ng vi n đ m là khu v c đ c đánh d u đ xâyắ ấ ố ườ ề ậ ự ượ ấ ể
d ng.ự
Yêu c u:ầ Hãy l p trình tìm ra khu đ t có di n tích l n nh t theoậ ấ ệ ớ ấ
yêu c u c a các nhà khoa h c đã đ a ra.ầ ủ ọ ư
D li u vào:ữ ệ g m nhi u dòng:ồ ề
- dòng đ u tiên là n, n là đ r ng c a tam giác (1 ≤ n ≤ 100).ầ ộ ộ ủ
- n dòng ti p theo ch a các ký t {#, -} đ i di n các hàng c a tamế ứ ự ạ ệ ủ
giác. Ký t ‘#’ là màu đen và ‘-’ màu tr ng. Trong m i tam giác,ự ắ ỗ
s ký t ‘#’ và ‘-’ là l và gi m d n t 2n – 1 xu ng 1. ố ự ẻ ả ầ ừ ố
D li u ra:ữ ệ ch m t dòng ch a m t s nguyên là k t qu tìm ra khuỉ ộ ứ ộ ố ế ả
đ t l n nh t c n xây d ng có n i dung “Dien tich lon nhat:” ti p theo làấ ớ ấ ầ ự ộ ế
di n tích tìm đ c. N u không tìm ra cũng tr l i “KHONG TIM RA”ệ ượ ế ả ờ
Ví d , v i hình trên ta có d li u vào, ra nh sau:ụ ớ ữ ệ ư
D li u vàoữ ệ D li u raữ ệ
5
#-##----#
-----#-
---#-
-#-
-
Dien tich lon nhat: 9
3
-Giám th không gi i thích gì thêm.ị ả
ĐÁP ÁN, H NG D N CH M MÔN TIN H C (VÒNG 1) KỲ THI CH N H CƯỚ Ẫ Ấ Ọ Ọ Ọ
SINH GI I L P 12 C P T NH NĂM H C 2005 – 2006Ỏ Ớ Ấ Ỉ Ọ
I.Đáp án, h ng dãn ch m.ướ ấ
BÀI 1: BÀI TOÁN C . 12đi mỔ ể
Có 24 test, m i test cho 0.5 đi m. T t c th c hi n cùng lúc trongỗ ể ấ ả ự ệ
m t th i đi m test, th i gian th c thi không quá 30 giâyộ ờ ể ờ ự
INP OUT
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
5
6
7
8
9
10
14
15
24
25
26
124
125
624
625
3124
3125
9999
100
200
501
5001
7029
7501
5 -> 2
6 -> 2
7 -> 4
8 -> 2
9 -> 8
10 -> 8
14 -> 2
15 -> 8
24 -> 6
25 -> 4
26 -> 4
124 -> 4
125 -> 8
624 -> 6
625 -> 6
3124 -> 4
3125 -> 2
9999 -> 8
100 -> 4
200 -> 2
501 -> 4
5001 -> 2
7029 -> 4
7501 -> 6
BÀI 2: KIM T THÁP. 8 đi mỰ ể
Có 16 test, m i test cho 0.5 đi m. Th c hi n m i lúc m t test, th iỗ ể ự ệ ỗ ộ ờ
gian th c thi không quá 30 giâyự
1
-
1
#
2
4
#--
#
3
-----
--#
-
3
-#-#-
---
#
5
---------
-------
-----
---
-
10
--#--#--#---#---#--
---------#-------
--#-##----#----
---------#---
#-#------#-
--#-#-#--
------#
--#--
---
-
20
----------------#------#-#------#--#---
#------#------##-#--#------------##--
-#--------#--##--------##-#---#-#--
##-------#--#---#------#------##-
#-#-------#-------#---------#--
-----#------------#--------#-
--##----#-----------------#
--#-------#--------#--##-
-##---#------#-#---#---
--#-------###--------
---#---#-----------
-------#-#--#-##-
-------#-------
---#------##-
-#-----##--
-------#-
#-#----
-----
-#-
-
30
-----#---##---#-----#---------#----------#----#---##-------
----------#--#----------------#-----#-----#--#-----------
---#------#--------#-----#----#-----#----#----#-------#
--#------#-#--#-----#-----#-----------##--#---#------
------#------##----#-----###------#-----------#----
5