Sở Giáo dục - Đào tạo Kỳ thi chọn học sinh giỏi cấp thành phố
Thành phố Đà Nẵng năm học 2007-2008

Môn thi : Tin học - lớp 10 THPT
Thời gian : 150 phút (Không tính thời gian giao đề)

ĐỀ THI ĐỀ NGHỊ: Chú ý bài thi gồm có 2 bài trong 2 trang

Tổng quan đề thi
Cặp ký tự
Bản đồ

Tên bài làm
Bl1.pas
Bl2.pas

Dữ liệu vào
capkytu.inp
bando.inp

Dữ liệu ra
capkytu.out
bando.out

Giới hạn
2 giây
2 giây

Dấu * trong tên file chương trình sẽ được thay thế bằng PAS hoặc PP tuỳ thuộc môi trường thí sinh chọn tương ứng là Borland Pascal hoặc Free Pascal.
Hãy lập trình giải các bài toán sau đây:
Bài 1: Cặp ký tự
Cho xâu ký tự gồm n cặp ký tự ‘A’ và ‘B’ trong đó các cặp ký tự ‘A’ và ‘B’ hoặc chứa trong nhau hoặc rời nhau và không giao nhau.
Chẳng hạn: AABB hoặc ABAB
└┘ └┘└┘
└ ┘
Thông tin về một xâu ký tự là một dãy số nguyên dương, là số các ký tự nằm giữa các cặp ký tự từ trái sang phải.

Ví dụ: AAABAABABBBB
└┘ └┘└┘
0 0 0
4
8
10
có thông tin là: 10 8 0 4 0 0

Yêu cầu: Cho biết thông tin về xâu ký tự. Hãy phục hồi lại xâu ký tự đó.
Dữ liệu vào: Đọc từ file văn bản CAPKYTU.INP gồm 2 dòng:
- Dòng thứ nhất chứa số n.
- Dòng thứ hai chứa thông tin về n cặp ký tự, mỗi số cách nhau
một dấu cách.
Dữ liệu ra: Ghi ra file văn bản CAPKYTU.OUT gồm một dòng là xâu ký tự
đã được phục hồi.
Ví dụ:

CAPKYTU.INP
CAPKYTU.OUT

6
10 8 0 4 0 0
AAABAABABBBB


Bài 2: Nhóm học tập

Tại một trung tâm tin học có N học viên được sắp ngồi theo một hàng dọc, mỗi học viên được trung tâm cấp một tấm thẻ ghi số giờ đã học tại trung tâm (số giờ học là một số tự nhiên). Ta gọi một nhóm học tập là nhóm các học viên được sắp hàng ngồi cạnh nhau vẫn giữ nguyên thứ tự sắp ban đầu, biết rằng mỗi học viên chỉ được ở một nhóm.
Yêu cầu: Hãy tìm cách chia N học viên này thành nhiều nhóm học tập nhất sao cho tổng số giờ học ghi trên tấm thẻ của mỗi nhóm đều bằng nhau.
Dữ liệu vào: Đọc từ file văn bản NHOMHT.INP gồm:
Dòng đầu tiên là số N (1Các dòng tiếp theo là các số hạng a1,a2,...,aN ghi số giờ học trên tấm thẻ của các học viên theo thứ tự được sắp. Mỗi số cách nhau ít nhất một dấu cách, mỗi dòng 10 số. Riêng dòng cuối cùng có thể ít hơn 10 số.
Dữ liệu ra: Ghi ra file văn bản NHOMHT.OUT gồm 4 dòng:
- Dòng thứ 1 là vị trí cuối của mỗi nhóm, mỗi vị trí cách nhau một dấu cách.
- Dòng thứ 2 là tổng S các giờ học ghi trên tấm thẻ của tất cả các học viên.
Dòng thứ 3 là số k các nhóm học tập.
Dòng thứ 4 là tổng t các giờ học ghi trên tấm thẻ của mỗi nhóm.

Ví dụ:

NHOMHT.INP
NHOMHT.OUT

19
1 0 2 0 0 3 1 1 1 0
2 1 0 0 2 1 2 0 1

3 6 9 12 16 19
18
6
3


---------------------------------HẾT------------------------------------

Thí sinh không được sử dụng tài liệu dưới mọi hình thức.
Giám thị không giải thích gì thêm.