Đề thi chọn học sinh giỏi quốc gia Lớp 12 THPT năm 2005 môn Tin học(Bảng B - Đề 2)

BỘ GIÁO DỤC VÀ ĐÀO TẠO 	 KÌ THI CHỌN HỌC SINH GIỎI QUỐC GIA
	 LỚP 12 THPT NĂM HỌC 2004-2005
§Ò Thi ChÝnh thøc
Môn: Tin học - Bảng B
Thời gian: 180 phút (Không kể thời gian giao đề)
Ngày thi: 11/03/2005
TỔNG QUAN BÀI THI NGÀY THỨ HAI BẢNG B
Tên bài
Tên chương trình
File dữ liệu vào
File kết quả
BÀI 3
Đổi đất
LAND.PAS
LAND.INP
LAND.OUT
BÀI 4
Bộ sưu tập
COLLECT.PAS
COLLECT.INP
COLLECT.OUT
Hãy lập trình giải các bài toán sau:
Bài 3. Đổi đất	 Tên file chương trình: LAND.PAS
Hai bộ lạc Anpha và Bêta sống rất hoà thuận với nhau. Một phần ranh giới của hai bộ lạc là một đường gấp khúc không tự cắt. Đường gấp khúc nhận được bằng cách lần lượt nối điểm đôi một khác nhau . Điểm được xác định bởi hoành độ và tung độ ( là các số nguyên thoả mãn điều kiện: ). Phần đất của bộ lạc Anpha nằm ở phía trên đường gấp khúc. 
Nhân dịp năm mới, tù trưởng hai bộ lạc quyết định thay đổi đường ranh giới cũ bằng cách xây dựng một đường cao tốc là đường nối thẳng từ tới và lấy đường cao tốc này làm ranh giới mới. Dĩ nhiên, sự thay đổi này sẽ chuyển một số phần đất của bộ lạc Anpha cho bộ lạc Bêta và ngược lại. Hai tù trưởng thoả thuận phần diện tích chênh lệch do việc thay đổi đường ranh giới sẽ được điều chỉnh trong tương lai bằng một cách khác.
Yêu cầu: Hãy tính diện tích phần đất của bộ lạc Anpha trở thành đất của bộ lạc Bêta và diện tích phần đất của bộ lạc Bêta trở thành đất của bộ lạc Anpha sau khi thay đổi đường ranh giới giữa hai bộ lạc.
Dữ liệu: Vào từ file văn bản LAND.INP trong đó :
Dòng đầu chứa số ;
Dòng thứ i trong N dòng tiếp theo chứa hai số nguyên và đặt cách nhau ít nhất 1 dấu cách.
Kết quả: Đưa ra file văn bản LAND.OUT trong đó dòng thứ nhất chứa , dòng thứ hai chứa . Kết quả được lấy chính xác với 4 chữ số sau dấu chấm thập phân.
Ví dụ : 
LAND.INP
LAND.OUT
6
0 0
2 4
5 1
7 11
10 8
11 11
8.0000
9.0000
Bài 4. Bộ sưu tập Tên chương trình: COLLECT.PAS
Một bộ sưu tập tiền xu cổ được coi là có giá trị phải gồm không ít hơn đồng tiền vàng, đồng tiền bạc và đồng tiền đồng. Bộ sưu tập ban đầu của Alibaba có một số lượng nhất định các đồng tiền vàng, bạc và đồng nhưng chưa phải là một bộ sưu tập có giá trị. Tại Trụ sở của Hiệp hội những người sưu tầm tiền cổ có đặt một máy đổi tiền để giúp hội viên đổi được các bộ sưu tập có giá trị. Tuy nhiên, máy đổi chỉ hỗ trợ việc đổi tiền trọn gói theo quy tắc đổi gói () lấy gói () đồng tiền. Các quy tắc đổi tiền khác nhau từng đôi một, được gán số hiệu tuần tự 1,2,3, . . . và được công bố trước. Hội viên có thể tạo gói tiền thích hợp từ bộ sưu tập của mình để thực hiện việc đổi tiền. Số lần đổi tiền là không hạn chế, tuy nhiên, để ngăn chặn việc đầu cơ, Hiệp hội quy định mỗi hội viên không được giữ quá 4 đồng tiền mỗi loại. Các đồng tiền nhận được sau mỗi lần đổi được gộp lại với các đồng tiền mà hội viên đang có để thành một bộ sưu tập mới và có thể được sử dụng để đổi trong những lần sau nếu cần. 
Yêu cầu: Cho biết số lượng các đồng tiền vàng, bạc, đồng mà Alibaba có ban đầu và các quy tắc đổi tiền. Hãy chỉ ra một phương án đổi tiền nào đó để Alibaba có được bộ sưu tập có giá trị. Dữ liệu vào đảm bảo luôn có phương án.
Dữ liệu: Vào từ file văn bản COLLECT.INP:
Dòng đầu ghi 6 số nguyên không âm ; 
Các dòng tiếp theo mỗi dòng ghi 6 số nguyên không âm xác định một quy tắc đổi tiền. 
Kết quả: Đưa ra file văn bản COLLECT.OUT một dòng ghi dãy số hiệu các quy tắc theo thứ tự đã sử dụng trong phương án đổi tiền. 
Các số trên một dòng của file dữ liệu và file kết quả đặt cách nhau ít nhất một dấu cách. 
Ví dụ:
COLLECT.INP
COLLECT.OUT
4 0 1 3 3 3
1 0 1 0 2 2
0 1 1 0 0 3
2 0 1 1 2 3
1 0 0 1 1 0
3 4
_________________________________________
Ghi chú: 
Thí sinh không được sử dụng tài liệu
Giám thị không giải thích gì thêm.