Đề thi chọn học sinh giỏi quốc gia lớp 12 THPT môn Tin năm học 2011 - 2012

Së Gd&§t Qu¶ng b×nh kú thi CHäN ®éi tuyÓn chÝnh thøc dù thi chän hsg quèc gia líp 12 thpt §Ò thi chÝnh thøc n¨m häc 2011 - 2012 M«n thi: tin häc - Vßng 1 Sè B¸o Danh: ................ (Khãa thi ngµy 24 th¸ng 11 n¨m 2011) Thêi gian lµm bµi: 180 phót (kh«ng kÓ thêi gian giao ®Ò) ĐỀ RA 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: (6,0 điểm) Tổng lớn nhất. SUM.PAS Cho một bảng A kích thước NxN chứa các số nguyên. Các dòng được đánh số từ trên xuống dưới, bắt đầu từ 1 đến N. Các cột được đánh số từ trái qua phải, bắt đầu từ 1 đến N. Đường chéo chính của bảng là đường thẳng nối hai ô (1,1) và (N,N). Như vậy trên bảng có 2N-1 đường chéo song song với đường chéo chính. Yêu cầu: Hãy tìm đường chéo song song với đường chéo chính có tổng giá trị các phần tử nằm trên đường chéo đó là lớn nhất. Dữ liệu vào: Cho trong file văn bản SUM.INP có cấu trúc như sau: - Dòng 1: Ghi số nguyên dương N, (1 ≤ N ≤ 100). - Dòng thứ i trong N dòng tiếp theo: Mỗi dòng ghi N số nguyên lần lượt ứng với các phần tử nằm trên dòng thứ i (1 ≤ i ≤ N) của bảng A, mỗi số nguyên trong bảng A có giá trị tuyệt đối không vượt quá 10000, 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 SUM.OUT theo cấu trúc: - Dòng 1: Ghi số nguyên dương T là tổng giá trị các phần tử nằm trên đường chéo tìm được. Ví dụ: SUM.INP SUM.OUT 4 1 2 4 3 3 4 2 5 2 5 4 3 4 3 2 5 14 Câu 2: (7,0 điểm) Chia đất. DIVIDE.PAS Một người cha viết di chúc để lại một mảnh đất có hình dạng là một đa giác lồi làm của thừa kế cho hai người con của mình. Trong di chúc, ông yêu cầu hai người con phải chia mảnh đất này thành hai phần theo đường ranh giới là một đường thẳng cắt hai đỉnh bất kỳ của đa giác lồi sao cho diện tích chênh lệch nhau giữa hai phần là bé nhất. Giả sử mảnh đất là đa giác lồi với các đỉnh là A1, A2, ..., AN nằm trên mặt phẳng toạ độ Oxy, các đỉnh của đa giác được liệt kê theo chiều xuôi hoặc ngược chiều kim đồng hồ, tọa độ các đỉnh của đa giác là các số nguyên. Yêu cầu: Hãy tìm cách chia để giúp hai người con thực hiện bản di chúc này. Dữ liệu vào: Cho trong file văn bản DIVIDE.INP, có cấu trúc như sau: - Dòng 1: Ghi số nguyên dương N là số đỉnh của đa giác (4 ≤ N ≤ 100). - Dòng thứ i trong N dòng tiếp theo: Mỗi dòng ghi hai số nguyên xi yi là tọa độ tương ứng của đỉnh thứ i trong đa giác. Hai số được ghi cách nhau ít nhất một dấu cách (-10000 ≤ xi, yi ≤ 10000). Dữ liệu ra: Ghi ra file văn bản DIVIDE.OUT, theo cấu trúc như sau: - Dòng 1: Ghi 2 số thực S1 S2 là diện tích phần đất mà mỗi người con nhận được. S1, S2 được ghi chính xác đến 4 chữ số thập phân và cách nhau một dấu cách. Ví dụ: DIVIDE.INP DIVIDE.OUT 4 0 0 2 0 2 2 0 2 2.0000 2.0000 Câu 3: (7,0 điểm) Dự án. PROJECT.PAS Một dự án xây dựng công trình trọng điểm quốc gia có N gói thầu, các gói thầu được đánh số từ 1 đến N. Do yêu cầu nghiêm ngặt về thiết kế cho nên mỗi giai đoạn chỉ được thi công và hoàn thành một gói thầu. Có một số gói thầu mà việc thi công nó chỉ được tiến hành sau khi hoàn thành một số gói thầu nào đó. Ví dụ: muốn thi công gói thầu i thì trước đó phải hoàn thành các gói thầu j, k, m … (1 ≤ i, j, k, m, … ≤ N). Yêu cầu: Hãy lập một kế hoạch thi công các gói thầu của dự án. Giả sử rằng luôn lập được một kế hoạch thi công để hoàn thành được các gói thầu của dự án. Dữ liệu vào: Cho trong file văn bản PROJECT.INP, có cấu trúc như sau: - Dòng 1: Ghi số nguyên dương N là số lượng gói thầu (1 ≤ N ≤ 100). - Dòng thứ i trong N dòng tiếp theo: Gồm nhiều số, số đầu tiên di là số lượng các gói thầu cần phải hoàn thành trước gói thầu thứ i; di số tiếp theo là chỉ số các gói thầu phải hoàn thành trước gói thầu thứ i. 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 PROJECT.OUT, theo cấu trúc như sau: - Dòng 1: Ghi N số nguyên dương theo thứ tự cần thi công các gói thầu trong kế hoạch thi công tìm được. Các số được ghi cách nhau một dấu cách. Nếu có nhiều kế hoạch thi công thì chỉ cần đưa ra một kế hoạch. Ví dụ: PROJECT.INP PROJECT.OUT Giải thích: 6 3 5 3 2 0 1 4 1 6 0 1 2 2 5 6 4 3 1 - Muốn thi công gói thầu 1 phải hoàn thành 3 gói thầu 5, 3, 2. Gói thầu 2 thi công thời điểm nào cũng được. Muốn thi công gói thầu 3 phải hoàn thành gói thầu 4. Muốn thi công gói thầu 4 phải hoàn thành gói thầu 6. Gói thầu 5 thi công thời điểm nào cũng được. Muốn thi công gói thầu 6 phải hoàn thành gói thầu 2. ==HẾT==