De thi hsg

đề thi tin học trẻ tỉnh hà tĩnh năm 2011
Bằng b - Khối thcs
(Thời gian 120 phút)

Bài 1: Xâu đối xứng
Xâu đối xứng là xâu có các ký tự giống nhau và đối xứng với nhau qua điểm giữa xâu. Cho trước N xâu số hiệu 1,2,…,N (1<=N<=20000). Hãy tìm các xâu đối xứng.
Dữ liệu vào: tệp văn bản XAU.INP có cấu trúc
Dòng đầu tiên chứa số N
N dòng tiếp theo chứa các xâu ký tự, mỗi xâu nằm trên một dòng và có độ dài không qua 255 ký tự
Dữ liệu ra: tệp văn bản XAU.OUT có cấu trúc:
Dòng đầu tiên ghi số L là số lượng các xâu đối xứng
Các dòng tiếp theo ghi số hiệu của các xâu đối xứng, tuần tự theo thứ tự tìm được cho đến hết L số. Mỗi dòng ghi không quá 20 số, các số trên mỗi dòng cách nhau ít nhất một ký tự trống.
Ví dụ:

Tệp xâu XAU.INP
Tệp xâu XAU.OUT

4
aba
AcCA
uVkKKkVu
deged
3
1 3 4


Bài 2: Xây dựng dãy số
Cho trước một dãy số A gồm N số tự nhiên a1,a2, …., an (1<=N<=64). Hãy xây dựng dãy số B gồm N số b1,b2, …., bn trong đó b là số đứng trước ar mà lớn hơn ar (1<=r<=N)
Dữ liệu vào: Tệp văn bản DAYSO.INP có cấu trúc
Dòng đầu ghi số N
Dòng tiếp theo ghi dãy số A, các số cách nhau ít nhất một ký tự trống
Dữ liệu ra: Tệp văn bản DAYSO.OUT ghi dãy số B, mỗi số cách nhau một ký tự trống.
Ví dụ:

Tệp DAYSO.INP
Tệp DAYSO.OUT

7
6 1 3 5 7 4 2
0 1 1 1 0 3 5


Bài 3: Hình chữ nhật trong lưới ô vuông
Trong lưới ô vuông có kích thước NxN (N<=100) người ta tạo một số hình chữ nhật bằng cách định vị một số ô liên tiếp kề nhau, các hình chữ nhật này từng đôi một không giao nhau (việc giao nhau xét tới đơn vị điểm của các đường biên trên các cạnh). Người ta dùng một bảng vuông A có kích thước NxN để mô tả thông tin về các hình chữ nhật trong lưới ô vuông, giá trị của các phần tử trong bảng này được xác định như sau:
Giá trị của các phần tử thuộc hàng i, cột j của bảng A bằng 1 nếu ô vuông ở hàng i, cột j của lưới ô vuông đã cho thuộc một hình chữ nhật nào đó, bằng 0 nếu ngược lại
Dữ liệu vào: tệp văn bản HCN.INP có cấu trúc
Dòng thứ nhất ghi số nguyên dương N
N dòng tiếp theo, mỗi dòng ghi N số 0 hoặc số 1 liên tiếp nhau là giá trị của các phần tử của bảng A
Dữ liệu ra: tệp văn bản HCN.OUT có cấu trúc
Dòng thứ nhất ghi số M là số hình chữ nhật có trong lưới ô vuông
M dòng tiếp theo, mối dòng ghi 4 số p, q, r, s cách nhau ít nhất là một ký tự trống với ý nghĩa. Cặp số p, q là tọa độ đỉnh trái trên và r, s là tọa độ đỉnh phải dưới của một hình chữ nhật nào đó trong M hình chữ nhật trong lưới ô vuông
Ví dụ:

Tệp HCN.INP
Tệp HCN