Đề Pascal HSG đề xuất 12

Sở GD&ĐT Nghệ an

Đề đề xuất kỳ thi chọn học sinh giỏi tỉnh lớp 12
năm học 2006-2007
Môn: Tin học
Thời gian: 150 phút( không kể thời gian phát đề)
Chú ý: Đề gồm có ba bài, tên chương trình của các bài: bài1, bài2, bài3 phải ghi vào đĩa với các tên tương ứng là bai1.pas, bai2.pas, bai3.pas.

Bài 1: Thành luỹ Thời xa xưa, để đề phòng và chống lại sự tấn công của các bộ tộc khác, tù trưởng bộ tộc vùng Fladland đã quyết định cho xây dựng các thành luỹ quanh các điểm dân cư đông đúc của mình. Theo lời khuyên của thầy phù thuỷ, tên của các thành luỹ phải được chọn là một xâu con các ký tự liên tiếp nhau của một tên thiêng W nào đó. Ví dụ, nếu W là ’baobaab’, thì tên của thành luỹ có thể là ’ba’, ’oba’, ’baab’…, còn ’bab’ hoặc ’bob’ không thể được dùng để đặt tên. Dĩ nhiên, các thành luỹ khác nhau không được đặt tên trùng nhau. Tù trưởng muốn biết là có thể xây dựng được tối đa bao nhiêu thành luỹ dựa vào số tên có thể đặt. Dữ liệu: Vào từ file văn bản BASTION.INP gồm một dòng chứa tên thiêng W, trong đó chỉ có các chữ cái la tinh thường và có độ dài không quá 255. Kết quả: Đưa ra file văn bản BASTION.OUT một số nguyên là số lượng các tên thành luỹ có thể đặt khác nhau. Ví dụ:
bastion.inp
bastion.out

baobaab
23


Bài 2: Permut
Cho một mảng A gồm N số là một hoán vị từ 1 đến N. Một dẫy con của dãy trên là một đoạn liên tục từ u đến v (u<=v). Cần tìm tất cả các dãy con sao cho dãy con đó cũng là một hoán vị của các số liên tiếp bắt đầu từ 1.
Dữ liệu vào từ File PERMUT.INP:
Dòng thứ nhất ghi số N (N<=30000).
Dòng thứ hai ghi N số A[1] đến A[N]
Dữ liệu ra ghi vào File PERMUT.OUT:
Dòng thứ nhất ghi K là số dãy con của dãy A là hoán vị,
Tiếp theo là K dòng, mỗi dòng ghi 3 số u v w với ý nghĩa đoạn từ u đến v là hoán vị của các số từ 1 đến w.
Ví dụ:
PERMUT.INP
PERMUT.OUT

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


Bài 3: Điệp viên
Một điệp viên trưởng phụ trách một nước nọ trước khi về nước muốn gặp nhân viên của mình để nghe báo cáo. Hai người đang ở hai thành phố khác nhau vì vậy họ phải di chuyển để gặp nhau. Quy tắc di chuyển như sau:
Họ di chuyển vào ban ngày và nghỉ tại một thành phố vào buổi tối.
Trong ngày, họ chỉ có thể di chuyển từ một thành phố tới thành phố bên cạnh (có đường đi trực tiếp và các đường đi này là 1 chiều).
Để bảo đảm an toàn, các điệp viên luôn luôn di chuyển (không dừng tại một thành phố quá một đêm).
Hai người có thể gặp nhau nếu họ ở cùng1 thành phố vào buổi tối.
Lập chương trình kiểm tra xem 2 người có gặp nhau không.
Dữ liệu: agent.inp
Dòng đầu ghi 2 số: n là số thành phố, m là số các đường đi trực tiếp giữa các thành phố (n <=50, m<=100).
Dòng tiếp theo là 2 số p, q là vị trí hiện thời của hai điệp viên.
M dòng tiếp theo mỗi dòng chứa 2 số ai, aj là số hiêu các thành phố và từ ai có đường đi trực tiếp (một chiều) đến aj.
Kết quả: agent.out
Nếu 2 người không gặp nhau in ra -1
Nếu 2 người gặp nhau in ra t là số ngày ngắn nhất mà hai người có thể gặp nhau.
Ví dụ:

Agent.in1
Agent.ou1
Agent.in2
Agent.ou2
Agent.in3
Agent.ou3
Agent.in4
Agent.ou4

6 7
1 5
1 2
4 5
2 3
3 4
4 1
5 4
5 6
3
3 3
1 3
1 2
2 3
3 1
No
8 9