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

Đề thi Olympic Tin học sinh viên lần thứ XV khối Siêu cúp (Năm 2006) cung cấp cho thí sinh các bài tập giải quyết vấn đề lập trình gồm: đoạn thẳng; truyền thông trên mạng; bậc tăng của hoán vị; bức phù điêu; . 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Ứ XV 2006 Khối thi Siêu cúp Thời gian làm bài 180 phút Ngày thi 06-05-2006 Nơi thi TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI Tªn file Tªn file Tªn file H n chÕ thêi Tªn bµi ch- ng tr nh d liÖu kÕt qu gian cho mçi test Đoạn thẳng SEGMENTS. 1 giây Truyền thông trên mạng MESHNET. 1 giây Bậc tăng của hoán vị INCRDEG. 4 giây Bức phù điêu TRIPIC. 2 giây 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. H y lËp tr nh gi i c c bµi sau y Bài 1. Đoạn thẳng Trên mặt phẳng toạ độ cho hình chữ nhật xác định bởi toạ độ đỉnh dưới trái là 0 0 và toạ độ góc trên phải là w h . Cho n đoạn thẳng song song với trục toạ độ mỗi đoạn thẳng xác định 3 bởi toạ độ các điểm đầu và cuối. Các đoạn thẳng có thể cắt 1 1 nhau trùng nhau đè lên nhau hoặc suy biến thành một điểm. 2 Các toạ độ theo giá trị tuyệt đối không vượt quá 10 000. Các đoạn thẳng này chia hình chữ nhật đã cho thành một số phần. 5 2 1 Hãy xác định diện tích các phần đó. Dữ liệu Vào từ file văn bản 0 1 2 3 Dòng đầu tiên chứa 2 số nguyên w h Dòng thứ 2 chứa số nguyên n Dòng thứ i trong n dòng sau chứa 4 số nguyên ai bi ci di xác định đoạn thẳng thứ i. Hai số liên tiếp trên cùng dòng được ghi cách nhau bởi dấu cách. Kết quả Đưa ra file văn bản dãy các diện tích theo thứ tự không tăng mỗi số trên một dòng. Ví dụ 3 3 5 3 2 1 3 1 1 1 1 2 4 2 1 2 0 2 6 Hạn chế 1 w h 10 000 0 n 50. 1 3 Trang Bài 2. Truyền thông trên mạng Một hệ thống máy tính được nối lại thành một mạng theo kiểu lưới ô vuông đơn vị gồm 2000 dòng và 2000 cột. Các dòng được đánh số từ 0 đến 1999 từ dưới lên trên. Các cột được đánh số từ 0 đến 1999 từ trái qua phải. Nút lưới nằm trên giao của dòng i cột j có toạ độ i j . Các máy tính được đặt trên các nút lưới. Các cạnh của các ô vuông của lưới là các cáp nối cho phép truyền tin hai chiều tại một thời điểm có thể có một số