SỞ GD&ĐT VĨNH PHÚC

ĐỀ CHÍNH THỨC
KỲ THI CHỌN HSG LỚP 11 THPT NĂM HỌC 2010-2011
ĐỀ THI MÔN: TIN HỌC
Dành cho học sinh các trường THPT không chuyên
Thời gian làm bài: 180 phút, không kể thời gian giao đề.
(Đề thi có 02 trang, gồm 03 bài)

TỔNG QUAN
TT
Tên bài
File chương trình
File dữ liệu
File kết quả
1
Đi hay ở lại?
GOSTAY.PAS
GOSTAY.INP
GOSTAY.OUT
2
Xếp trâu
XTRAU.PAS
XTRAU.INP
XTRAU.OUT
3
Đoạn con
SUBSEQ.PAS
SUBSEQ.INP
SUBSEQ.OUT
Lập chương trình giải các bài toán sau:


VINHYEN
HANOI
STAY
Bài 2. Xếp trâu
Để đổi lấy gói xôi gấc của Phú ông, Bờm cần sắp xếp các con trâu với số lượng không
hạn chế vào một mảnh đất có dạng lưới ô vuông kích thước   , trong đó      


Vốn thích sự cân bằng, Phú ông yêu cầu Bờm thực hiện lần lượt 3 thao tác sau:
o Bước 1. Tìm ô chính giữa của lưới và đặt một con trâu vào đó, nếu không tìm
được ô chính giữa thì dừng lại.
o Bước 2. Giả sử ô chính giữa là ô  , chia lưới ô vuông thành 4 phần bằng nhau
có được phân cách nhau bởi hàng , cột  và đặt một con trâu vào ô  .
o Bước 3. Thực hiện lại từ bước 1 cho 4 phần đã được chia ở bước 2.
Các thao tác trên cứ lặp đi lặp lại cho đến khi không tìm được ô trung tâm hoặc không thể
chia được nữa. Phú ông yêu cầu Bờm tính số con trâu được xếp chỗ.
Ví dụ: Mảnh đất chưa đặt con trâu có kích thước N = 7 và M = 15 và xếp được 21 con
trâu.

Dữ liệu (xtrau.inp)
 Một dòng duy nhất ghi hai số nguyên   cách nhau bởi một dấu cách.
Kết quả (xtrau.out)
 Một dòng duy nhất ghi số trâu được xếp chỗ.
Ví dụ:
xtrau.inp
xtrau.out
7 15
21
Bài 3. Đoạn con