Kỳ thi chọn học sinh giỏi lớp 10 THPT năm học 2012 - 2013 đề thi môn: Tin Học

SỞ GD&ĐT VĨNH PHÚC 
ĐỀ CHÍNH THỨC 
(Đề thi gồm 02 trang) 
KỲ THI CHỌN HSG LỚP 10 THPT NĂM HỌC 2012-2013 
ĐỀ THI MÔN: TIN HỌC 
(Dành cho học sinh THPT không chuyên) 
Thời gian làm bài: 180 phút, không kể thời gian phát đề 
Tổng quan về đề thi 
Tên bài Dữ liệu Kết quả Giới hạn Điểm 
Xếp kiện hàng arrange.inp arrange.out 1s/test 4 
Xâu MOO moo.inp moo.out 1s/test 4 
Nhân 17 xcoding.inp xcoding.out 1s/test 2 
Bài 1. Xếp kiện hàng 
Kho hàng của một công ty nọ có các kiện hàng kích thước giống nhau được xếp thành 
𝑁 (1 ≤ 𝑁 ≤ 10000) cột sắp thành một dãy đánh số thứ tự 1,2,  , 𝑁. Ban đầu, các cột đều có 
số kiện hàng bằng nhau nên có chiều cao bằng nhau, tuy nhiên, một anh công nhân mới vào làm 
đã di chuyển một số kiện hàng giữa các cột, làm cho chiều cao của các cột không bằng nhau 
nữa. 
Yêu cầu 
Cho số lượng kiện hàng của các cột, hãy giúp công ty tính số lượng kiện hàng ít nhất phải 
di chuyển để khôi phục lại trạng thái các cột như ban đầu, nghĩa là có chiều cao bằng nhau. 
Dữ liệu (arrange.inp) 
 Dòng 1: số nguyên 𝑁 (1 ≤ 𝑁 ≤ 10000) là số lượng cột kiện hàng, 
 Dòng 2  1 + 𝑁: dòng thứ 𝑖 + 1 chứa số nguyên 𝑎𝑖 (1 ≤ 𝑎𝑖 ≤ 10000) là số kiện hàng 
trong cột thứ 𝑖. 
Kết quả (arrange.out) 
 Một dòng duy nhất ghi một số nguyên là số kiện hàng cần phải di chuyển để khôi phục 
lại trạng thái các cột có chiều cao bằng nhau. 
Ví dụ 
arrange.inp arrange.out Giải thích 
4 
2 
10 
7 
1 
7 
Bài 2. Xâu MOO 
Dãy xâu MOO là dãy vô hạn xâu được định nghĩa như sau: 
o 𝑆0 = ′𝑚𝑜𝑜′ 
o ∀𝑘 ≥ 0: 𝑆𝑘+1 = 𝑆𝑘 ⨁ ′𝑚𝑜  𝑜′ ⨁ 𝑆𝑘, trong đó xâu ′𝑚𝑜  𝑜′ có 𝑘 + 3 kí tự ′𝑜′; 
phép toán ⨁ là phép nối xâu. 
Chẳng hạn, dưới đây là một số phần tử trong dãy: 
o 𝑆0 = ′𝑚𝑜𝑜
′, 
o 𝑆1 = ′𝑚𝑜𝑜𝑚𝑜𝑜𝑜𝑚𝑜𝑜
′, 
o 𝑆2 = ′𝑚𝑜𝑜𝑚𝑜𝑜𝑜𝑚𝑜𝑜𝑚𝑜𝑜𝑜𝑜𝑚𝑜𝑜𝑚𝑜𝑜𝑜𝑚𝑜𝑜′, 
Yêu cầu 
Với mỗi số nguyên dương 𝑁 (1 ≤ 𝑁 ≤ 109), tất cả các xâu trong dãy có độ dài không nhỏ 
hơn 𝑁 đều có kí tự thứ 𝑁 giống nhau, hãy xác định kí tự đó. 
Dữ liệu (moo.inp) 
 Một dòng duy nhất ghi số nguyên 𝑁 (1 ≤ 𝑁 ≤ 109). 
Kết quả (moo.out) 
 Một dòng duy nhất ghi ký tự ′𝑚′ hoặc ′𝑜′. 
Ví dụ 
moo.inp moo.out 
11 m 
Bài 3. Nhân 17 
Sau khi nhận ra công việc viết phần mềm có nhiều tiềm năng, Bờm đã mở một cửa hàng 
nhỏ chuyên viết phần mềm cho khách hàng ở địa phương. 
Đơn hàng đầu tiên của Bờm là viết một chương trình đọc số nguyên dương 𝑁 ở file dữ 
liệu, và in ra số nguyên 17 × 𝑁 ra file kết quả. Bờm đã nhanh chóng lập trình xong chương trình 
quá đơn giản này nhưng khách hàng của Bờm lại gọi tới và yêu cầu sửa lại đơn hàng rằng các 
số trong file dữ liệu và file kết quả đều được biểu diễn bằng số nhị phân, số trong file dữ liệu có 
không quá 1000 chữ số. 
Yêu cầu 
Hãy giúp Bờm hoàn thành chương trình với yêu cầu mới. 
Dữ liệu (xcoding.inp) 
 Một dòng duy nhất ghi xâu độ dài không quá 1000 là biểu diễn nhị phân của số 𝑁. 
Kết quả (xcoding.out) 
 Một dòng duy nhất ghi xâu là biểu diễn nhị phân của 17 × 𝑁. 
Ví dụ: 
xcoding.inp xcoding.out 
10110111 110000100111 
-------------Hết----------- 
 Thí sinh không được sử dụng tài liệu. Cán bộ coi thi không giải thích gì thêm. 
Họ và tên thí sinh:.......; Số báo danh.