De thi hsg yen bai

SỞ GIÁO DỤC VÀ ĐÀO TẠO KỲ THI CHỌN HỌC SINH GIỎI
TỈNH YÊN BÁI LỚP 12 THPT NĂM HỌC 2010- 2011
Môn thi: Tin học
Thời gian: 180 phút (không kể thời gian giao đề)
Ngày thi: 10-10-2010


Bài 1(6 điểm): Cho một số tự nhiên N (1<=N<=120), người ta phân tích số N thành các số tự nhiên si (1<= si<= N) có tổng bằng N. Ví dụ N=4 ta có 5 cách phân tích:
Cách 1: 4 = 1+1 +1+1
Cách 2: 4 = 2 +1+1
Cách 3: 4= 2+2
Cách 4: 4= 3+1
Cách 5: 4= 4
Yêu cầu: Từ một số N cho trước, tìm số cách để phân tích như trên.
Dữ liệu vào: Từ file PT.INP có chứa giá trị N (1<=N<=120).
Kết quả ra: Ghi ra file PT.OUT chứa tổng số cách phân tích được.
Ví dụ:
PT.INP
PT.OUT

4
5


Bài 2 (7 điểm): Để xây dựng một trường Đại học mới tại tỉnh A, UBND tỉnh đã đưa ra n địa điểm và đánh số từ 1 đến n, sau đó chọn ra 1 địa điểm X để xây dựng trường. Để tạo điều kiện cho sinh viên đến trường, người ta tiến hành làm mới 1 số tuyến đường sao cho đảm bảo các sinh viên đến trường đều đi qua đường mới xây dựng và tổng độ dài các quãng đường phải xây dựng mới là nhỏ nhất.
Yêu cầu: Hãy tính ra m là tổng số độ dài các quãng đường phải xây mới.
Dữ liệu vào: - Từ file XT.INP có dòng đầu là n, X, (0 - Dữ liệu đảm bảo luôn có đường đi từ các điểm khác về điểm X đã chọn.
Kết quả ra: Ghi ra file XT.OUT gồm 1 số m.
Ví dụ:
XT.INP
XT.OUT

4 2
2 1 15
2 3 8
2 4 20
3 4 6
29


Bài 3 (7 điểm): Tại quốc gia T đã có n (n<100) tuyến đường được xây dựng giữa 2 thành phố A và B. Để quy hoạch và xây dựng mới lại các tuyến đường, Chính phủ ra quyết định cần phải phá huỷ các tuyến đường cắt nhau giữa 2 thành phố. Mỗi tuyến đường được hiển thị bởi 2 số ai và bi (1<= ai;bi <=10000, i=1..n);
Trong đó: - ai , bi tương ứng là 2 điểm nằm trên 2 thành phố.
- Hai tuyến đường p và q được gọi là cắt nhau khi apbq hoặc ap>aq, bpYêu cầu: - Không còn 2 tuyến đường nào cắt nhau giữa 2 thành phố.
- Số tuyến đường cần phá bỏ là ít nhất.
Dữ liệu vào: File văn bản tên là PD.INP có cấu trúc như sau:
- Dòng đầu tiên là số nguyên dương n.
- n dòng tiếp theo mỗi dòng chứa 2 số ai ,bi là toạ độ tương ứng của n tuyến đường.
Kết quả ra: Xuất ra file văn bản PD.OUT với 1 số duy nhất là số lượng tuyến đường cần phá.
Ví dụ:
PD.INP
PD.OUT

 4
4 3
6 8
7 8
7 1
2




..................................HẾT...................................














Họ và tên thí sinh:................................................SBD........................................
Chữ ký của giám thị 1:......................... Chữ ký của giám thị 2...........................
(Giám thị không giải thích gì thêm)
ĐÁP ÁN: Đề thi chính thức
Môn: Tin học lớp 12

Bài 1: (6 điểm)
program bt1;
const fi=`d:t1.txt`;
fo=`d:t1.out`;
var a:array[1..120,0..120] of longint;
n:byte;
procedure input;
var f:text;
begin
assign(f,fi);
reset(f);
readln(f,n);
close(f);
end;
procedure pt;
var i,j,