TỈNH ĐỒNG THÁP
ĐỀ THI CHỌN HỌC SINH GIỎI QUỐC GIAI NĂM 2014-2015
VÒNG 2
Câu 1. (7điểm) THẦN ĐỒNG ĐẤT VIỆT.
Trạng Tí trong bộtruyện “Thần đồng đất Việt” là một nhân vật nổi tiếng thông minh,
có khảnăng xửlí các tình huống một cách tài tình, khéo léo. Bạn của Tí gồm có: Sửu,
Dần Béo và CảMẹo. Một ngày nọ, bọn họcùng chơi một tròchơi như sau: Sửu soạn ra
một bộgồm n câu hỏi và đốCảMẹo, nếu trảlời đúng sẽđược 1 điểm , trảlời sai
thìkhông có điểm. Tuy nhiên, Tí thấy rằng tròchơi này chưa hứng thú lắm nên cậu ta
bèn chọn ra một con sốmay mắn, đặt là k và nhờDần Béo tham gia và tính điểm như
sau: Dần Béo chọn k hòn sỏi và cứmỗi lần CảMẹo chọn đúng 1 câu thìsau khi điểm
sốtăng lên 1, CảMẹo sẽđược tăng thêm 1 hòn sỏi đểđánh dấu. Khi Cả Mẹo có đủk hòn
sỏi thìsẽtrảđủsốhòn sỏi cho Dần Béo và ngay lúc đấy, sốđiểm của CảMẹo sẽđược tăng
gấp đôi Tròchơi sẽtiếp tục như thế. Tuy nhiên, nếu trảlời sai bất cứcâu nào thìCảMẹo
cũng trảlại tất cảsốhòn sỏi nhận được. Ban đầu, điểm của CảMẹo là 0 và không có
hòn sỏi nào. Cuối cùng tổng kết lại sau n câu hỏi, CảMẹo đãtrảlời dúng được m câu.
Rõràng là với cách tính điểm trên và lượng câu trảlời đúng như thếthìCảMẹo có
thểnhận được nhiều điểm sốkhác nhau tùy thuộc vào thứtựtrảlời đúng sai của các câu
hỏi của bạn ấy. Nhưng không may CảMẹo lại có sốđiểm thấp nhất (tính trong tất
cảcác tình huống có thểxảy ra).
Câu 2. (6 điểm) DIỄN ĐÀN TIN HỌC
Việt là một người rất thích diễn đàn ddth.com vì với việc thảo luận cùng các bạn yêu
Tin học gần xa, bạn ấy có thể học được rất nhiều điều bổ ích . Mỗi ngày, Việt thường
dành khoảng vải chục phút đọc thong tin trong đó và cập nhập tin tức mới.Trân diễn
đàn có nhiều chủ đề và có thể có nhiều bài viết. Diễn đàn này có hỗ trợ cho người
tham gia một danh sách n chủ đề mới cập nhật, tu712c là chủ đề vừa được đăng hoặc
chủ đề cũ nhưng cói bài viết mới. Mỗi khi một chủ đề nào đó mới được tạo ( cũng có
thể coi là có bài viết mới) hoặc chủ đề cũ có bài viết mới được gửi vào, nó đứng đầu
trong danh sách . Giả sử rằng không có bài viết nào được đăng cùng lúc. Môt ngày nọ
trước khi đi học Việt lên đọc tất cả các chủ đề nằm trong danh sách ở trang chủ diễn
đàn. Đến trưa về Việt bất ngờ khi thấy trong danh sách không có chủ đề mới nào
nhưng vị trí của chúng đã bị thay đổi, điều nay có nghĩa là một số bài viết mới đã
được gửi lên trong các chủ đề cũ đó .
Để tiết kiệm thời gian, Việt chỉ muốn đọc các chủ đề chắn chắc có bài viết mới , việc
chắc chắn ở đây là xét trên tất cả tình huống có thể
Yêu cầu: Hãy giúp Việt xác định số lương chủ đề bài chắc chắn có bài viết mới
Dữ liệu Trong file DIENDAN.INP, dòng đầu tiên gồm 1 số nguyên dương n cho biết
số lượng chủ đề có trong danh sách ở trang chủ với 0< n<=100. Dòng thứ hai gồm n
số nguyên dương a1,a2....,an
hai số kề nahu cách nhau bởi khoảng chắn , cho biết vị trí cũ của chủ đề tương ứng
hay nói cách khác ai chính là vị trí cũ thú i mà Việt đã thấy trước đó
Kết quả
In ra file DIENDAN.OUT một số duy nhất là số lượng chủ đề chắc chắn có bài viết
mới
DDTH.INP
DDTH.OUT
5
2
52134
4
2
1324
Giải thích Trong test đầu tiên chủ đề 1 trước đó ở vị trí số 5 , chủ đề 2 trước đó ở vị
trí thứ 2 , chủ đề 3 trước đó ở vị trí đầu tiên,... Điều bày cgi thấy rằng chủ đề thý 2 vả
thứ 5 chắc chắn co bài viêt mới . Điền này tương ứng với tin huống sau : ban đầu ,
danh sách chủ đề theo thứ tự 1,2,3,4,5: chủ đề 2 được cập nhật mới trở thành 2,1,3,4,5
rồi chủ đề 5 được cập nhật, trở thành 5,2,1,3,4 chủ đề 3,4 không được cập nhật ; do đó
chủ đề 1,3,4 là không chắc chắn có bài viết mới . Bằng cách lập luận tương tự trong
tset thứ 2, chỉ có 2 chủ đề 1 và 3 chắc chắn có bài viết mới.
Câu 3. Đi tìm kho báo (7điểm)
….
Thể được coi là con robot di chuyển qua bao nhiêu lần cũng được. Ban đầu nhóm
thám hiểm đã đưa con rovot đến được một trong các mảng dất trong danh sách. Mỗi
lần muốn đến một trong các mảng đất khác mà không thể tư di chuyển theo một
hướng lên, xuống, trái, phải từ mảng đất nào trước đó được thì nó cần có sự trợ giúp
của nhóm thám hiểm bằng cách chèo một chiếc thuyền độc mộc đưa nó băng qua khu
đầm lầy và đến vị trí nó cần. Giả sử tọa độ cảu tất cả các mảng đất là các số nguyên
không âm và hướng di chuyển của con robot sẽ song song với trục tung hoặc trục
hoành.
Yêu cầu: Hỏi để di chuyển qua hết các mảng đất thì số lần ít nhất mà nhóm thám hiểm
cần giúp con robot là bao nhiêu (không kể lần đầu tiên)?
Dữ liệu vào. Trong file KHOBAU.INP gồm có 2 dòng. Dòng đầu tiên là một số
nguyên dương n chỉ số lương mảng dất có trong danh sách của rcon robot. Trong n
dòng tiếp theo với 0
- Xem thêm -