S GD&ĐT VĨNH PHÚCỞ
TR NG THPT YÊN L C 2ƯỜ Ạ
——————
KÌ THI KSCL ĐI TUY N H C SINH GI I KH I 12Ộ Ể Ọ Ỏ Ố
Đ THI ỀMÔN: TIN H CỌ
NĂM H C 201Ọ7 - 2018
Th i gian làm bài 180 phút, không k th iờ ể ờ gian giao đ.ề
Đ thi g m: ề ồ 03 trang.
———————
T ng quan đ thiổ ề
Tên bàiFile ch ngươ
trình File d li uữ ệ File k t quế ả Th i gianờĐi mể
Tìm bi u th cể ứ bieuthuc.* bieuthuc.inp bieuthuc.out 1 giây 4
Đoán tu iổdoantuoi.* doantuoi.inp doantuoi.out 1 giây 3
Đng h báoồ ồ
th cứbaothuc.* baothuc.inp baothuc.out 1 giây3
Thí sinh thay * trong File ch ng trình b ng CPP ho c PAS tùy theo ngôn ng l p trình màươ ằ ặ ữ ậ
thí sinh s d ng là C++ ho c Pascalử ụ ặ
L p ch ng trình gi i các bài toán sau đâyậ ươ ả
Bài 1: Tìm bi u th cể ứ
M t bài toán tin mà Tu n r t thích thú, bài toán do th y Nam giao cho Tu n trongộ ấ ấ ầ ấ
th i gian Tu n chu n b cho k thi qu c t Tin h c t i Canada năm 2018. Bài toán nh sau:ờ ấ ẩ ị ỳ ố ế ọ ạ ư
Cho m t bi u th c đúng ch g m phép toán c ng v i các s h ng là s nguyên không âm,ộ ể ứ ỉ ồ ộ ớ ố ạ ố
ti n hành xóa h t các phép toán c ng v trái, sau đó d n các ch s l i, v bên trái thuế ế ộ ở ế ồ ữ ố ạ ế
đc xâu S. Hãy đa ra m t cách chèn các d u c ng vào xâu S đ nh n đc m t bi uượ ư ộ ấ ộ ể ậ ượ ộ ể
th c có giá tr b ng v ph i.ứ ị ằ ế ả
Ví d , bi u th c đúng 15+4+2017 = 2036, xóa h t d u c ng v trái ta thu đc xâu S =ụ ể ứ ế ấ ộ ở ế ượ
1542017, sau đó chèn các d u c ng đ nh n đc bi u th c 15+4+2017 có giá tr b ngấ ộ ể ậ ượ ể ứ ị ằ
2036. Tu n m i b n l p trình gi i quy t bài toán trên.ấ ờ ạ ậ ả ế
Input:
- Dòng đu ch a m t xâu ch g m các ký t s (t ‘0’ đn ‘9’) mô t xâu S;ầ ứ ộ ỉ ồ ự ố ừ ế ả
- Dòng th hai ch a m t xâu ch g m các ký t s (t ‘0’ đn ‘9’) mô t v ph i c a bi uứ ứ ộ ỉ ồ ự ố ừ ế ả ế ả ủ ể
th c đúng.ứ
Output: M t xâu ch g m các ký t s (t ‘0’ đn ‘9’) và d u c ng mô t v trái sau khiộ ỉ ồ ự ố ừ ế ấ ộ ả ế
thêm các d u c ng. (Các s h ng có th b t đu b ng ký t 0; N u có nhi u ph ng ánấ ộ ố ạ ể ắ ầ ằ ự ế ề ươ
đa ra m t ph ng án b t k .)ư ộ ươ ấ ỳ
Ràng bu c:ộ Đ dài xâu S không v t quá 100.ộ ượ
Ví dụ
1
Input Output
3207011864
32
3+2+07+01+1+8+6+4
Bài 2: Đoán tu iổ
Vi t và Nam cùng ch i trò đoán tu i, l n này Vi t ph i đoán tu i mà Nam ch n.ệ ơ ổ ầ ệ ả ổ ọ
Vi t bi t r ng s tu i đó là s nguyên n m trong đo n [1; n]. Đ d dàng h n, m i khiệ ế ằ ố ổ ố ằ ạ ể ễ ơ ỗ
Vi t đa ra m t s x (1 <= x <= n) và cho r ng đó là tu i Nam ch n thì Nam s cho Vi tệ ư ộ ố ằ ổ ọ ẽ ệ
bi t c chung l n nh t c a x và tu i mà Nam ch n.ế ướ ớ ấ ủ ổ ọ
Ví d v i n = 6, Vi t đoán x = 3, Nam tr l i r ng c chung l n nh t c a x và tu i Namụ ớ ệ ả ờ ằ ướ ớ ấ ủ ổ
ch n là 1, nghĩa là tu i Nam ch n không th là 3 ho c 6. Vi t ti p t c đoán x = 2, Nam trọ ổ ọ ể ặ ệ ế ụ ả
l i là 2, nghĩa là tu i Nam ch n không th là 1 ho c 5. Vi t ti p t c đoán x = 4, Nam tr l iờ ổ ọ ể ặ ệ ế ụ ả ờ
là 2, t đây có th đoán đc tu i Nam ch n là 2, trò ch i k t thúc.ừ ể ượ ổ ọ ơ ế
Trong ví d trên, đ tìm ra đáp án, Vi t ph i đoán 3 l n. Tuy nhiên có th tìm ra đáp án chụ ể ệ ả ầ ể ỉ
v i 2 l n đoán, đó là:ớ ầ
- Vi t đoán x = 6, n u Nam tr l i là 1 thì Vi t s đoán ti p x = 1 ho c x = 5, n u Nam trệ ế ả ờ ệ ẽ ế ặ ế ả
l i là 2 thì Vi t s đoán ti p x = 2 ho c x = 4, n u Nam tr l i là 3 ho c 6 thì đáp án chínhờ ệ ẽ ế ặ ế ả ờ ặ
là 3 ho c 6, nh v y ch c n t i đa 2 l n đoán.ặ ư ậ ỉ ầ ố ầ
Bài toán đt ra là v i m t s n cho tr c, hãy tìm s l n đoán ít nh t đ tìm ra đáp án c aặ ớ ộ ố ướ ố ầ ấ ể ủ
Vi t.ệ
Input
G m s nguyên d ngồ ố ươ n (2 <= n <= 10^4)
Output
S l n đoán ít nh t đ tìm ra đáp án c a Vi t.ố ầ ấ ể ủ ệ
Ví dụ
Input Output
6 2
Bài 3: Đng h báo th cồ ồ ứ
Mùa hè đn là lúc h c sinh đc ngh h c, là kho ng th i gian tuy t v i đ vui ch iế ọ ượ ỉ ọ ả ờ ệ ờ ể ơ
th a thích cùng nhau. Th nh ng Huy - m t h c sinh l p 12 chuyên Toán l i mu n t nỏ ế ư ộ ọ ớ ạ ố ậ
d ng nh ng ngày hè r nh r i đ "tu luy n" nh m đt k t qu cao trong k thi HSG s p t i.ụ ữ ả ỗ ể ệ ằ ạ ế ả ỳ ắ ớ
2
C u ta đt ra m t th i gian bi u cho mình và s d ng đng h báo th c đ th c hi n m tậ ặ ộ ờ ể ử ụ ồ ồ ứ ể ự ệ ộ
cách h p lý. Sau m t h i l c l i quanh nhà, c u đã tìm đc m t chi c đng h báo th cợ ộ ồ ụ ọ ậ ượ ộ ế ồ ồ ứ
hi n th b ng đèn LED mà ba c u mua cho t năm ngoái. Không may, do ít s d ng màể ị ằ ậ ừ ử ụ
chi c đng h đã b h ng v ph n hi n th gi . Nó h ng đn n i c u không th đc đcế ồ ồ ị ỏ ề ầ ể ị ờ ỏ ế ỗ ậ ể ọ ượ
th i gian trên đng h mà ch đm đc s v ch LED mà nó hi n th . Vì v y, đ xác đnhờ ồ ồ ỉ ế ượ ố ạ ể ị ậ ể ị
th i gian, c u ph i tìm m t th i đi m mà đng h hi n th có s v ch LED b ng s v chờ ậ ả ộ ờ ể ồ ồ ệ ị ố ạ ằ ố ạ
mà c u đm đc. Do b n ôn thi, c u không có th i gian suy nghĩ. Đây chính là lúc các ậ ế ượ ậ ậ ờ b nạ
giúp Huy đy!ấ
Input
S nguyênố n (0 <= n <= 30) là s v ch LED mà Huy đm đc.ố ạ ế ượ
Output
In ra 5 kí t theo đnh d ngự ị ạ hh:mm là th i đi m mà đng h hi n th có s v ch LED b ngờ ể ồ ồ ể ị ố ạ ằ
n, trong đó hh là gi vàờ mm là phút (0 <= hh < 24, 0 <= mm < 60)
N u có nhi u k t qu in ra k t qu b t kế ề ế ả ế ả ấ ỳ
N u không tìm đc in raế ượ Impossible
Ví dụ
Input Output
23 00:02
3
S GD&ĐT VĨNH PHÚCỞ
TR NG THPT ƯỜ YÊN L C 2Ạ
ĐÁP ÁN KSCL ĐI TUY N H C SINH GI I KH I 12Ộ Ể Ọ Ỏ Ố
Môn:Tin h c ọ L pớ: 12
Năm h c 2017- 2018ọ
Bài 1: (4 đi m)ể
Test D li uữ ệ K t quế ả Đi mể
11100020010
5
1+1+0+0+0+2+0+0+1+0
23207011864
32
3+2+07+01+1+8+6+4 0.25
34520100571
106
45+2+01+00+57+1 0.25
43132977040
1296
313+2+977+04+0 0.25
55549558237
10151
554+9558+2+37 0.25
62233521202
223366
223352+12+02 0.25
71101110421
1101153
1101110+42+1 0.25
82212241203
22122415
22122412+03 0.25
92663400041
266340005
266340004+1 0.25
10 1000000000
1000000000
1000000000
11 2
2
2 0.25
12 123456789
45
1+2+3+4+5+6+7+8+9 0.25
4
13 9999999999
90
9+9+9+9+9+9+9+9+9+9 0.25
14 95821012
10594
9582+1012 0.25
15 87522201
10953
8752+2201 0.25
16 4048602110
116
40+48+6+021+1+0 0.25
5