De thi hsg

SỞ GIÁO DỤC VÀ ĐÀO TẠO KỲ THI CHỌN HỌC SINH GIỎI CẤP TỈNH
PHÚ YÊN LỚP 12 THPT NĂM HỌC 2009-2010
Môn thi: TIN HỌC
Thời gian: 180 phút
(không kể thời gian phát đề)
---------------------------------------------------

TỔNG QUAN BÀI THI

Tên bài
File chương trình
File dữ liệu
File kết quả

Bài 1
CNDK.PAS
CNDK.INP
CNDK.OUT

Bài 2
KHAN.PAS
KHAN.INP
KHAN.OUT


Hãy lập trình bằng ngôn ngữ Pascal để giải các bài toán sau:

Bài 1. (10 điểm)
Một lần trong chương trình “Chiếc nón diệu kỳ”, ở phần chơi dành cho khán giả, thay vì đoán chữ như mọi khi, người dẫn chương trình tự mình quay “chiếc nón” và cho hiện lên màn hình trước mặt khán giả trong trường quay các số trong các ô mà kim chỉ thị lần lượt đi qua. “Chiếc nón” quay đúng một số nguyên vòng, nên trong dãy số hiện lên màn hình, số cuối cùng trùng với số đầu tiên. Sau đó, người dẫn chương trình mời một khán giả ở cuối trường quay (chỉ nhìn thấy màn hình mà không nhìn thấy “chiếc nón”) cho biết chiếc nón có tối thiểu bao nhiêu ô?
Yêu cầu: Hãy trả lời câu hỏi của người dẫn chương trình.
Dữ liệu: Vào từ tập tin văn bản CNDK.INP gồm hai dòng:
+ Dòng 1 ghi số N là số lượng số đã hiện lên màn hình, (2 ( N ( 100).
+ Dòng 2 ghi lần lượt N số, mỗi số có giá trị không quá 32000.
Kết quả: Ghi ra tập tin văn bản CNDK.OUT số ô tối thiểu của “chiếc nón”.
Lưu ý: Các số trên cùng một dòng cách nhau ít nhất một khoảng trắng.
Ví dụ:
CNDK.INP

CNDK.OUT

13
5 3 1 3 5 2 5 3 1 3 5 2 5

6


Bài 2. (10 điểm)
Quầy ăn của một khách sạn cần sử dụng D1, D2, ..., DN khăn trải bàn cho N ngày liên tiếp đánh số từ 1 đến N. Khách sạn có thể mua khăn trải bàn mới với giá là A đồng một khăn, hoặc thuê hiệu giặt trả nhanh (nhận lại khăn giặt sạch vào ngày hôm sau) với giá B đồng một khăn, hoặc thuê hiệu giặt trả chậm (khăn dùng trong ngày i được gởi giặt và trả lại vào ngày i + 2) với giá C đồng một khăn. Giả sử trong ngày 1 khách sạn chưa có khăn.
Yêu cầu: Hãy lập kế hoạch mua-giặt khăn bảo đảm yêu cầu về khăn cho N ngày với chi phí nhỏ nhất.
Dữ liệu: Vào từ tập tin văn bản KHAN.INP gồm hai dòng:
+ Dòng 1: gồm 4 số nguyên dương N, A, B, C, (N < 100, A > B > C).
+ Dòng 2: gồm N số nguyên dương D1, D2, ..., DN.
Kết quả: Ghi ra tập tin văn bản KHAN.OUT gồm N + 1 dòng:
+ Dòng 1: ghi tổng chi phí nhỏ nhất.
+ Dòng i + 1 (1 ( i ( N): ghi 3 số nguyên không âm Mi, Fi, Si theo thứ tự là số khăn cần mua, giặt trả nhanh, giặt trả chậm trong ngày i.
Lưu ý: Các số trên cùng một dòng cách nhau ít nhất một khoảng trắng.
Ví dụ:
KHAN.INP

KHAN.OUT

8 10 8 5
10 8 9 20 7 1 7 9

496
27 0 10
0 0 8
0 2 7
0 0 17
0 0 0
0 0 0
0 0 0
0 0 0


----------------------- H ế t -----------------------