Đề 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!
Nội dung trích xuất từ tài liệu:
Đề thi Olympic Tin học sinh viên lần thứ XV khối Siêu cúp (Năm 2006) 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.??? SEGMENTS.INP SEGMENTS.OUT 1 giây Truyền thông trên mạng MESHNET.??? MESHNET.INP MESHNET.OUT 1 giây Bậc tăng của hoán vị INCRDEG.??? INCRDEG.INP INCRDEG.OUT 4 giây Bức phù điêu TRIPIC.??? TRIPIC.INP TRIPIC.OUT 2 giâyDÊu ??? ®-îc thay thÕ bëi ®u«i ngÇm ®Þnh cña ng«n ng÷ ®-îc sö dông ®Ó cµi ®Æt ch-¬ngtr×nh.H·y lËp tr×nh gi¶i c¸c bµi sau ®©y:Bài 1. Đoạn thẳngTrê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 3bởi toạ độ các điểm đầu và cuối. Các đoạn thẳng có thể cắt 1 1nhau, trùng nhau, đè lên nhau hoặc suy biến thành một điểm. 2Cá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 1Hãy xác định diện tích các phần đó.Dữ liệu: Vào từ file văn bản SEGMENTS.INP: 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 SEGMENTS.OUT 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ụ: SEGMENTS.INP SEGMENTS.OUT 3 3 5 3 2 1 3 1 1 1 1 2 4 2 1 2 0 2 6Hạn chế: 1 ≤ w, h ≤ 10 000; 0 ≤ n ≤ 50. 1/3 TrangBài 2. Truyền thông trên mạngMộ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 2000dò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 đánhsố 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ácmá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 chophép truyền tin hai chiều (tại một thời điểm có thể có một số lượng không hạn chế các gói tinđược truyền đồng thời trên cáp theo cả hai chiều). Các gói tin đi qua mỗi cạnh như vậy mấtmột đơn vị thời gian. Các máy tính luôn ở trạng thái sẵn sàng nhận tin. Tại thời điểm 0 có Nmáy tính trong mạng thực hiện việc truyền tin và dù sớm hay muộn thì các gói tin do chúngtruyền đi sẽ đến tất cả các máy trong mạng.Yêu cầu: Hãy tính thời điểm sớm nhất để cho có ít nhất một máy trong mạng nhận được tấtcả các gói tin do N máy này truyền đi.Dữ liệu: Vào từ file văn bản MESHNET.INP gồm một dòng: số đầu tiên trên dòng là sốnguyên N, tiếp theo là N cặp số nguyên tương ứng là các toạ độ của N máy thực hiện việctruyền tin. Hai số liên tiếp được ghi cách nhau bởi dấu cách.Kết quả: Ghi ra file văn bản MESHNET.OUT thời điểm sớm nhất tìm được.Ví dụ: MESHNET.INP MESHNET.OUT Hình vẽ minh hoạ 4 0 1 0 2 4 0 4 3 4Hạn chế: 2  N  1000.Bài 3. Bậc tăng của hoán vịXét dãy p = p(1), p(2), ..., p(N) là một hoán vị của các số tự nhiên 1, 2, … , N. Ta nói hoán vịp chứa dãy con tăng độ dài k nếu như tìm được các số 1 ≤ i1 < i2 < … < ik ≤ N sao cho p(i1)