De hsg 11 tinh Ha Tinh

SỞ GIÁO DỤC VÀ ĐÀO TẠO HÀ TĨNH
KỲ THI CHỌN HỌC SINH GIỎI TỈNH
LỚP 12 THPT NĂM HỌC 2011-2012
Môn: Tin học
Thời gian làm bài: 180 phút


Bài 1: Xâu kí tự:
Có không quá 1000 chiến sỹ công an tham gia chiến dịch truy quét tội phạmở tỉnh X. Các chiến sỹ công an được chia thành không quá 26 đội. Để dễ điều hành, bộ chỉ huy chiến dịch kí hiệu cho mỗi đội là một chữ cái in thường nằm trong khoảng từ ‘a’ đến’z’. Hai đội khác nhau thì có kí hiệu khác nhau. Các chiến sỹ công an thuộc đội nào thì được gắn một kí hiệu là kí hiệu của đội đó. Nếu lấy kí hiệu đã gắn cho tất cả các chiến sĩ công an tham gia chiến dịch ghép lại với nhau thì được một xâu kí tự.
Hãy xác định số lượng các chiến sỹ công an trong mỗi đội.
Ví dụ:
Tệp XAU.INP
Tệp XAU.OUT

abcad
a2
b1
c1
d1


Bài 2: Chuyển động của Robot
Robot được cài đặt để có thể di chuyển trong lưới ô vuông theo một chương trình điều khiển. Từ một ô vuông nào đó, robot có thể di chuyển đến một ô vuông kề cạnh với nó. Chương trình điều khiển gồm các lệnh chỉ rõ hướng mà robot cần di chuyển như sau:
L (lên ô phía trên), X, T, P. Ban đầu robot được đặt vào một ô vuông nào đó ở dòng thứ nhất của lưới ô vuông. Mỗi bước di chuyển của robot là việc thực hiện một lênh để di chuyển đến ô vuông kề cạnh. Hãy xác định xem robot thực hiện bao nhiêu bước di chuyển trước khi dời khỏi lưới ô vuông hoặc bao nhiêu bước di chuyển trước khi rơi vào chu trình và bao nhiêu bước trong một chu trình (chu trình là từ một ô vuông nào đó, sau một số bước di chuyển robot lại trở về ô vuông đó).
Dữ liệu vào là tệp văn bản ROBOT.INP có cấu trúc:
Dòng đầu tiên ghi 3 số nguyên dương M, N, P (1<=M,N,p<=100) theo thứ tự là số dòng, số cột của lưới ô vuông và chỉ số cột của ô xuất phát. Các số ghi cách nhau 1 kí tự trống.
M dòng tiếp theo, mỗi dòng ghi N kí tự thuộc tập hợp {L,X,P,T} là các lệnh điều khiển robot. Các kí tự ghi liên tiếp nhau.
Dữ liệu ra là tệp văn bản ROBOT.OUT:
Ghi một số là số bước di chuyển của robot trước khi rời khỏi lưới ô vuông hoặc ghi hai số cách nhau một kí tự trống là số bước trước khi vào chu trình và số bước trong chu trình.
Ví dụ:
ROBOT.INP
ROBOT.OUT

3 6 5
LPPXTP
TTTPXX
XLTTTT
10

4 5 1
XPXTP
PPXLT
LTPPL
PTXPL
3 8

Bài 3: Đường đi
Sơ đồ đường đi giữa N địa điểm (có số hiệu là 1,2,…,N) trong thành phố X được cho bởi bảng vuông A kích thước NxN. Mỗi phần tử của bảng A chỉ có thể là 0 hoặc 1. Nếu phần tử bảng hàng i, cột j mà bằng 1 thì có đường đi từ địa điểm i đến địa điểm j (1<=i,j<=N). Ngược lại không có đường đi.
Hãy liệt kê tất cả các đường đi từ địa điểm P đến địa điểm Q trong thành phố X, mỗi địa điểm xuất hiện trên mỗi đường đi không quá 1 lần.
Ví dụ:
DUONG.INP
DUONG.OUT

3
0 1 1
1 0 1
1 1 0
1 3
1->2->3
1->3