Kỳ thi chọn học sinh giỏi lớp 11 năm học 2011 – 2012 đề thi môn: Tin học dành cho học sinh khối THPT chuyên

SỞ GD&ĐT VĨNH PHÚC 
ĐỀ CHÍNH THỨC 
KỲ THI CHỌN HSG LỚP 11 NĂM HỌC 2011 – 2012 
ĐỀ THI MÔN: TIN HỌC 
Dành cho học sinh khối THPT Chuyên 
Thời gian làm bài: 180 phút, không kể thời gian giao đề 
Lưu ý: đề thi có 02 trang 
Tổng quan 
Tên bài Chương trình Dữ liệu Kết quả Giới hạn Điểm 
Đuôi số bintails.* bintails.inp bintails.out 256MB, 1s/test 40 
Đối xứng enpalin.* enpalin.inp enpalin.out 256MB, 1s/test 40 
Đường gấp khúc brkline.* brkline.inp brkline.out 256MB, 1s/test 20 
Lập chương trình giải các bài toán sau: 
Bài 1. Đuôi số 
Xét số nguyên dương , giả sử biểu diễn nhị phân của là . Gọi là chỉ số nhỏ nhất 
thỏa mãn . Ta định nghĩa đuôi của , kí hiệu ( ), là số nguyên có biểu diễn nhị phân 
 . 
Chẳng hạn, với , biểu diễn nhị phân của là ( ) đuôi của là ( ) ( ) . Tương 
tự, có ( ) ( ) . 
Cho hai số nguyên dương . Hãy tính tổng đuôi của tất cả các số nguyên trong phạm vi . 
Dữ liệu (bintails.inp) 
 Dòng : hai số nguyên ( ). 
Kết quả (bintails.out) 
 Dòng : số nguyên kết quả. 
Ví dụ 
bintails.inp bintails.out giải thích 
2 5 8 f(2)+f(3)+f(4)+f(5) = 
 2 + 1 + 4 + 1 = 8 
Bài 2. Đối xứng 
Xâu kí tự được gọi là đối xứng nếu khi viết lại xâu theo chiều từ phải sang trái, ta vẫn nhận được 
chính xâu đó, chẳng hạn các xâu là xâu đối xứng còn các xâu thì 
không. 
Cho xâu chỉ gồm các chữ số và chữ cái Latin hoa hay thường. Để nhận được xâu đối xứng từ , 
ta có thể thực hiện một số phép biến đổi. Mỗi phép biến đổi là việc chọn ra hai kí tự và thay 
tất cả các kí tự trong bởi kí tự . Chi phí của phép biến đổi là số kí tự bị thay đổi. 
Hãy xác định tổng chi phí nhỏ nhất để biến đổi được thành xâu đối xứng. 
Dữ liệu (enpalin.inp) 
 Dòng : xâu (| | ) 
Kết quả (enpalin.out) 
 Dòng : số nguyên kết quả 
Ví dụ 
enpalin.inp enpalin.out giải thích 
01bacbb50 2 Có thể sử dụng hai phép 
biến đổi 1-->5 và a-->b 
Bài 3. Đường gấp khúc 
Trên một đường tròn cho điểm đánh số theo chiều kim đồng hồ. Có đoạn thẳng nối 
các cặp điểm trong điểm đó, mỗi đoạn thẳng nối hai điểm phân biệt, mỗi cặp điểm được nối bởi 
không quá một đoạn thẳng. 
Hãy xác định một đường gấp khúc không tự cắt qua cả điểm gồm toàn các đoạn thẳng trong 
đoạn kể trên. 
Dữ liệu (brkline.inp) 
 Dòng : hai số nguyên ( ) 
 Dòng : mỗi dòng ghi hai số nguyên thể hiện đoạn thẳng nối hai điểm . 
Kết quả (brkline.out) 
 Dòng : số nguyên là các đỉnh trên đường gấp khúc theo thứ tự, nếu không có đường 
gấp khúc thỏa mãn yêu cầu bài toán thì dòng này chỉ ghi . 
Ví dụ 
brkline.inp brkline.out giải thích 
7 9 
1 4 
5 1 
1 7 
5 6 
2 3 
3 4 
2 6 
4 6 
6 7 
2 3 4 1 7 6 5 
------ HẾT----- 
Thí sinh không được sử dụng tài liệu để làm bài 
Cán bộ coi thi không được giải thích gì thêm 
HỌ VÀ TÊN THÍ SINH: ...................................................................................................................................................... 
SỐ BÁO DANH: .....................................................................................................................................................................