HSG lớp 9 Bình Dương 2021-2022

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

MÔN TIN HỌC 4 câu: CHOHANG, VONGTAY, TINHTOAN, LEHOI

Câu 1. Chở hàng

Mẹ nhờ Bo ra chợ lấy hàng hóa để chuẩn bị bán hàng vào dịp Tết sắp đến. Do chưa biết hàng hóa được đóng gói như thế nào nên Bo mang theo thùng chứa hàng chứa được tối đa N kg. Khi đến điểm bán hàng, Bo thấy cửa hàng chỉ đóng gói hàng vào 02 loại hộp A kg và B kg.

Yêu cầu: Bạn hãy giúp Bo tính toán số kg hàng hóa tối đa mà Bo có thể chở một chuyến, biết rằng số kg hàng hóa của cửa hàng đang có nhiều hơn khả năng chở hàng của thùng trên xe Bo.

Dữ liệu vào: Số nguyên N, A, B (1 ≤ A, B, N ≤ 1000).

Kết quả: Một số nguyên duy nhất là số kg hàng hóa tối đa mà Bo có thể chở một chuyến.

Ví dụ:

CHOHANG.INP	CHOHANG.OUT	Giải thích
`77 17 25`	`76`	Bo sẽ chở 3 gói hàng 17 kg và 1 gói hàng 25 kg

Câu 2. Vòng tay

Để có tiền đi chơi lễ hội trong mùa xuân năm nay, Bo quyết định làm các vòng tay để bán cho du khách. Bo tham gia khóa học kết các vòng tay của một cửa hàng. Bo muốn ghi chép lại các kiểu kết vòng tay nên quy ước mỗi loại hạt dùng để kết vòng tay là một con số từ 1 đến 9. Một vòng tay được kết từ một dãy các hạt mẫu lặp đi lặp lại k lần và luôn kết thúc bằng hạt cùng loại với hạt bắt đầu. Bạn hãy giúp Bo tìm số lượng các hạt trong dãy hạt mẫu để Bo dễ dàng kết vòng tay nhé.

Dữ liệu vào: Số nguyên N (1 ≤ N ≤ 100) và một dãy aᵢ (1 ≤ aᵢ ≤ 9) là các hạt được kết trong vòng tay.

Kết quả: Một số nguyên duy nhất là số lượng các hạt trong dãy hạt mẫu.

Ví dụ:

VONGTAY.INP	VONGTAY.OUT	Giải thích
`13` `5 3 1 3 5 2 5 3 1 3 5 2 5`	`6`	Dãy hạt mẫu là 5 3 1 3 5 2 có 6 hạt

Câu 3. Tính toán

Bo quyết định mua nguyên liệu kết vòng tay để bán cho du khách. Đầu tiên, Bo vay tiền của bạn bè để mua nguyên liệu và khi bán được vòng tay sẽ trả lại tiền đã vay. Bo liệt kê tất cả N các khoản tiền bán vòng tay và các khoản vay từ bạn bè trong sổ ghi chép được đánh số vị trí từ 1 đến N.

Khi có đủ tiền trả cho khoản vay thì Bo sẽ trả ngay cho người mình đang vay không nhất thiết phải bán hết vòng tay mới trả. Bo luôn bắt đầu ở vị trí 0 và kết thúc phải là vị trí cuối cùng trong danh sách liệt kê. Hãy giúp Bo tìm số bước ngắn đi nhất để thu tiền bán vòng tay và trả tất cả nợ cho bạn bè. Trong trường hợp Bo không đủ tiền trả các khoản vay thì Bo quay về vị trí cuối cùng và vẫn còn nợ.

Dữ liệu vào: Số nguyên N (1 ≤ N ≤ 10⁵) và N số nguyên aᵢ (−10³ ≤ aᵢ ≤ 10³).

Dữ liệu xuất: Một số nguyên duy nhất là số bước ngắn nhất Bo phải đi.

Ví dụ:

TINHTOAN.INP	TINHTOAN.OUT	Giải thích
`5` `100 -200 250 -200 150`	`9`	Bắt đầu 100 -200 250 -200 150 - Đi 1 đơn vị nhận được 100 (số bước: 1) - Đi tiếp 2 đơn vị nhận được 350 (số bước: 3) - Quay lại 1 đơn vị trả 200 còn lại 150 (số bước: 4) - Đi tiếp 3 đơn vị nhận được 150 (số bước: 7) - Quay lại 1 đơn vị và trả 200 (số bước: 8)
`5` `100 -200 250 -200 10`	`7`	Bắt đầu 100 -200 250 -200 10 - Đi 1 đơn vị nhận được 100 (số bước: 1) - Đi tiếp 2 đơn vị nhận được 350 (số bước: 3) - Quay lại 1 đơn vị trả 200 còn lại 150 (số bước: 4) - Đi tiếp 3 đơn vị nhận được 10 (số bước: 7)

Câu 4. Lễ hội

Đã đến lễ hội mùa xuân, Bo rất vui vì đã có đủ tiền tham gia lễ hội. Trong rất nhiều trò chơi được tổ chức, Bo muốn sắp xếp thời gian để có thể tham gia nhiều trò chơi nhất có thể mà không trùng về mặt thời gian.

Yêu cầu: Hãy giúp Bo xác định số lượng trò chơi nhiều nhất mà Bo có thể tham gia.

Dữ liệu vào:

Dòng đầu ghi số nguyên N (1 ≤ N ≤ 1000) là số lượng trò chơi;
N dòng tiếp theo, dòng thứ i ghi hai số nguyên aᵢ, bᵢ (1 ≤ aᵢ ≤ bᵢ ≤ 10; i = 1..N) là thời gian bắt đầu và kết thúc của trò chơi thứ i.

Ví dụ:

LEHOI.INP	LEHOI.OUT	Giải thích
`6` `3 8` `9 12` `6 10` `1 4` `2 7` `11 4`	`3`	Đầu tiên Bo tham gia trò chơi thứ 4, sau đó tham gia trò chơi thứ 3 và cuối cùng tham gia trò chơi thứ 6.

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