Đề thi Tin học trẻ tỉnh Đồng Tháp năm 2012 - Bảng C - Cấp THPT

HỘI THI TIN HỌC TRẺ TỈNH ĐỒNG THÁP NĂM 2012

Đề thi: Thực hành – Bảng C - cấp THPT
Ngày thi: 08/06/2012 - Thời gian: 120 phút

TỔNG QUAN BÀI THI:

BÀI 1 (6 điểm) DÂY CHUYỀN SẢN XUẤT

Nhà máy Bích Chi cần kết hợp N công việc thành một dây chuyền sản xuất. Công việc thứ i cần a_i ngày công. Mỗi công đoạn sản phẩm là kết hợp 2 công việc liên tiếp lại với nhau thành một công việc với chi phí cho công đoạn này bằng tổng ngày công của 2 công việc đó.

- Yêu cầu: Bạn hãy giúp nhà máy ghép N công việc đó thành dây chuyền bằng N-1 công đoạn sản phẩm sao cho tổng chi phí các công đoạn là nhỏ nhất.

- Dữ liệu vào: từ tệp văn bản SXUAT.INP có dạng:

+ Dòng đầu ghi số N (1<=N<=100) là số công việc.

+ Dòng thứ i trong N dòng tiếp theo ghi số nguyên dương a_i là số ngày công của công việc thứ i (a_i < 1000).

- Kết quả: ghi ra tệp văn bản SXUAT.OUT có một số nguyên dương là chi phí nhỏ nhất tìm được.

BÀI 2 (7 điểm) PHÒNG THI

Trong một kỳ thi, giám thị lần lượt gọi tên thí sinh vào phòng thi, thí sinh được gọi tên bước vào phòng thi tìm đúng chỗ ngồi của mình. Thí sinh vào phòng thi theo lối đi ở mỗi hàng ghế (được đánh số thứ tự từ1, từ trên xuống) thí sinh dừng lại đúng 1 giây (hoặc lâu hơn nếu phía trước có một thí sinh khác) cho đến khi thí sinh đến đúng hàng ghế của mình và dừng lại đúng 5 giây (có thể có nhiều thí sinh ngồi cùng một hàng ghế).

Trong mỗi giây trên lối đi tại một hàng ghế chỉ có thề có một thí sinh, bỏ qua thời gian thí sinh di chuyền từ hàng ghế này đến hàng ghế kia.

- Yêu cầu: Tính thời gian cần thiết để giám thị gọi tất cả các thí sinh vào phòng thi và tất cả các thí sinh đã ngồi vào dúng vị trí.

- Dữ liệu vào: từ tệp văn bản PTHI.INP có dạng:

+ Dòng đầu tiên ghi số nguyên N , là số thí sinh (1 ≤N ≤100).

+ Dòng i+1 chứa số nguyên R_i là số hàng ghế mà ở đó thí sinh thứ i phải ngồi (1 ≤ Ri ≤ 1000).

- Kết quả: ghi ra tệp văn bản PTHI.OUT có một số nguyên (tính bằng giây), là thời gian theo yêu cầu của bài.

BÀI 3 (7 điểm) HÌNH VUÔNG

Trên mặt phẳng cho N hình vuông với các cạnh song song với hệ trục toạ độ được đánh số từ 1 đến N (1 ≤ N ≤ 2000). Hình vuông thứ i được cho bởi toạ độ góc trái dưới (x_i,y_i) và toạ độ gốc phải trên (z_i, t_i). Toạ độ của các đỉnh là các số nguyên trong phạm vi -10000 đến 10000. Khoảng cách giữa hai hình vuông A và B được định nghĩa là độ dài đoạn thẳng ngắn nhất trong số các đoạn thẳng mà đầu mút thuộc hình vuông A và đầu mút kia thuộc hình vuông B.

- Yêu cầu: Viết chương trình tìm hai hình vuông xa nhau nhất trong số N hình vuông cho trước.
- Dữ liệu vào: Cho từ tệp văn bản HVUONG.INP có dạng:

+ Dòng đầu tiên chứa số N.

+ Dòng thứ i trong N dòng tiếp theo chứa 4 số xi, yi, zi và ti
.
- Kết quả: Ghi ra tệp văn bản HVUONG.OUT là chỉ số của hai hình vuông xa nhau nhất tìm được.