Sở Gd&Đt kỳ thi CHọN học sinh giỏi cấp tỉnh lớp 12 thpt
Quảng bình năm học 2012 - 2013
Môn thi: tin học - Vòng I
Đề thi chính thức (Khóa thi ngày 11 tháng 10 năm 2012)
Số Báo Danh: ................ Thời gian làm bài: 180 phút (không kể thời gian giao đề)

ĐỀ RA
Sử dụng ngôn ngữ lập trình Turbo Pascal để lập trình giải các bài toán sau:

Câu 1: (3,0 điểm) Sắp xếp xâu. SAPXAU.PAS
Người ta định nghĩa: Từ là một nhóm ký tự đứng liền nhau.
Cho một xâu St gồm các ký tự lấy từ tập ‘a’ .. ‘z’ và dấu cách. Xâu không quá 20 từ, mỗi từ dài không quá 10 ký tự.
Yêu cầu: Sắp xếp các từ của xâu ký tự theo thứ tự không giảm của độ dài các từ trong xâu St.
Dữ liệu vào: Cho trong file văn bản SAPXAU.INP, có cấu trúc:
- Dòng 1: Ghi một xâu ký tự St (có ít nhất 1 từ).
Dữ liệu ra: Ghi ra file văn bản SAPXAU.OUT, theo cấu trúc:
- Dòng 1: Ghi các từ của xâu ký tự sau khi được sắp xếp. Các từ được ghi cách nhau đúng một dấu cách.
Ví dụ:
SAPXAU.INP
SAPXAU.OUT

acb abcde abcd abc
acb abc abcd abcde


Câu 2: (3,5 điểm) Dãy con liên tiếp. DAYCON.PAS
Cho dãy số nguyên dương gồm N phần tử A1, A2,…, An.
Yêu cầu: Hãy liệt kê tất cả các dãy con gồm các phần tử đứng liên tiếp của dãy trên sao cho tổng giá trị các phần tử của dãy con đó bằng M.
Dữ liệu vào: Cho trong file văn bản DAYCON.INP, có cấu trúc như sau:
- Dòng 1: Ghi 2 số nguyên dương N và M. Hai số được ghi cách nhau ít nhất một dấu cách. (1
N
1000; 1
M
32000)
- Dòng 2: Ghi N số nguyên dương Ai. Các số được ghi cách nhau ít nhất một dấu cách. (1
Ai
10000 )
Dữ liệu ra: Ghi ra file văn bản DAYCON.OUT, gồm nhiều dòng. Mỗi dòng ghi một dãy con tìm được. Các dãy con được ghi theo thứ tự xuất hiện của nó trên dãy ban đầu. Các số trên cùng một dòng được ghi cách nhau ít nhất một dấu cách.
Nếu không tìm được dãy con thỏa mãn điều kiện thì ghi ra file một số: 0.
Ví dụ:
DAYCON.INP
DAYCON.OUT

11 6
1 4 3 1 2 1 6 5 1 4 1
3 1 2
6
5 1
1 4 1

5 6
1 2 5 2 1
0

Câu 3: (3,5 điểm) Đếm nhóm bạn trong Hội trại NHOMBAN.PAS
Trong một Hội trại hè do Tỉnh Đoàn tổ chức, có N học sinh tham gia, trong đó, có một số học sinh quen nhau. Một số học sinh được gọi là cùng 1 nhóm bạn, nếu bất kì một học sinh nào thuộc nhóm đều có quen ít nhất 1 học sinh khác trong cùng nhóm đó.
Yêu cầu: Hãy đếm xem có bao nhiêu nhóm bạn trong N học sinh tham gia Hội trại.
Dữ liệu vào: Cho trong file văn bản NHOMBAN.INP, có cấu trúc như sau:
- Dòng 1: Ghi số nguyên dương N, là số lượng học sinh tham gia Hội trại.
(1 ≤ N ≤ 100).
- Trong N dòng tiếp theo: Mỗi dòng ghi N số nguyên dương a[i,j] với ý nghĩa:
a[i,j] = 1 nếu học sinh i quen học sinh j (với i ≠j).
a[i,j] = 0 nếu học sinh i không quen học sinh j (với i ≠j).
a[i,i] = 1 (học sinh i được xem là quen bản thân nó).
Các số trên cùng một dòng được ghi cách nhau ít nhất một dấu cách.
Dữ liệu ra: Ghi ra file văn bản NHOMBAN.OUT, theo cấu trúc như sau:
- Dòng 1: Ghi số nguyên dương K, là số lượng nhóm bạn tìm được trong N học sinh tham gia Hội trại.
Ví dụ:
NHOMBAN.INP
NHOMBAN.OUT

5
1 0 0 1 1
0 1 1 0 0
0 1 1 0 0
1 0 0 1 1
1 0 0 1 1
2


==HẾT==