Đề thi Toán - Tin quốc tế

Cùng tham khảo đề thi học sinh giỏi môn Toán giúp các em ôn tập lại các kiến thức đã học, đánh giá năng lực làm bài của mình và chuẩn bị kì thi học sinh giỏi được tốt hơn với số điểm cao như mong muốn.
Nội dung trích xuất từ tài liệu:
Đề thi Toán - Tin quốc tế Bai toan 1-991. Cửa hàng bán hoaBài toánTại một cửa hàng người ta muốn cắm một số loài hoa vào các chậu hoa nhỏ. Có tất cả F loại hoavà V chậu hoa (F Bai Toan 3-993. Thành phố ngầmBài toánBản đồ một thành phố ngầm được biểu diễn bởi một lưới ô vuông. Các ô vuông mở ký hiệu là O,các ô vuông tường ký hiệu là W. Bạn sẽ xuất phát tại một vị trí được gọi bởi thủ tục (hàm số)start. Bạn sẽ phải tìm hiểu và di chuyển trong thành phố bởi hai thủ tục (hàm số) look và move.Hàm look(dir) với dir chỉ hướng bao gồm N, S, E và W chỉ ra các hướng Bắc, Nam, Đông,Tây. Hàm này sẽ trả lại các giá trị O hay W nếu ô bên cạnh theo hướng dir có giá trị O hay W.Bạn sẽ dùng thủ tục move(dir) để chuyển động sang các ô vuông bên cạnh của lưới. Tất nhiên bạnchỉ được phép đi vào các ô vuông mở.Nhiệm vụ của bài toán là phải tìm ra vị trí xuất phát ban đầu của bạn sau ít lần sử dụng hàm looknhất. Khi đã tìm thấy bạn phải thông báo chúng bằng cách gọi thủ tục finish (x,y) với x, y là toạ độcủa vị trí tìm được.Hạn chế kỹ thuật • 3 Hướng dẫn cho chương trình PascalBạn phải có dòng sau trong chương trình:uses undertpu;Unit này chứa các hàm và thủ tục sau:Procedure start; {cần phải gọi đầu tiên}function look(dir: char):char;procedure move(dir:char);procedure finish(x,y:integer); {phải gọi cuối cùng }Hướng dẫn cho chương trình C/C++Bạn phải có dòng sau trong chương trình:#include under.hTệp này chứa các hàm sau:void start(void); /* cần phải gọi đầu tiên */char look(char);void move(char);void finish(int, int); /* phải gọi cuối cùng */Khi tạo project có tên under, bạn phải bổ sung vào project chương trình của bạn và thư viện cáctương tác với tên underobj.obj. Chú ý nên sử dụng mô hình bộ nhớ LARGE để dịch chương trình. Page 2 3Trắc nghiệmChương trình của bạn chỉ được phép chạy trong 5 giây.Để đạt được điểm tối đa A, số các lần gọi hàm look, x, của chương trình cần phải nhỏ hơn hoặcbằng M là số đ-a ra bởi chương trình kiểm tra. Chú ý rằng M được chọn lớn hơn minimum. Số Mđược chọn không phụ thuộc vào hướng và thứ tự của việc tìm kiếm. Bạn có thể đạt điểm khi sốlần gọi hàm look lớn hơn M như-ng nhỏ hơn 2M. Số điểm đạt được sẽ là tròn số của công thứcsau đây:Các lỗi khác do chương trình tạo ra đều sẽ bị 0 điểm.Thử nghiệm chương trìnhĐể chạy thử chương trình, bạn hãy tạo một text file có tên place.txt bao gồm một dòng có chứa tọađộ của một vị trí trên bản đồ. Bạn hãy chạy chương trình và xem kết quả trong tệp result.txt. Fileresult.txt chứa hai dòng, dòng đầu tiên ghi hai toạ độ x và y để gọi thủ tục finish(x,y). Dòng thứhai ghi dòng chữ You used look nnn times (Bạn đã dùng hàm look nnn lần). Chú ý rằng việcthử này chỉ kiểm tra tính tương thích của chương trình với các thư viện được tạo ra chứ tuyệtnhiên không liên quan gì đến lời giải thực sự của bài toán. Page 3 Bai toan 2-992. Các mã ẩnBài toánXét tập các mã, mỗi mã là một từ có phân biệt chữ in hoa và chữ in thường chỉ bao gồm các chữcái tiếng Anh. Ta định nghĩa dãy phủ của một mã là xâu ký tự có chứa tất cả các chữ cái của mãđược xuất hiện đúng theo thứ tự và có ký tự đầu tiên và cuối cùng là của mã. Ví dụ AuLvL là dãyphủ của ALL. Hai xâu con được gọi là không gối chồng lên nhau nếu vị trí bắt đầu của xâu nàylớn hơn vị trí cuối của xâu kia hoặc ngược lại.Cho trước một văn bản text và một tập hợp các mã. Một nghiệm của bài toán là một tập hợp cácphần tử, một phần tử bao gồm một mã và một dãy phủ của mã đó thoã mãn các điều kiện sau:a) Các dãy phủ trên là không gối chồng lên nhau từng đôi một.b) Mỗi dãy phủ có độ dài tệp này. • File text.inp chứa dãy các ký tự (kết thúc bởi ký tự xuống dòng, sau đó là ký tự kết thúc file), file này không chứa dấu cách.OutputOutput file là file text codes.out. • Dòng đầu tiên ghi số tổng chiều dài các mã của nghiệm bài toán • Các dòng tiếp theo mỗi dòng là phần tử của nghiệm. Mỗi dòng bao gồm ba số tự nhưiên i, s, e. Với i là số thứ tự mã, s,e là vị trí đầu và cuối của dãy phủ t-ơng ứng của mã này trong văn bản. Thứ tự các hàng này không quan trọng.Ví dụwords.inp4RuNRaBbitHoBbitStoPcodes.out122 9 211471 24 28text.inpStXRuYNvRuHoaBbvizXztNwRRuuNNP(Chú ý: Đoạn mã ẩn thu được từ văn bản trên sẽ là RuN RaBit RuN. (Một phương án khác cóthể là RuN HoBbit RuN). Đoạn mã này không thể hiện ra ở output.)Trắc nghiệmChương trình của bạn chỉ được chạy trong 10 giây. Page 2OutputĐầu ra là file text có tên flower.out gồm 2 dòng: • Dòng đầu tiên ghi tổng số điểm thẩm mỹ của cách xếp. • Dòng thứ hai ghi lần l-ợt F số, số thứ k ghi số chậu hoa của loài hoa thứ k đã xếp.Ví dụflower.inp3 57 23 -5 -24 165 21 -4 10 23-21 5 -4 -20 20flower.out532 4 5Trắc nghiệmChương trình của bạn chỉ được chạy trong hai giây. Page 2 Bai toan 1-981. ContactTiến sỹ Astro Insky làm việc ở một trung tâm thiên văn học. Gần đây, bà ta phát hiện thấy nhữngsóng ngắn rất kỳ lạ phát ra trực tiếp từ trung tâm giải ngân hà. Liệu những sóng kỳ lạ này có mangtheo những sinh vật sống thông minh từ ngoài hành tinh đến không? Hay đó chỉ là những hoạtđộng bình thường của tâm các hành tinh?Bài toánBạn phải giúp tiến sỹ Insky tìm ra câu trả lời bằng cách cung cấp các công cụ phân tích mẫu bit dữliệu trong các file bà ghi lại được. Tiến sỹ Insky muốn tìm các chiều dài chuỗi bit giữa A và B,chúng được lặp lại nhiều lầ ...