tailieunhanh - Đề thi học sinh giỏi quốc gia 2010

Đề thi học sinh giỏi quốc gia 2010 là tài liệu mang tính chất tham khảo, giúp ích cho các bạn có dự định ôn thi học sinh giỏi quốc gia, tai flieeuj hay để các bạn tham khảo. | Bộ GIÁO DỤC VÀ ĐÀO TẠO KÌ THI CHỌN HỌC SINH GIỎI QUÓC GIA ĐỀ THI CHÍNH THỨC L íp 12 THPT NÄM 2010 Môn TIN HỌC Thời gian 180 phút không kể thời gian giao đề Ngày thi 11 3 2010 Đề thi có 04 trang gồm 03 bài BẢN CHÍNH TÔNG QUAN BÀI THI Tên bài File chương trình File dữ liệu vào File kết quả Bài 1 Dãy con chung không lỉẻn kề dài nhất LNACS. Bài 2 Ổn định STABLE. Bài 3 Mẵ số thuế TAXID. Dấu được thay thế bởi PAS hoặc CPP của ngôn ngữ lập trinh được sử dụng tuvng ứng là Pascal hoặc C-H-. Hãy lập trình giãi các bài toán sau Bài 1. Dãy con chung không liền kề dài nhất ổ điểm Dãy c C C2 . Ck được gọi là dãy con không liền kề của dãy A 1 02 am nếu c cồ thể nhận được bằng cách chọn một dẫy các phần tử không liền kề cùa A nghĩa là tìm được dây các chi số Z Ì2 ikSão cho 1 0 Ì2 ìkZ m i Ỉ2 - 1 Ì2 h - 1 .ik-i ik 1 CI ai c2 ai2 ck ai Ta gọi độ dài cùa dãy là số phần tử của nó. Cho hai dãy A ữ Ỡ2 Oịịị và B b b2 . b Dãy c được gọi là dãy con chung không liền kề của hai dãy A và B nếu như nó vừa là dây con không liền kề của A vừa là dãy con không liền kề của B. Yêu cầu Cho hai dãy sổ A và B. Hãy tìm độ dài của dãy con chung không liền kề dài nhất của hai dãy đã cho. Dữ liệu Vào từ file văn bản Dòng đầu tiên chứa hai số nguyên dưong m và n 2 m n 103 được ghi cách nhau bởi dấu cách lần lượt là số lượng phần tử của dãy A và däy B. Dòng thứ i trong m dòng tiếp theo chứa số nguyên không âm ữ ữ 104 i - 1 2 . m. Dòng thứ trong n dòng tiếp theo chứa số nguyên không âm bj bj 1 o4 j 1 . Kết quả Ghi ra trên một dòng của file văn bản độ dài cùa dãy con chung không liền kề dài nhất của hai dãy A và B. Trang 1 4 Ví dụ 4 5 4 9 2 4 1 9 7 3 4 2 Ràng buộc 50 số tests ứng với 50 số điểm của bài có 1 n 100. Bài 2. ổn định 7 điểm Trong mạng xã hội mỗi trang web được tổ chức trên một máy tính thành viên và cung cấp dịch vụ truy nhập tới một số trang web khác. Để truy nhập tới một trang web nào đó không