HSG lớp 9 Hòa Bình 2021-2022

ĐỀ THI CHỌN HỌC SINH GIỎI LỚP 9 TỈNH HÒA BÌNH Năm học 2021 - 2022

MÔN TIN HỌC 4 bài: TICKET, ARRAY, SHOES, INSTRUCK

Bài 1. Phiếu giảm giá

Để thu hút khách hàng, Siêu thị điện máy cho đặt một máy tính ngay cạnh lối vào. Trên màn hình của máy tính hiển thị số nguyên n có 4 chữ số (không có số 0 ở đầu) và cho biết số này nhận được từ số nguyên X có 4 chữ số có nghĩa bằng cách cộng 2 chữ số đầu của X và 2 chữ số cuối của X sau đó viết liên tiếp 2 số nhận được thành số hiển thị trên màn hình, trong đó số lớn hơn được viết trước. Ví dụ X = 3165 thì 2 số nhận được sẽ là 3 + 1 = 4 và 5 + 6 = 11 và kết quả hiển thị trên màn hình sẽ là 114.

Khách hàng phải có nhiệm vụ nạp vào máy tính số nguyên nhỏ nhất có 4 chữ số (không có các số 0 không có nghĩa), từ đó tạo ra kết quả đã nêu trên màn hình. Nếu không tồn tại số phù hợp thì nạp vào số 0. Nếu khách hàng trả lời đúng trong phạm vi chờ đợi của máy thì sẽ nhận được một phiếu giảm giá khi mua hàng trong Siêu thị.

Em hãy viết chương trình xác định số cần đưa vào để nhận được phiếu giảm giá.

Dữ liệu vào: số nguyên n có 4 chữ số.

Kết quả ra: số cần đưa vào để nhận được phiếu giảm giá hoặc số 0 nếu không tồn tại số cần tìm.

Ví dụ:

TICKET.INP	TICKET.OUT
`1311`	`2949`
`2304`	`0`

Giải thích ví dụ 1: x = 2949 thì 2 số nhận được sẽ là 2 + 9 = 11, 4 + 9 = 13 và kết quả hiển thị trên màn hình là 1311.

Bài 2. Dãy số

Thầy giáo cho bạn An một dãy số gồm n số nguyên a₁, a₂, a₃, …, aₙ và yêu cầu An thực hiện thao tác quay dãy số bằng cách chuyển số đầu tiên xuống cuối dãy. An rất thích thú với thao tác này vì quá dễ đối với cậu. Tuy nhiên, để tăng độ khó thầy yêu cầu An tìm số đầu tiên của dãy số sau khi thực hiện k lần quay dãy số.

Em hãy lập trình giúp bạn An giải bài toán của thầy giáo.

Dữ liệu vào:

Dòng 1 chứa hai số nguyên n, k (1 ≤ n ≤ 10⁶; 1 ≤ k ≤ 10⁹);
Dòng 2 chứa n số nguyên a₁, a₂, a₃, …, aₙ.

Kết quả ra: một số nguyên là kết quả của bài toán.

Ví dụ:

ARRAY.INP	ARRAY.OUT
`6 4` `1 2 3 4 5 6`	`5`

Ràng buộc:

Subtask 1: 60% số test ứng với k < n;
Subtask 2: 20% số test tiếp theo ứng với 1 ≤ n ≤ 100; 1 ≤ k ≤ 10⁴;
Subtask 3: 20% số test còn lại không có ràng buộc gì.

Bài 3. Chọn giày

Một ngày Cristiano Ronaldo muốn đếm lại xem hiện tại mình đang có bao nhiêu chiếc giày. Sau khi kiểm tra, Ronaldo còn n chiếc giày, chiếc thứ i có màu độ sáng Sᵢ (i = 1..n), số càng lớn thì màu càng sáng.

Mỗi trận đấu Ronaldo lấy ra một đôi sử dụng, sau trận đấu đó, anh tháo giày và tặng lại cho các fan hâm mộ của mình. Hai chiếc giày mà anh chọn phải có độ sáng chênh lệch nhau không quá d, tức là 2 chiếc giày thứ i và j (i ≠ j) có thể được chọn nếu |Sᵢ − Sⱼ| ≤ d.

Em hãy viết chương trình tính giúp Ronaldo xem với n chiếc giày hiện có anh ấy sẽ đá được tối đa bao nhiêu trận đấu.

Dữ liệu vào:

Dòng 1 chứa hai số nguyên n, d (1 ≤ n ≤ 2×10⁵; 1 ≤ d ≤ 10⁶);
Dòng 2 chứa n số nguyên S₁, S₂, S₃, …, Sₙ (0 ≤ Sᵢ ≤ 10⁶, i = 1..n).

Kết quả ra: một số nguyên là kết quả của bài toán.

Ví dụ:

SHOES.INP	SHOES.OUT
`6 0` `3 1 5 1 1 1`	`2`
`6 2` `3 1 2 4 1 1`	`3`

Giải thích ví dụ 2: Ronaldo sẽ chọn các đôi giày có độ sáng là (3, 1), (2, 4), (1, 1). Anh cũng có thể chọn các đôi giày có độ sáng là (1, 2), (3, 4), (1, 1).

Ràng buộc:

Subtask 1: 50% số test tương ứng với d = 0;
Subtask 2: 30% số test tiếp theo tương ứng với n ≤ 1000;
Subtask 3: 20% số test còn lại không có ràng buộc gì.

Bài 4. Bé làm toán

Bạn An sẽ kết thúc chương trình tiểu học trong năm học này. Bài kiểm tra cuối cùng của cậu là bài kiểm tra toán. Cậu chuẩn bị rất kỹ lưỡng cho bài kiểm tra này. Anh trai của cậu giúp đỡ bằng cách cho cậu một bài tập.

Trong bài tập này, người anh viết ra dãy số theo thứ tự lần lượt có 1 số 1, 2 số 2, 3 số 3, và liên tục như vậy được một dãy vô hạn. Dưới đây là một vài số đầu tiên của dãy mà người anh viết:

1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, …

Bây giờ, người anh cho An hai số nguyên A, B và hỏi rằng tổng các số trong dãy có chỉ số từ A đến B bằng bao nhiêu? Ví dụ, nếu A = 1 và B = 3 thì nó là tổng của ba số đầu tiên kết quả là 1 + 2 + 2 = 5.

Em hãy viết chương trình giúp bạn An tính tổng theo yêu cầu của người anh.

Dữ liệu vào: một dòng duy nhất chứa hai số nguyên A, B (1 ≤ A ≤ B ≤ 10⁹).

Kết quả ra: một dòng duy nhất là số dư của tổng cho (10⁹ + 7).

Ví dụ:

INSTRUCK.INP	INSTRUCK.OUT
`1 3`	`5`
`3 7`	`15`
`50 50`	`10`

Giải thích ví dụ 2: tổng các số từ vị trí 3 đến vị trí 7 là: 2 + 3 + 3 + 3 + 4 = 15. Vậy kết quả in ra là 15 mod (10⁹ + 7) = 15.

Ràng buộc:

Subtask 1: 50% số test tương ứng với 1 ≤ A ≤ B ≤ 100;
Subtask 2: 30% số test tiếp theo tương ứng với 1 ≤ A ≤ B ≤ 10⁵;
Subtask 3: 20% số test còn lại không có ràng buộc gì.

Th.S Trần Huy Phúc

Kỹ sư phần mềm @Adnovum & Bumbii Academy

Học Tiếng Anh với Bumbii English