Đề thi chọn học sinh giỏi cấp Thành phố môn Tin học Lớp 11 - Sở GD&ĐT Thành phố Đà Nẵng

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 2006-2007
M«n thi : tin häc - líp 11 THPT
 Thêi gian : 150 phót (Kh«ng tÝnh thêi gian giao ®Ò)
§Ò CHÝNH THøC: Chú ý: Bài thi gồm có 2 bài trong 2 trang
Tổng quan đề thi
Ngôn ngữ của bộ lạc
Olimpic
Tên bài làm
BL1.PAS
BL2.PAS
Dữ liệu vào
Syntax.inp
Olimpic.inp
Dữ liệu ra
Syntax.out
Olimpic.out
Giới hạn
2 giây
2 giây
Bài 1: Ngôn ngữ của bộ lạc 
	Một bộ lạc có ngôn ngữ chỉ gồm các chữ cái p, q, N, C, văn phạm của ngôn ngữ này cũng rất đơn giản. Một câu đúng theo ngôn ngữ này được định nghĩa như sau:
Mỗi chữ cái p, q là câu đúng.
Nếu A là một câu đúng thì NA là câu đúng.
Nếu A và B là 2 câu đúng thì CAB là câu đúng.
Chỉ các câu nhận được từ các quy tắc 1, 2, 3 là các câu đúng.
Như vậy, câu đúng là một xâu không rỗng và chỉ gồm các ký tự trong số các chữ cái p, q, N, C.Ngược lại nói chung không đúng.
Yêu cầu: Bài toán đặt ra là: một xâu ký tự S không rỗng và chỉ gồm các ký tự trong số các chữ cái p, q, N, C. Hãy tìm một câu đúng S1 thỏa mãn hai điều kiện:
Gồm các ký tự liên tiếp của S.
Có độ dài lớn nhất trong các xâu thỏa mãn điều kiện 1.
Nếu có nhiều xâu S1 cùng thỏa mãn điều kiện 1 và 2, chọn S1 có vị trí đầu tiên trong S.
	 Dữ liệu vào:	Đọc từ file văn bản Syntax.inp gồm một số dòng, mỗi dòng là một xâu ký tự S không rỗng có độ dài không quá 100, chỉ gồm các ký tự trong số các chữ cái p, q, N, C.
	 Dữ liệu ra: Ghi ra file văn bản Syntax.out theo cấu trúc như sau:
	Với mỗi dòng của file Syntax.inp, ghi ra file Syntax.out một dòng tương ứng gồm hai số L, K (L là độ dài xâu S1, K là vị trí ký tự đầu tiên của S1 trong S). Nếu không có xâu S1 ghi L=0, K=0.
	Ví dụ: 
Syntax.inp
Syntax.out
N
CCpqCNp
CNCCpqCqp
0
2
8 2
Bài 2:(5 điểm) Olimpic
	Olimpic Bắc Kinh 2008 được tổ chức tại thủ đô Bắc Kinh của Trung Quốc, có n địa điểm thi đấu được đánh số từ 1 đến n. Đường đi nối từ địa điểm i đến địa điểm j là đường một chiều. Nếu đi ngược lại phải đi con đường khác. Độ dài đường đi từ địa điểm này đến địa điểm kia được cho bởi ma trận D như sau:
	+ D[i, j] là độ dài đường đi từ địa điểm i đến địa điểm j.
	+ D[i, j] = 0 nếu không có đường đi từ địa điểm i đến địa điểm j.
	+ D[i, i] = 0.
	+ D[i, j] nguyên, không âm, D[i, j] ¹ D[j, i].
	Viết chương trình tìm độ dài đường đi ngắn nhất giữa mọi địa điểm thi đấu của thủ đô Bắc Kinh nói trên. 
	Dữ liệu vào:
	Đọc từ file văn bản Olimpic.inp gồm n+1 dòng có cấu trúc:
	- Dòng đầu chứa giá trị n (số lượng địa điểm, n nguyên dương, n £ 50).
	- Dòng i+1 (i = 1..n) chứa n số D[i,1], D[i,2] ,..., D[i,n].
	Các số ghi trên cùng một dòng, cách nhau ít nhất một dấu cách.
	Dữ liệu ra:
	Ghi ra file văn bản Olimpic.out gồm n dòng có cấu trúc:
	 Dòng thứ i (i = 1..n) ghi n số D[i,1], D[i,2] ,..., D[i,n]. 
	Các số ghi trên cùng một dòng, cách nhau ít nhất một dấu cách.
	Ví dụ
Olimpic.inp
Olimpic.out
6
0 7 0 2 0 0
0 0 4 0 1 0
0 0 0 0 0 3
0 4 0 0 0 0
2 0 2 0 0 0
0 1 0 0 0 0
9 6 9 2 7 12 
3 7 3 5 1 6 
7 4 7 9 5 3 
7 4 7 9 5 10 
2 6 2 4 7 5 
4 1 4 6 2 7 
-------------------------------------------------HẾT-------------------------------------------------
Chú ý: Cán bộ coi thi không giải thích gì thêm