Đề thi Olympic XV (2009)

BAN TỔ CHỨC KÌ THI
------------------------(((------------------------



TUYỂN TẬP ĐỀ THI OLYMPIC
30 THÁNG 4 LẦN 15-2009








TIN HỌC




LỚP 10










NHÀ XUẤT BẢN ĐẠI HỌC SƯ PHẠM
TRƯỜNG THPT CHUYÊN LÊ HỒNG PHONG – TP. HỒ CHÍ MINH
Bài 1: Dự tiệc (MS0001)
Ông An đến dự một buổi tiệc. Buổi tiệc đã có N người (0Yêu cầu: Cho trước một danh sách khách dự tiệc cùng với các số trên áo của họ, hãy giúp ban tổ chức tìm ra số hiệu của phòng khách có số lượng khách là số lẻ.
Dự liệu vào: cho một file văn bản DUTIEC.INP gồm:
Dòng đầu tiên ghi một số N cho biết số khách của buổi tiệc khi ông An đến
Trong N dòng tiếp theo, mỗi dòng ghi một số nguyên dương cho biết con số ghi trên áo của người khách thứ i
Dữ liệu ra: Cho file văn bản DUTIEC.OUT gồm 1 số nguyên dương duy nhất đó là số hiệu phòng có số khách là số lẻ
Ví dụ
DUTIEC.INP
DUTIEC.OUP

5
1
2
2
3
1
3

Bài 2: Lưới (MS0002)
Cho một lưới ô vuông gồm M dòng N cột. Trong mỗi ô của lưới chỉ chứa số 0 hoặc 1, mỗi ô vuông ở dòng x cột y kí hiệu là (x,y). Từ một ô vuông có thể di chuyển sang ô vuông chung cạnh. Một vùng là tập hợp các ô vuông kề cạnh với nhau và có giá trị bằng nhau. Các ô kề cạnh với vùng và có giá trị khác nhau với giá trị các ô trong vùng thì không thuộc vùng. Cho trước hia ô vuông (x1,y1) và (x2,y2). Hãy cho biết hai ô vuông đã cho có cùng thuộc 1 vùng hay không, trong trường hợp hai ô vuông này không cùng thuộc một vùng hãy kiểm tra xem di chuyển từ ô (x1,y1) sang ô (x2,y2) có phải đi qua đúng một vùng trung gian hay không (Nếu đi qua đúng một vùng trung gian thì gọi là hai ô cách một vùng)
Ví dụ: Hình bên dưới là ô vuông 4x6, hai ô (3,4) và (1,2) là thuộc một vùng, hai ô (2,3) và (1,6) cách một vùng
1
1
0
0
1
1

0
1
1
0
0
1

0
0
1
1
0
0

1
1
0
0
0
0

Dữ liệu vào: Cho trong file văn bản LUOI.INP
Dòng đầu tiên ghi các số M, N, x1, y1, x2, y2 (1≤ x1, x2 ≤M≤100; 1≤y1, y2,≤N≤100)
Trong M dòng tiếp theo, mỗi dòng ghi N số 0 hoặc 1 tương ứng với giá trị của các ô lưới
Các số cách nhau ít nhất một khoảng trắng
Dữ liệu ra: Ghi ra file văn bản LUOI.OUT gồm 1 số nguyên:
Nếu hai ô (x1,y1) và (x2,y2) cùng thuộc một vùng thì ghi số 1
Nếu hai ô (x1,y1) và (x2,y2) cách một vùng thì ghi số 2
Các trường hợp khác ghi số 3
Ví dụ:
LUOI.INP
LUOI.OUT

4 6 2 3 1 6
1 1 0 0 1 1
0 1 1 0 0 1
0 0 1 1 0 0
1 1 0 0 0 0
2

Bài 3: Lớp học (MS0003)
Trong lớp học khiêu vũ có N học viên gồm các bé trai và các bé gái. Các học viên được xếp thành một hàng. Giáo viên muốn chọn ra một nhóm gồm những học viên đứng liên tiếp nhau và số lượng các bé trai bằng số lượng các bé gái để hướng dẫn kĩ thuật khiêu vũ
Hỏi có bao nhiêu cách chọn thỏa mãn yêu cầu của giáo viên?
Dữ liệu vào: Cho trong file văn bản LOPHOC.INP
Dòng đầu tiên ghi số nguyên N (1≤N≤106)
Dòng thứ hai ghi mô tả các học viên đứng trong