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

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

MÔN TIN HỌC 4 bài: FBALL, BPAIRS, DOOR, TOWER

Bài 1. Giải bóng đá

Giải bóng đá phong trào khối lớp 9 của trường Trung học cơ sở HB có ba đội tham gia là A, B, C. Giải được tổ chức theo thể thức thi đấu vòng tròn tính điểm: A gặp B, A gặp C, B gặp C. Điểm mỗi trận được tính theo luật của FIFA: Đội thắng được 3 điểm, đội thua được 0 điểm, nếu hòa thì mỗi đội được 1 điểm.

Kết quả trận A gặp B có tỉ số là p : q - Đội A ghi được p bàn thắng và thủng lưới q lần, kết quả trận A gặp C có tỉ số r : s - Đội A ghi được r bàn thắng và bị thủng lưới s lần, kết quả trận B gặp C có tỉ số u : v - Đội B ghi được u bàn và bị thủng lưới v lần.

Cho biết các số p, q, r, s, u, v, hãy tính và đưa ra số điểm của mỗi đội.

Dữ liệu vào: Các số p, q, r, s, u, v (0 ≤ p, q, r, s, u, v ≤ 20).

Kết quả ra: Ghi ba số lần lượt là số điểm của ba đội A, B, C.

Ví dụ:

FBALL.INP	FBALL.OUT
`9 7 7 5 4 8`	`6 0 3`

Bài 2. Cặp số đẹp

Nội dung số học là một trong những chủ đề thú vị được khai thác rất nhiều trong các bài toán Tin học. Người ta có thể đưa ra những khái niệm mới đối với các số nguyên trong Tin học, ví dụ: số phong phú là số X mà tổng các ước (không kể chính nó) của nó lớn hơn X, hoặc cặp số bạn bè là cặp (a, b) mà tổng các ước (không tính a, b) của số này bằng số kia, …. Trong bài toán này, chúng ta định nghĩa cặp số đẹp (a, b) là cặp số mà tổng các chữ số của a và b bằng nhau, ví dụ: (14, 23) là cặp số đẹp vì 1 + 4 = 2 + 3, còn hai số (14, 25) không phải cặp số đẹp vì 1 + 4 ≠ 2 + 5.

Cho dãy số nguyên dương gồm n phần tử a₁, a₂, …, aₙ. Hãy đếm số lượng cặp số đẹp có trong dãy.

Dữ liệu vào:

Dòng thứ nhất chứa số nguyên dương n (1 ≤ n ≤ 3×10⁵);
Dòng thứ hai chứa n số nguyên dương a₁, a₂, …, aₙ (aᵢ ≤ 10⁹). Các số cách nhau bởi dấu cách.

Kết quả ra: Một số nguyên duy nhất là số lượng cặp số đẹp tìm được.

Ví dụ:

BPAIRS.INP	BPAIRS.OUT
`5` `3 8 21 17 12`	`4`

Giải thích: Có 4 cặp số đẹp là (3, 21), (8, 17), (21, 12), (3, 12).

Giới hạn:

Subtask 1: Có 70% số test đầu tiên n ≤ 1000.
Subtask 2: Có 30% số test còn lại n ≤ 3×10⁵.

Bài 3. Mở cửa

Tầng áp mái thường được sử dụng như nhà kho lưu trữ các giấy tờ, đồ đạc cũ và ít ai lên đó. Hôm nay, Bình có việc cần lên đó tìm cuốn album lưu ảnh của những thế hệ trước trong gia đình.

Ổ khóa mở cánh cửa có hai núm xoay hình tròn, núm thứ nhất đang chỉ tới số a, núm thứ hai đang chỉ tới số b. Các núm chỉ có thể xoay theo chiều kim đồng hồ. Khi xoay một vòng, số được chỉ sẽ tăng thêm 1. Cánh cửa sẽ mở khi các số a và b nhận được có ước chung khác 1.

Đáng tiếc, do để lâu không dùng núm thứ nhất bị kẹt, không xoay được và vì vậy luôn chỉ tới số a. Như vậy chỉ có thể xoay núm thứ hai.

Hãy xác định số vòng xoay tối thiểu cần thực hiện của núm thứ hai để mở cửa.

Dữ liệu vào:

Dòng thứ nhất chứa số nguyên n là số cặp a, b (1 ≤ n ≤ 100);
Dòng thứ i trong n dòng sau chứa 2 số nguyên a và b, ghi cách nhau một dấu cách (2 ≤ a, b ≤ 10⁹).

Kết quả ra: Với mỗi test đã cho đưa ra trên một dòng một số nguyên là lời giải tìm được.

Ví dụ:

DOOR.INP	DOOR.OUT
`3` `15 7` `23 11` `35 42`	`2` `12` `0`

Ràng buộc:

Subtask 1: 50% số test tương ứng với n = 1, 1 ≤ a, b ≤ 10⁵;
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ì.

Bài 4. Xếp tháp

Hội thi Olympic Khoa học viễn tưởng là hội thi thường niên diễn ra giữa các trường Trung học cơ sở trên cả nước, ngoài nội dung thi kiến thức học sinh giỏi, Ban tổ chức còn có nội dung thi vận động dành cho các bạn học sinh. Năm nay, hội thi được tổ chức tại trường Ngôi Sao - thành phố XYZ. Ban tổ chức sẽ có một trò chơi vận động mới đó là cuộc thi xếp tháp dành cho các đội chơi.

Mỗi đội chơi sẽ được Ban tổ chức cung cấp n khối hộp, và các đội phải xếp thành các tòa tháp thỏa mãn các yêu cầu sau:

Mỗi đội nhận khối hộp đầu tiên và tạo tháp đầu tiên.
Khi nhận được một khối hộp các đội phải xếp luôn vào tháp đã có hoặc tạo ra một tháp mới, sau đó mới được nhận khối hộp tiếp theo từ Ban tổ chức.
Các tòa tháp phải thỏa mãn điều kiện khối hộp ở trên có thể tích không lớn hơn khối hộp ở ngay dưới nó.
Không được chuyển khối hộp từ tòa tháp này sang tòa tháp khác.
Mỗi đội cần phải xếp được càng ít tòa tháp càng tốt.

Bạn là một thành viên của trường Trung học cơ sở HB tham gia cuộc thi xếp tháp, nhiệm vụ của bạn và đồng đội của mình là xếp được các tòa tháp thỏa mãn điều kiện của Ban tổ chức đưa ra.

Dữ liệu vào:

Dòng đầu tiên chứa số nguyên dương n là số lượng các khối hộp mà Ban tổ chức cung cấp cho trường Trung học cơ sở HB.
Dòng thứ hai chứa n số nguyên dương a₁, a₂, …, aₙ (aᵢ ≤ 10⁹) là thể tích của các khối hộp.

Kết quả ra: Một dòng duy nhất là số lượng tòa tháp ít nhất được tạo thành.

Ví dụ:

TOWER.INP	TOWER.OUT
`5` `3 8 5 2 2`	`2`

Giải thích ví dụ (các tháp liệt kê từ dưới lên trên):

Các khối hộp	Các tháp tạo được
Khối hộp thứ nhất: 3	Tháp 1: 3
Khối hộp thứ hai: 8	Tháp 1: 3 - Tháp 2: 8
Khối hộp thứ ba: 5	Tháp 1: 3 - Tháp 2: 8, 5
Khối hộp thứ tư: 2	Tháp 1: 3 - Tháp 2: 8, 5, 2
Khối hộp thứ năm: 2	Tháp 1: 3, 2 - Tháp 2: 8, 5, 2

Giới hạn:

Subtask 1: 70% số test tương ứng với 1 ≤ n ≤ 1000;
Subtask 2: 30% số test tiếp theo tương ứng với 1 ≤ n ≤ 3×10⁵.

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