Đề 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 A - Đề 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 A
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 A
Tờn bài
Tờn chương trỡnh
File dữ liệu vào
File kết quả
BÀI 3
Bộ sưu tập
COLLECT.PAS
COLLECT.INP
COLLECT.OUT
BÀI 4
Khuụn thộp
STEEL.PAS
STEEL.INP
STEEL.OUT
Hóy lập trỡnh giải cỏc bài toỏn sau:
Bài 3. 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. 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. Số lần đổi khụng hạn chế, tuy nhiờn, là người thực dụng, Alibaba luụn cố gắng giảm tới mức tối đa số lần đổi tiền. Mặt khỏc, để ngăn chặn việc đầu cơ, Hiệp hội quy định, trong mọi thời điểm, mỗi hội viờn khụng được giữ quỏ 4 đồng tiền mỗi loại và khụng được phộp đổi tiếp khi đó đổi được một bộ sưu tập cú giỏ trị. 
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 tất cả cỏc bộ sưu tập tiền cổ cú giỏ trị mà Alibaba cú thể cú được sau một số lần đổi khụng vượt quỏ k cho trước. 
Dữ liệu: Vào từ file văn bản COLLECT.INP. 
Dũng đầu ghi số nguyờn dương ; dũng thứ 2 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. Nếu khụng tồn tại cỏch đổi để cú được bộ sưu tập cú giỏ trị, file kết quả chỉ gồm một số -1. Trong trường hợp ngược lại, dũng đầu ghi số v là số cỏc bộ tiền cổ cú giỏ trị mà Alibaba cú thể đổi được. Dũng thứ i trong v dũng tiếp theo ghi 4 số nguyờn mụ tả bộ sưu tập cú giỏ trị thứ i và số lần đổi ớt nhất khụng vượt quỏ k cần thực hiện để cú được bộ sưu tập ấy. 
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
2
4 0 1 3 3 3
1 0 1 1 1 1
2 0 1 1 3 3
1
3 3 3 1
Bài 4. Khuụn thộp Tờn chương trỡnh: STEEL.PAS	
Để chuẩn bị cho Lễ hội kỷ niệm 30 năm ngày Chiến dịch Hồ Chớ Minh toàn thắng, giải phúng miền Nam, thống nhất đất nước, người ta cần gia cụng cỏc loại khuụn thộp cú hỡnh dạng là cỏc hỡnh đa giỏc lồi đỉnh. Mỗi khuụn thộp được thiết kế trờn một tấm thộp cũng cú hỡnh dạng là một hỡnh đa giỏc lồi đỉnh, khụng cú cạnh nào của khuụn thộp nằm gọn trờn một cạnh của tấm thộp. Để tiện cho việc gia cụng, khuụn thộp được vẽ sao cho hai đường thẳng chứa hai cạnh khụng kề nhau của nú khụng cắt nhau ở bờn trong tấm thộp.
Cụng việc chớnh cần làm trong quỏ trỡnh gia cụng là sử dụng mỏy cắt để cắt được khuụn thộp từ tấm thộp ra. Rừ ràng là cần phải thực hiện nhỏt cắt. Mỗi nhỏt cắt được thực hiện bằng cỏch chọn một cạnh nào đú của khuụn thộp và cắt theo đường thẳng chứa cạnh ấy chia tấm thộp thành hai phần, một phần chứa khuụn thộp cần gia cụng. Chi phớ cắt khuụn thộp là tổng chiều dài của cỏc đường cắt. 
Trờn hỡnh 1 và 2, tấm thộp là tứ giỏc được tụ nhạt, khuụn thộp là hỡnh vuụng được tụ bằng cỏc gạch đậm. Cỏc nột gạch đứt là cỏc đường cắt với tổng chi phớ bằng 6.5 đơn vị.
Yờu cầu: Cho biết hỡnh dạng tấm thộp và khuụn thộp cần gia cụng. Hóy tỡm phương ỏn cắt khuụn thộp cú chi phớ nhỏ nhất.
Dữ liệu: Vào từ file văn bản STEEL.INP: Dũng đầu ghi số là số đỉnh của tấm thộp;dũng tiếp theo, mỗi dũng ghi 2 số thực và , là toạ độ đỉnh của tấm thộp được liệt kờ theo chiều kim đồng hồ bắt đầu từ một đỉnh nào đú; dũng tiếp theo ghi số là số đỉnh của khuụn thộp; cuối cựng là dũng, mỗi dũng ghi 2 số thực và là toạ độ đỉnh của khuụn thộp được liệt kờ theo chiều kim đồng hồ bắt đầu từ một đỉnh nào đú. Cỏc số trờn một dũng cỏch nhau ớt nhất một dấu cỏch.
Kết quả: Đưa ra file văn bản STEEL.OUT chi phớ nhỏ nhất tỡm được với độ chớnh xỏc tới 4 chữ số sau dấu chấm thập phõn. 
Vớ dụ: 
STEEL.INP
STEEL.OUT
4
6.5000
2 1 
2 5 
5 3.5 
5 2
4
3 3 
3 4 
4 4 
4 3 
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.