Đề 3 thi phần lập trình - Bảng B thời gian làm bài: 120 phút, không kể thời gian giao đề

HỘI THI TIN HỌC TRẺ
TỈNH VĨNH PHÚC
LẦN THỨ XI - NĂM 2016
ĐỀ THI PHẦN LẬP TRÌNH - BẢNG B
Thời gian làm bài: 120 phút, không kể thời gian giao đề
————————————
TỔNG QUAN
STT
Tên bài
File chương trình
File dữ liệu
File kết quả
Điểm
Thời gian
1
Tìm cặp số
PON.***
PON.INP
PON.OUT
20
1s/test
2
Biến đổi dãy số
CHANGE.***
CHANGE.INP
CHANGE.OUT
20
1s/test
3
Chữ số tận cùng
NUMBER.***
NUMBER.INP
NUMBER.OUT
30
1s/test
Lưu ý:
- Thí sinh thay “.***” bằng “.PAS” hoặc “.CPP” tuỳ thuộc theo ngôn ngữ lập trình mà thí sinh lựa chọn là Turbo Pascal (Free Pascal) hoặc C/C++;
- Thí sinh đặt đúng tên file theo yêu cầu;
- Đề thi có 02 trang.
Lập chương trình giải các bài toán sau:
Bài 1. Tìm cặp số.
Ước số chung lớn nhất của 2 số nguyên dương a và b (ký hiệu là ƯCLN(a, b)) là số nguyên lớn nhất p mà a và b đều chia hết cho p. Bội số chung nhỏ nhất của 2 số nguyên dương a và b (ký hiệu là BCNN(a, b)) là số nguyên dương nhỏ nhất q mà q đồng thời chia hết cho a và b. Ví dụ: ƯCLN(15, 20) = 5; BCNN(15, 20) = 60.
Tùng nhanh chóng nhận ra rằng có những cặp số nguyên có cùng ƯCLN và BCNN. Với 2 số nguyên dương a, b cho trước, Tùng muốn tìm cặp số x và y gần nhau nhất, tức là y - x nhỏ nhất và ƯCLN(a, b) = ƯCLN(x, y), BCNN(a, b) = BCNN(x, y). 
Yêu cầu: Với a và b cho trước hãy xác định x và y.
Dữ liệu vào: (PON.INP)
Dòng 1: Ghi 2 số nguyên a và b (1 ≤ a, b ≤ 109), mỗi số cách nhau ít nhất 1 ký tự trắng.
Kết quả: (PON.OUT)
Dòng 1: Ghi số nguyên x và y tìm được (1 ≤ x ≤ y), mỗi số cách nhau ít nhất 1 ký tự trắng.
Ví dụ:
PON.INP
PON.OUT
3 10
5 6
Bài 2. Biến đổi dãy số.
Sơn là người yêu thích Toán học và thường được cô giáo gọi lên bảng giải những bài rất khó. Hôm nay cô giáo viết lên bảng dãy số nguyên không âm a1, a2, . . ., an và yêu cầu dùng ít phép biến đổi nhất để đưa về dãy số mới sao cho trong đó có k số liên tiếp nhau tạo thành một dãy tăng dần từ 1 đến k, tức là tồn tại i sao cho ai = 1, ai+1 = 2, . . ., ai+k-1 = k. Nội dung mỗi phép biến đổi là xóa một số tùy chọn và thay nó bằng số mới lớn hơn số cũ một đơn vị.
Dĩ nhiên, anh bạn Sơn của chúng ta lại được cô giáo gọi lên bảng.
Yêu cầu: Hãy xác định số phép biến đổi tối thiểu mà Sơn cần thực hiện hoặc đưa ra số -1 nếu không tồn tại cách nhận được dãy số mới theo yêu cầu.
Dữ liệu vào: (CHANGE.INP)
Dòng 1: Ghi 2 số nguyên n và k (1 ≤ k ≤ n ≤ 200 000).
Dòng 2: Ghi n số nguyên a1, a2, . . ., an (0 ≤ ai ≤ n; ).
Kết quả: (CHANGE.OUT)
Ghi một số nguyên là kết quả tìm được.
Ví dụ:
CHANGE.INP
CHANGE.OUT
4 3
1 1 0 2
3
Bài 3. Chữ số tận cùng.
Hai anh em Tùng và Sơn rất thích chơi những trò chơi liên quan đến con số. Một hôm Sơn nói: “Nếu anh chọn một chữ số, em chọn một chữ số thì chữ số tận cùng của tích hai số anh em mình chọn là số nào nhỉ?”. Là một người yêu thích Toán học, Sơn yêu cầu anh phải chọn số thật lớn để thử khả năng tính toán của anh mình. Bạn hãy giúp Tùng tìm chữ số tận cùng đó nhé.
Yêu cầu: Cho hai số , hãy tìm chữ số tận cùng của tích .
Dữ liệu vào: (NUMBER.INP)
Dòng 1: Ghi số tự nhiên t.
Dòng 2: Ghi số tự nhiên s.
Kết quả: (NUMBER.OUT)
Ghi một chữ số là kết quả tìm được.
Ví dụ:
NUMBER.INP
NUMBER.OUT
15122011
14102015
5
=Hết=
(Cán bộ coi thi không giải thích gì thêm)
Họ và tên thí sinh:SBD:..