Đề 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 - Đề 1)

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: 10/03/2005
TỔNG QUAN BÀI THI NGÀY THỨ NHẤT 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 1
Phõn đoạn
SEGPAR.PAS
SEGPAR.INP
SEGPAR.OUT
BÀI 2
Phỏo hoa
FIREWK.PAS
FIREWK.INP
FIREWK.OUT
Hóy lập trỡnh giải cỏc bài toỏn sau:
Bài 1. Phõn đoạn 	Tờn file chương trỡnh: SEGPAR.PAS
Cho dóy số nguyờn a1, a2, , an và số nguyờn dương k. Ta gọi k-phõn đoạn của dóy số đó cho là cỏch chia dóy số đó cho ra thành k đoạn, mỗi đoạn là một dóy con gồm cỏc phần tử liờn tiếp của dóy. Chớnh xỏc hơn, một k-phõn đoạn được xỏc định bởi dóy chỉ số 
.
Đoạn thứ i là dóy con . Ở đõy quy ước 
Yờu cầu: Hóy xỏc định số M nhỏ nhất để tồn tại k-phõn đoạn sao cho tổng cỏc phần tử trong mỗi đoạn đều khụng vượt quỏ M.
Dữ liệu: Vào từ file văn bản SEGPAR.INP.
Dũng đầu tiờn chứa hai số nguyờn n và k (1≤ k ≤ n ≤ 15000);
Dũng thứ i trong số n dũng tiếp theo chứa số nguyờn ai (|ai| ≤ 30000), i =1, 2, , n.
Cỏc số cạnh nhau trờn một dũng trong file dữ liệu cỏch nhau ớt nhất một dấu cỏch.
Kết quả: Ghi ra file SEGPAR.OUT một số nguyờn duy nhất là giỏ trị M tỡm được.
Vớ dụ:
SEGPAR.INP
SEGPAR.OUT
9 4
1
1
1
3
2
2
1
3
1
5
Bài 2: Phỏo hoa	 Tờn chương trỡnh: FIREWK.PAS
Nhằm chào mừng cỏc ngày lễ lớn trong năm 2005 người ta đó chế tạo một loại đạn phỏo hoa mới, khi bắn, đạn nổ thành bụng hoa 2n cỏnh màu ( 1 ≤ n ≤ 30). Nguyờn vật liệu cho phộp tạo được m màu khỏc nhau, đỏnh số từ 1 đến m (2 ≤ m ≤ 32). 
Để đảm bảo tớnh mỹ thuật, việc chuyển tiếp màu giữa 2 cỏnh hoa kề nhau phải tuõn theo quy tắc chuyển màu cầu vồng sau đõy:
Bờn cạnh cỏnh hoa màu i phải là cỏnh hoa màu i-1 hoặc i+1, với 1 < i < m,
Bờn cạnh cỏnh hoa màu 1 chỉ cú thể là cỏnh hoa màu 2,
Bờn cạnh cỏnh hoa màu m chỉ cú thể là cỏnh hoa màu m-1.
Một bụng hoa khụng nhất thiết phải cú đầy đủ m màu. Mỗi bụng hoa tương ứng với một vũng trũn 2n số thể hiện màu của cỏc cỏnh hoa. Vớ dụ, hỡnh 1 là bụng hoa 24 cỏnh (n = 12) và hỡnh 2 là vũng trũn số tương ứng với nú. Mỗi bụng hoa được mụ tả bằng dóy 2n số nguyờn liệt kờ cỏc chỉ số màu của cỏc cỏnh hoa theo chiều kim đồng hồ. Vớ dụ, bụng hoa ở hỡnh 1 cú thể được mụ tả bằng dóy số
3 4 3 2 1 2 3 4 3 2 1 2 3 4 3 2 1 2 3 4 3 4 3 2.
Dóy cú thứ tự từ điển nhỏ nhất trong cỏc dóy cú thể dựng để mụ tả hoa được gọi là mó hoa. Khi đú, mó hoa của bụng hoa ở hỡnh 1 sẽ là 
1 2 3 4 3 2 1 2 3 4 3 2 1 2 3 4 3 4 3 2 3 4 3 2.
Trong cỏc ngày lễ, Ban tổ chức yờu cầu bắn cỏc đạn phỏo hoa 2n cỏnh cú đỳng k cỏnh màu C (0 ≤ k ≤ 2). Cỏc mó hoa thỏa món yờu cầu vừa nờu cũng được sắp xếp theo thứ tự từ điển và đỏnh số bắt đầu từ 1. Hơn nữa, nhằm tạo ra cỏc hoa khụng giống nhau, đội bắn phỏo hoa cần đảm bảo hai viờn đạn phỏo hoa bắn liờn tiếp phải cú mó khỏc nhau. Do vậy, người ta đó thiết kế một Hệ thống chụp ảnh và phõn tớch tự động để bỏo cho đội bắn phỏo hoa biết số thứ tự của viờn đạn phỏo hoa vừa nổ trờn trời. Em được giao viết chương trỡnh giải quyết nhiệm vụ chớnh trong phần mềm phõn tớch tự động này.
Yờu cầu: Cho biết n, m, k và C. Gọi X là tập tất cả cỏc mó hoa 2n cỏnh cú đỳng k cỏnh màu C.
Hóy xỏc định số lượng p cỏc phần tử của X;
Cho một mó hoa nào đú trong tập X. Hóy xỏc định số thứ tự từ điển của nú trong X. 
Dữ liệu: Vào từ file văn bản FIREWK.INP. Dũng đầu tiờn chứa 4 số nguyờn n, m, k, C; dũng tiếp theo chứa 2n số nguyờn mụ tả một mó hoa.
Cỏc số trờn một dũng của file dữ liệu cỏch nhau ớt nhất một dấu cỏch.
Kết quả: Đưa ra file văn bản FIREWK.OUT. Dũng đầu tiờn ghi số nguyờn p; dũng tiếp theo ghi số thứ tự tỡm được của mó hoa.
Vớ dụ:
FIREWK.INP
FIREWK.OUT
3 4 0 1
2 3 4 3 4 3 
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.