tailieunhanh - Đề thi Olympic Tin học sinh viên lần thứ XVIII khối Siêu cúp (Năm 2009)

Đề thi Olympic Tin học sinh viên lần thứ XVIII khối Siêu cúp (Năm 2009) cung cấp cho thí sinh các bài toán lập trình nhằm giải quyết các vấn đề sau: tổng trung vị; vi rút cúm; tùy chọn; . Mời các bạn cùng tham khảo chi tiết nội dung đề thi! | OLYMPIC TIN HỌC SINH VIÊN LẦN THỨ XVIII 2009 Khối thi Siêu cúp Thời gian làm bài 180 phút Ngày thi 08-10-2009 Nơi thi ĐẠI HỌC NHA TRANG Tên file Tên file Tên file Hạn chế thời gian Tên bài chương trình dữ liệu kết quả cho mỗi test Tổng trung vị MEDSUM. 2 giây Vi rút cúm VIRUS. 2 giây Tuỳ chọn OPTION. 2 giây Chú ý Dấu được thay thế bởi đuôi ngầm định của ngôn ngữ được sử dụng để cài đặt chương trình. Thí sinh phải nộp cả file mã nguồn của chương trình và file chương trình thực hiện chương trình đã được biên dịch ra file .exe . Hãy lập trình giải các bài sau đây Bài 1. Tổng trung vị Cho N dãy số không giảm A1 A2 AN mỗi dãy gồm L số nguyên dãy số được gọi là không giảm nếu mỗi phần tử đứng sau là lớn hơn hoặc bằng phần tử đứng trước . Xét hai dãy Ai và Aj 1 i j N ta gọi dãy gộp ký hiệu là Aij của hai dãy Ai Aj là dãy gồm tất cả 2L phần tử của hai dãy Ai Aj được sắp xếp theo thứ tự không giảm và phần tử đứng ở vị trí thứ L trong dãy gộp được gọi là phần tử trung vị của nó. Ví dụ Xét hai dãy số Ai 1 3 4 5 6 Aj 0 1 5 6 7 . Khi đó dãy gộp Aij từ hai dãy đã cho là 0113455667 có phần tử trung vị là 4. Yêu cầu Tính tổng của tất cả các phần tử trung vị của tất cả các dãy gộp Aij với 1 i lt j N. Dữ liệu Vào từ file văn bản Dòng đầu tiên chứa hai số N và L 2 N 200 1 L 20000 Dòng thứ i trong số N dòng tiếp theo chứa L số nguyên là các phần tử của dãy thứ i trong số N dãy đã cho. Giả thiết là các phần tử của các dãy số là các số nguyên có trị tuyệt đối không vượt quá 109. Hai số liên tiếp trên cùng một dòng trong file dữ liệu được ghi cách nhau bởi ít nhất một dấu cách. Trang 1 4 Khối Siêu cúp - 2009 Kết quả Ghi ra file văn bản giá trị σ mod 109 là phần dư trong phép chia σ cho 109 trong đó σ là tổng của tất cả các phần tử trung vị của tất cả các dãy gộp Aij với 1 i lt j N. Lưu ý Có 50 số test thoả mãn 2 N 100 1 L 300. Giải đúng các test này thí sinh được ít nhất 50 số điểm tối đa cho toàn bộ .