Kì thi chọn học sinh giỏi lớp 9 năm học 2014 - 2015 đề thi môn: Tin Học

Trang 1 / 2 
SỞ GD&ĐT VĨNH PHÚC 
ĐỀ CHÍNH THỨC 
KÌ THI CHỌN HSG LỚP 9 NĂM HỌC 2014-2015 
ĐỀ THI MÔN: TIN HỌC 
Thời gian làm bài: 150 phút không kể thời gian giao đề 
Tổng quan đề thi: 
STT Tên bài File chương trình File dữ liệu File kết quả Thời gian Điểm 
1 BRC brc.* brc.inp brc.out 1 giây 2.0 
2 PNM pnm.* pnm.inp pnm.out 1 giây 4.0 
3 MXM mxm.* mxm.inp mxm.out 1 giây 4.0 
Lưu ý: Thí sinh thay * trong File chương trình là PAS hoặc C hoặc CPP tùy theo ngôn 
ngữ lập trình mà thí sinh sử dụng là Pascal hoặc C/C++ 
Lập chương trình giải các bài toán sau đây: 
Bài 1. BRC 
 Cần chia 𝑛 bánh cho 𝑚 người. Ban đầu mỗi cái bánh là một phần, chỉ dùng một dao 
cắt bánh, mỗi thao tác cắt chỉ được chia một phần bánh thành hai phần với tỷ lệ tùy ý. 
 Yêu cầu: Dùng ít thao tác cắt nhất để chia bánh thành các phần cho 𝑚 người, mỗi 
phần thuộc về đúng một người và lượng bánh mỗi người nhận được là bằng nhau. 
 Dữ liệu: 
 Một dòng duy nhất ghi hai số 𝑛 và 𝑚, cách nhau bởi một dấu cách, 
1 ≤ 𝑛, 𝑚 ≤ 1018 
 Kết quả: 
 Ghi ra số thao tác cắt ít nhất thỏa yêu cầu. 
 Ví dụ: 
input output Giải thích 
3 5 4 
Bài 2. PNM 
 Ngôn ngữ PNM thường được sử dụng để trình diễn phông chữ trong máy tính hoặc 
dùng để in thử nghiệm trong các thiết bị in ấn. Một từ hoặc một câu gọi là PNM nếu các chữ 
cái của bảng chữ cái Latin đều xuất hiện ít nhất một lần trong từ hoặc câu đó. 
 Cho một chuỗi các kí tự (bao gồm cả in thường và in hoa) thuộc bảng chữ cái Latin, 
kiểm tra xem chuỗi này có là PNM hay không? 
 Dữ liệu: 
 Dòng đầu ghi số nguyên dương 𝑁 (1 ≤ 𝑁 ≤ 300) là số kí tự trong chuỗi 
 Dòng tiếp theo ghi 𝑁 kí tự thuộc bảng chữ cái Latin. 
 Kết quả: 
 Ghi YES nếu nó là ngôn ngữ PNM, ghi NO trong trường hợp ngược lại. 
 Ví dụ: 
input output input output 
12 
toosmallword 
NO 35 
TheQuickBrownFoxJumpsOverTheLazyDog 
YES 
 Ràng buộc: Có 60% số test ứng với 60% số điểm có 1 ≤ 𝑁 ≤ 255 
Trang 2 / 2 
Bài 3. MXM 
 Cho số nguyên dương 𝑁. Tìm bội số lớn nhất của số 30 sau khi xáo trộn các chữ số 
của số 𝑁. 
 Dữ liệu: 
 Một dòng duy nhất ghi số 𝑁, 2 ≤ 𝑁 ≤ 1018 
 Kết quả: 
 Ghi kết quả tìm được trên một dòng, nếu không tìm được ghi -1 
 Ví dụ: 
input output input output input output 
30 30 102 120 2931 -1 
 Ràng buộc: 
 Có 40 % số test ứng với 40% số điểm có 2 ≤ 𝑁 ≤ 103 
 Có 30% số test khác ứng với 30% số điểm có 103 ≤ 𝑁 ≤ 105 
 Có 20% số test khác ứng với 20% số điểm có 105 ≤ 𝑁 ≤ 109 
 Có 10% số test khác ứng với 10% số điểm có 109 ≤ 𝑁 ≤ 1018 
--------------HẾT--------------- 
Thí sinh không sử dụng tài liệu để làm bài 
Cán bộ coi thi không giải thích gì thêm 
Họ và tên thí sinh :_________________________________________ Số báo danh: ________________________