Tài liệu Dethi_chonqg_2015_v2

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 -