Bảng B 2023 - Thành phố Vũng Tàu

HỘI THI TIN HỌC TRẺ THÀNH PHỐ VŨNG TÀU Năm 2023

ĐỀ THI THỰC HÀNH BẢNG B – KHỐI THCS Thời gian: 120 phút (không kể thời gian phát đề)

Tổng quan bài thi

STT	Tên bài	File chương trình	File dữ liệu	File kết quả
1	Chia bánh	CAKES.*	CAKES.INP	CAKES.OUT
2	Mua sách	BOOKS.*	BOOKS.INP	BOOKS.OUT
3	Đếm dãy con liên tiếp	CNTSEQ.*	CNTSEQ.INP	CNTSEQ.OUT

(Dấu * được thay thế bởi ngôn ngữ lập trình Pascal, C/C++ hoặc Python tương ứng.)

Bài 1: Chia bánh (6 điểm)

Với mong muốn kỳ thi Tin học trẻ cấp thành phố sẽ là sân chơi bổ ích và vui vẻ cho các bạn học sinh, BTC đã mua N chiếc bánh kem nhỏ xinh để thưởng cho các bạn thí sinh. Vấn đề là BTC muốn tìm ra tất cả các cách chia đều số bánh kem trên cho các bạn mà không cần phải cắt bất kỳ chiếc bánh nào.

Yêu cầu: Hãy giúp BTC tìm tất cả các cách chia cho các bạn thí sinh thoả mãn điều kiện trên.

Dữ liệu: Đọc vào từ file CAKES.INP: một dòng duy nhất chứa số nguyên N (1 ≤ N ≤ 10¹²).

Kết quả: Ghi ra file CAKES.OUT: ghi ra đáp án theo thứ tự tăng dần, mỗi số trên một dòng.

Ví dụ:

CAKES.INP	CAKES.OUT
`6`	`1` `2` `3` `6`

Giải thích: Với 6 chiếc bánh, BTC có các cách chia đều như sau: 1 bạn (6 chiếc), 2 bạn (mỗi bạn 3 chiếc), 3 bạn (mỗi bạn 2 chiếc), 6 bạn (mỗi bạn 1 chiếc).

Bài 2: Mua sách (7 điểm)

Trong khi đợi BTC khai mạc hội thi, Nam ghé vào một hiệu sách gần trường để mua sách. Hiệu sách đặc biệt này bán n cuốn sách khác nhau. Người bán hàng luôn ghi rõ giá tiền và số trang của mỗi cuốn sách tương ứng trên kệ. Với số tiền đang có, Nam đã quyết định rằng tổng số tiền mua sách của Nam sẽ nhiều nhất là x.

Yêu cầu: Hãy giúp Nam tính xem với quyết định của cậu thì số trang sách tối đa Nam có thể mua là bao nhiêu? Nam chỉ mua mỗi cuốn sách nhiều nhất một lần.

Dữ liệu: Đọc vào từ file BOOKS.INP:

Dòng đầu tiên chứa hai số nguyên n (1 ≤ n ≤ 1000) và x (1 ≤ x ≤ 10⁵): tương ứng với số lượng sách và tổng số tiền tối đa.
Dòng tiếp theo chứa n số nguyên h₁, h₂, …, hₙ (1 ≤ hᵢ ≤ 1000): tương ứng với giá của mỗi cuốn sách.
Dòng cuối cùng chứa n số nguyên s₁, s₂, …, sₙ (1 ≤ sᵢ ≤ 1000): tương ứng với số trang của mỗi cuốn sách.

Hai số liên tiếp trên cùng dòng được ghi cách nhau bởi dấu cách.

Kết quả: Ghi ra file BOOKS.OUT: một số nguyên là số trang sách nhiều nhất mà Nam có thể mua theo yêu cầu.

Ví dụ:

BOOKS.INP	BOOKS.OUT
`4 13` `5 8 4 3` `6 12 8 2`	`20`

Giải thích: Nam có thể mua quyển sách 2 và 3. Giá của chúng là 8 + 4 = 12 và số trang là 12 + 8 = 20.

Bài 3: Đếm dãy con liên tiếp (7 điểm)

Cho dãy số A có n số nguyên a₁, a₂, …, aₙ. Một dãy con liên tiếp các số hạng của dãy A là dãy các số hạng từ số hạng aᵢ đến số hạng aⱼ (1 ≤ i ≤ j ≤ n).

Yêu cầu: Hãy cho biết dãy A có bao nhiêu dãy con liên tiếp mà giá trị tuyệt đối của tổng các số hạng trong dãy con đó lớn hơn một số nguyên dương S cho trước.

Dữ liệu: Vào từ file văn bản CNTSEQ.INP:

Dòng thứ nhất chứa hai số nguyên dương n và S (n ≤ 10⁵, S ≤ 10¹⁴).
Dòng thứ hai chứa n số nguyên a₁, a₂, …, aₙ (|aᵢ| ≤ 10⁹).

Hai số liên tiếp trên cùng dòng được ghi cách nhau bởi dấu cách.

Kết quả: Ghi ra file văn bản CNTSEQ.OUT trên một dòng, một số nguyên duy nhất là số dãy con liên tiếp thoả mãn yêu cầu của bài toán.

Ví dụ:

CNTSEQ.INP	CNTSEQ.OUT
`4 4` `5 -2 8 -6`	`6`

Giải thích: Trong ví dụ có 6 dãy con thoả mãn yêu cầu là: (5), (8), (−6), (−2; 8), (5; −2; 8) và (5; −2; 8; −6).

Ràng buộc:

Có 50% số test ứng với 50% số điểm của bài có n ≤ 100.
Có 30% số test khác ứng với 30% số điểm của bài có n ≤ 10³.
Có 20% số test còn lại ứng với 20% số điểm của bài có n ≤ 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