đề thi hsg cấp tỉnh 2017 - 2018
phần 1 : đề bài
Bài 1/1999 - Trò chơi cùng nhau qua cầu
Bốn
người cần đi qua một chiếc cầu. Do cầu yếu nên mỗi lần đi không quá hai người,
và vì trời tối nên phải cầm đèn mới đi được. Bốn người đi nhanh chậm khác nhau,
qua cầu với thời gian tương ứng là 10 phút, 5 phút, 2 phút và 1 phút. Vì chỉ có
một chiếc đèn nên mỗi lần qua cầu phải có người mang đèn trở về cho những người
kế tiếp. Khi hai người đi cùng nhau thì qua cầu với thời gian của người đi chậm
hơn. Ví dụ sau đây là một cách đi:
- Người 10 phút đi
với người 5 phút qua cầu, mất 10 phút.
- Người 5 phút
cầm đèn quay về, mất 5 phút.
- Người 5 phút đi
với người 2 phút qua cầu, mất 5 phút.
- Người 2 phút
cầm đèn quay về, mất 2 phút.
- Người 2 phút đi
với người 1 phút qua cầu, mất 2 phút.
Thời gian tổng
cộng là 10+5+5+2+2 = 24 phút.
Em hãy tìm cách đi
khác với tổng thời gian càng ít càng tốt, và nếu dưới 19 phút thì thật tuyệt
vời! Lời giải ghi trong tệp văn bản có tên là P1.DOC
Bài 2/1999 - Tổ chức tham quan
(Dành cho học
sinh THCS)
Trong đợt tổ
chức đi tham quan danh lam thắng cảnh của thành phố Hồ Chí Minh, Ban tổ chức
hội thi Tin học trẻ tổ chức cho N đoàn ( đánh từ số 1 đến N) mỗi đoàn đi thăm
quan một địa điểm khác nhau. Đoàn thứ i đi thăm địa điểm ở cách Khách sạn Hoàng
Đế di km (i=1,2,...., N). Hội thi có M xe taxi đánh số từ 1 đến M (M³N) để
phục vụ việc đưa các đoàn đi thăm quan. Xe thứ j có mức tiêu thụ xăng là vj đơn
vị thể tích/km.
Yêu cầu: Hãy chọn N xe để phục vụ việc đưa các đoàn đi thăm quan, mỗi xe
chỉ phục vụ một đoàn, sao cho tổng chi phí xăng cần sử dụng là ít nhất.
Dữ liệu: File văn bản P2.INP:
- Dòng đầu tiên
chứa hai số nguyên dương N, M (N£M£200);
- Dòng thứ hai
chứa các số nguyên dương d1, d2, ..., dN;
- Dòng thứ ba
chứa các số nguyên dương v1, v2, ..., vM.
- Các số trên
cùng một dòng được ghi khác nhau bởi dấu trắng.
Kết quả: Ghi ra file văn bản
P2.OUT:
- Dòng đầu tiên
chứa tổng lượng xăng dầu cần dùng cho việc đưa các đoàn đi thăm quan (không
tính lượt về);
- Dòng thứ i
trong số N dòng tiếp theo ghi chỉ số xe phục vụ đoàn i (i=1, 2, ..., N).
Ví dụ:
|
P2.INP |
|
P2.OUT |
|
3 4 7 5 9 17 13 15 10 |
|
256 2 3 4 |
Bài 3/1999 - Mạng tế bào
(Dành cho học
sinh THPT)
Mạng tế bào có
dạng một lưới ô vuông hình chữ nhật. Tại mỗi nhịp thời gian: mỗi ô của lưới
chứa tín hiệu là 0 hoặc 1 và có thể truyền tín hiệu trong nó cho một số ô kề
cạnh theo một qui luật cho trước. Ô ở góc trên bên trái có thể nhận tín hiệu từ
bên ngoài đưa vào. Sau nhịp thời gian đó, tín hiệu ở một ô sẽ là 0 nếu tất cả
các tín hiệu truyền đến nó là 0, còn trong trường hợp ngược lại tín hiệu trong
nó sẽ là 1. Một ô không nhận được tín hiệu nào từ các ô kề cạnh với nó sẽ giữ
nguyên tín hiệu đang có trong nó. Riêng đối với ô trên trái, sau khi truyền tín
hiệu chứa trong nó đi, nếu có tín hiệu vào thì ô trên trái sẽ chỉ
nhận tín hiệu này, còn nếu không có tín hiệu nào thì ô trên trái cũng hoạt động
giống như các ô khác. ở trạng thái đầu tín hiệu trong tất cả các ô là 0.
Yêu cầu: Cho trước số nhịp thời gian T và dãy tín hiệu vào S là một dãy gồm
T ký hiệu S1, ..., ST, trong đó Si là 0 hoặc 1 thể hiện có tín hiệu
vào, ngược lại Si là X thể hiện không có tín hiệu vào tại nhịp thời gian thứ i
(1£
i £T),
hãy xác định trạng thái của lưới sau nhịp thời gian thứ T.
Dữ liệu: vào từ file văn bản
P3.INP:
- Dòng đầu tiên
chứa 3 số nguyên M, N, T theo thứ tự là số dòng, số cột của lưới và số nhịp
thời gian (1<M, N £ 200; T £ 100);
- Dòng thứ hai
chứa xâu tín hiệu vào S;
- M dòng tiếp
theo mô tả qui luật truyền tin. Dòng thứ i trong số M dòng này chứa N số ai1,
ai2, ..., aiN, trong đó giá trị của aij sẽ là 1, 2, 3, 4, 5, 6, 7, 8
tương ứng lần lượt nếu ô (i, j) phải truyền tin cho ô kề cạnh bên trái, bên
phải, bên trên, bên dưới, bên trên và bên dưới, bên trái và bên phải, bên trên
và bên trái, bên dưới và bên phải (xem hình vẽ); còn nếu ô (i, j) không phải
truyền tín hiệu thì aij = 0.
Kết quả: Ghi ra file văn bản
P3.OUT gồm M dòng, mỗi dòng là một xâu gồm N ký tự 0 hoặc 1 mô tả trạng thái
của lưới sau nhịp thời gian thứ T.
Ví dụ:
|
P3.INP |
|
P3.OUT |
|
2 2 5 101XX 2 4 2 1 |
|
11 01 |
Quá trình biến đổi
trạng thái được diễn tả trong hình dưới đây:
|
0 |
0 |
|
|
1 |
0 |
|
|
0 |
1 |
|
|
1 |
0 |
|
|
1 |
1 |
|
|
1 |
1 |
|
|
|
0 |
0 |
|
|
0 |
0 |
|
|
0 |
0 |
|
|
0 |
1 |
|
|
1 |
0 |
|
|
0 |
1 |
|
|
Bài 4/1999 - Trò chơi bốc sỏi
(Dành cho học
sinh Tiểu học)
Trên
mặt đất có một đống sỏi có 101 viên. Hai em học sinh Hoàng và Huy chơi trò chơi
như sau: Mỗi em đến lượt đi phải bốc ra từ đống sỏi trên tối thiểu là 1 viên và
tối đa là 4 viên. Người thua là người phải bốc viên sỏi cuối cùng. Giả sử Hoàng
là người được bốc trước, Huy bốc sau. Các em thử nghĩ xem ai là người thắng
cuộc, Hoàng hay Huy? Và người thắng cuộc phải suy nghĩ gì và thực hiện các bước
đi của mình ra sao?
Bài 5/1999 - 12 viên bi
(Dành cho học
sinh THCS)
Có 12 hòn bi
giống hệt nhau về kích thước, hình dáng và khối lượng. Tuy nhiên trong chúng
lại có đúng một hòn bi kém chất lượng: hoặc nhẹ hơn hoặc nặng hơn bình thường.
Dùng một cân bàn hai bên, bạn hãy dùng 3 lần cân để tìm ra được viên bi đó. Cần
chỉ rõ rằng viên bi đó là nặng hơn hay nhẹ hơn.
Viết chương
trình mô phỏng việc tổ chức cân các hòn bi trên. Dữ liệu về hòn bi kém chất
lượng do người sử dụng chương trình nắm giữ. Yêu cầu trình bày chương trình đẹp
và mỹ thuật.
Bài 6/1999 - Giao điểm các đường thẳng
(Dành cho học
sinh THPT)
Trên mặt phẳng
cho trước n đường thẳng. Hãy tính số giao điểm của các đường thẳng này. Yêu cầu
tính càng chính xác càng tốt.
Các đường thẳng
trên mặt phẳng được cho bởi 3 số thực A, B, C với phương trình Ax + By + C = 0,
ở đây các số A, B không đồng thời bằng 0.
Dữ liệu vào của
bài toán cho trong tệp B6.INP có dạng sau:
- Dòng đầu tiên
ghi số n
- n dòng tiếp
theo, mỗi dòng ghi 3 số thực A, B, C cách nhau bởi dấu cách.
Kết quả của bài
toán thể hiện trên màn hình.
Bài 7/1999 - Miền mặt phẳng chia bởi các đường
thẳng
(Dành cho học
sinh THPT)
Xét bài toán
tương tự như bài 6/1999 nhưng yêu cầu tính số miền mặt phẳng được chia bởi n đường
thẳng này:
Trên mặt phẳng
cho trước n đường thẳng. Hãy tính số miền mặt phẳng được chia bởi các đường
thẳng này. Yêu cầu tính càng chính xác càng tốt.
Các
đường thẳng trên mặt phẳng được cho bởi 3 số thực A, B, C với phương trình Ax +
By + C = 0, ở đây các số A, B không đồng thời bằng 0.
Dữ liệu vào của
bài toán cho trong tệp B7.INP có dạng sau:
- Dòng đầu tiên
ghi số n
- n dòng tiếp
theo, mỗi dòng ghi 3 số thực A, B, C cách nhau bởi dấu cách.
Kết quả của bài
toán thể hiện trên màn hình.
){kind=link}
0 Nhận xét