Đề thi học sinh giỏi lớp 12 THPT tỉnh Quảng Bình năm học 2012 - 2013 môn Tin học - Vòng 2 (Có đáp án

[DOWNC="http://w6.mien-phi.com/data/file/2013/thang05/08/Dethi-HSG-L12-2013-QuangBinh-Tinhoc-V2.doc"]TẢI TÀI LIỆU[/DOWNC]

Đề thi học sinh giỏi lớp 12 THPT tỉnh Quảng Bình năm học 2012 - 2013 môn Tin học - Vòng 2 (Có đáp án) - Sở GD&ĐT Quảng Bình

[TABLE]
[TBODY]
[TR]
[TD]
SỞ GIÁO DỤC VÀ ĐÀO TẠO
QUẢNG BÌNH
(Đề thi chính thức)
[/TD]
[TD]
KỲ THI CHỌN HỌC SINH GIỎI TỈNH LỚP 12 THPT
NĂM HỌC 2012-2013
(Khóa ngày 11 tháng 10 năm 2012)
[/TD]
[/TR]
[/TBODY]
[/TABLE]
MÔN THI: TIN HỌC - Vòng 2
Thời gian làm bài: 180 phút (không kể thời gian giao đề)
--------------------------------------------------------------------------------
Sử dụng ngôn ngữ lập trình Turbo Pascal để lập trình giải các bài toán sau:

Câu 1: (3,0 điểm) Tính diện tích tam giác. DT.PAS.
Trong hệ trục tọa độ Decac, cho ba điểm không thẳng hàng A, B, C có tọa độ: A(x[SUB]1[/SUB], y[SUB]1[/SUB]); B(x[SUB]2[/SUB], y[SUB]2[/SUB]); C(x[SUB]3[/SUB], y[SUB]3[/SUB]).
Yêu cầu: Tính diện tích tam giác ABC.
Dữ liệu vào: Cho trong file văn bản DT.INP, có cấu trúc 3 dòng, mỗi dòng chứa hai số nguyên xi yi, là tọa độ của một đỉnh của tam giác ABC. Các số được ghi cách nhau ít nhất một dấu cách. (-2000 ≤ x[SUB]i[/SUB], y[SUB]i[/SUB] ≤ 2000)
Dữ liệu ra: Ghi ra file văn bản DT.OUT, theo cấu trúc:
- Dòng 1: Ghi diện tích tam giác tìm được. Làm tròn kết quả đến một chữ số sau dấu ngăn cách thập phân.
Câu 2: (3,5 điểm) Đặt vé vào sân NouCamp NOUCAMP.PAS
NouCamp là một sân bóng lớn. Sân có N ghế ngồi, các ghế được đánh số thứ tự từ 1 đến N.
Tối nay, sân NouCamp sẽ diễn ra trận đấu giữa hai đội bóng lớn của thế giới: Barcelona và Real Madrid. Hiện nay, một số ghế trên sân đã được khán giả đặt mua làm chỗ ngồi.
Yêu cầu: Hãy kiểm tra xem trên sân còn những ghế nào chưa được mua vé đặt chỗ.
Dữ liệu vào: Cho trong file văn bản NOUCAMP.INP, có cấu trúc như sau:
- Dòng 1: Ghi hai số nguyên dương N M. Trong đó: N là số lượng ghế có trong sân. M là số lượng ghế đã được khán giả mua vé đặt chỗ. Hai số được ghi cách nhau ít nhất một dấu cách. (N chia hết cho 8; 1 ≤ N ≤ 400000; 1 ≤ M ≤ N).
- Dòng 2: Ghi M số nguyên dương a1, a2, , am, là chỉ số của M ghế đã được khán giả mua vé đặt chỗ. Các số được ghi cách nhau ít nhất một dấu cách.
Dữ liệu ra: Ghi ra file văn bản NOUCAMP.OUT, theo cấu trúc như sau:
- Dòng 1: Ghi K số nguyên dương b1, b2, , bk, là chỉ số của các ghế trên sân chưa được mua vé đặt chỗ (K = N-M). Các số được ghi theo thứ tự tăng dần và cách nhau ít nhất một dấu cách.
Câu 3: (3,5 điểm) Xếp hộp lồng nhau XEPHOP.PAS
Bé Ri tuy còn nhỏ nhưng là một cô bé rất xinh xắn và chăm chỉ. Mẹ bé Ri là chủ một cửa hàng. Hàng ngày, cửa hàng của mẹ loại ra rất nhiều hộp giấy hình hộp chữ nhật. Bé Ri thường giúp mẹ xếp những hộp giấy này lồng vào nhau cho gọn.
Giả sử có N hộp giấy, các hộp được đánh số từ 1 đến N. Với mỗi hộp giấy, bé Ri biết được chính xác độ dài hai cạnh đáy của hộp là a và b.
Yêu cầu: Hãy giúp bé Ri xếp các hộp sao cho số lượng các hộp lồng vào nhau là lớn nhất.
Dữ liệu vào: Cho trong file văn bản XEPHOP.INP, có cấu trúc như sau:
- Dòng 1: Ghi số nguyên dương N, là số lượng hộp giấy. (1 ≤ N ≤ 1000)
- N dòng tiếp theo: Mỗi dòng ghi hai số nguyên dương ai bi, là độ dài hai cạnh đáy của hộp giấy thứ i. (1 ≤ ai, bi ≤ 32767)
Dữ liệu ra: Ghi ra file văn bản XEPHOP.OUT theo cấu trúc như sau:
- Dòng 1: Ghi số nguyên dương M là số lượng các hộp giấy lồng nhau tìm được.
- Dòng 2: Ghi M số nguyên dương, là chỉ số của M hộp giấy theo thứ tự từ ngoài vào trong của một cách xếp hộp.