Bảng B 2020 - Tỉnh Tiền Giang

HỘI THI TIN HỌC TRẺ TỈNH TIỀN GIANG
Lần thứ XXVI – Năm học 2019-2020

ĐỀ THI BẢNG B – THCS
(Free Pascal hoặc C++)
Thời gian làm bài: 120 phút
Ngày thi: 25/07/2020

Bài 1. Cung cấp nước sạch miễn phí (4 điểm)

Do tình hình hạn hán xảy ra ở các tỉnh miền tây, một số nhà dân ở vùng sâu, phương tiện đi lại khó khăn, nên việc vận chuyển nước sạch đến nhà dân cũng gặp khó khăn. Ông A giám đốc công ty ABC quyết định dự trữ nước vào thùng để chở đi phát đến các hộ dân ở vùng hạn mặn. Vì phải chở làm nhiều đợt nên có N (1 ≤ N ≤ 1000) thùng chứa nước có kích thước khác nhau, mỗi thùng có sức chứa Cᵢ (1 ≤ Cᵢ ≤ 10000, 1 ≤ i ≤ N). Dự đoán rằng năm nay sẽ có đợt hạn kéo dài, Ông A muốn dự trữ nước nên đổ đầy hết các thùng. Sau khi kiểm tra ông thấy rằng có một số thùng vẫn còn đầy, một số khác thì vơi đi một phần, còn một số thì đã hết. Ông quyết định các thùng nào chưa đầy thì sẽ đổ đầy nước. Nhưng do nơi cấp nước phải đi xa, và mỗi lần chỉ chở đi được một thùng, ông quyết định sẽ sang nước giữa các thùng với nhau để số thùng phải chở đi là ít nhất.

Yêu cầu: Cho dung lượng nước hiện có của thùng thứ i là Bᵢ (0 ≤ Bᵢ ≤ Cᵢ, 1 ≤ i ≤ N), hãy giúp ông A xác định số lượng thùng ít nhất phải mang đi.

Dữ liệu vào:

Dòng thứ nhất: số tự nhiên N là số lượng các thùng nước.
Dòng thứ i trong N dòng tiếp theo: 2 số nguyên Bᵢ và Cᵢ (0 ≤ Bᵢ ≤ Cᵢ), cách nhau ít nhất một khoảng trắng.

Kết quả: Một số là số lượng ít nhất các thùng nước phải mang đi.

Ví dụ:

Dữ liệu vào:

Kết quả ra: 2

Bài 2. Đếm số xâu con (3 điểm)

Cho xâu A có chiều dài N ký tự. Xâu chỉ gồm hai loại ký tự là 'X' và 'Y'. Một xâu B được gọi là xâu con của A nếu:

B là một đoạn ký tự liên tiếp của A;
Có chiều dài L ≤ M (M cho trước);
Có đúng K ký tự 'X'.

Ví dụ: Xâu A là YXYXYXXYYY. Với M=5 và K=3 thì xâu XYXX là xâu con.

Yêu cầu: Hãy tìm số lượng xâu con của xâu A.

Dữ liệu vào:

Dòng 1: 3 số N M K (0 < N ≤ 1000000; 0 < L ≤ M ≤ 14; 0 < K ≤ M). N là độ dài của A, M là chiều dài lớn nhất của các xâu con B, K là số lượng ký tự 'X' cần có.
Dòng 2: N kí tự của xâu A, viết liền nhau.

Kết quả: Số lượng xâu con tìm được.

Ví dụ:

Dữ liệu vào:

30 14 4
YYXYYYXXXXXXYYXXYYYXYYXYXYXYXY

Kết quả ra: 41

Bài 3. Cặp số bạn bè cùng nhóm (3 điểm)

Cặp số (x, y) được gọi là cặp số bạn bè cùng nhóm thỏa các điều kiện sau:

ƯCLN(x, y) = 1;
Số đảo của số x là số y và ngược lại;
Số x và y là các số có thể gồm từ 2 đến k chữ số (2 ≤ k ≤ 4) và được tạo thành từ n (4 ≤ n ≤ 9) chữ số của hệ thập phân cho trước khác nhau.

Dữ liệu vào:

Dòng 1: số n và k.
Dòng 2: n chữ số thập phân cho trước.

Kết quả:

Các dòng đầu: liệt kê các cặp số đôi bạn.
Dòng cuối: tổng số đôi bạn.

Ví dụ:

Dữ liệu vào:

4 2
4 6 5 3

Kết quả ra:

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