Bảng B 2020 - Vòng sơ khảo quốc gia (đợt 11/10)

HỘI THI TIN HỌC TRẺ TOÀN QUỐC LẦN THỨ XXVI
Năm 2020

ĐỀ THI VÒNG SƠ KHẢO QUỐC GIA — BẢNG B - THCS
Thời gian làm bài 120 phút, không kể thời gian phát đề
Ngày thi: 11/10/2020 — Điểm thi: Trường Cao đẳng Viễn Đông

Tổng quan

Tên bài	File chương trình	Điểm
Bài 1. Bánh trung thu	mooncake.*	100 điểm
Bài 2. Bảng quảng cáo	adwins.*	100 điểm

Bài 1. Bánh trung thu (100 điểm)

Dựa trên ý tưởng của búp bê Nga Matrioska, công ty bánh Trung Thu có sản xuất những hộp bánh đặc biệt như sau: Trong một hộp bánh có thể chứa những hộp bánh nhỏ hơn, hộp bánh nhỏ nhất sẽ chứa bánh trung thu. Giả sử bánh trung thu là hộp bánh cấp 0, hộp bánh cấp 1 sẽ chứa những hộp bánh cấp 0 (bánh trung thu), hộp bánh cấp i (i ≥ 1) sẽ chứa a_i hộp bánh cấp i − 1. Thấy ý tưởng rất độc đáo nên Bờm cũng đã mua một hộp bánh cấp N về để mở tiệc trung thu cho các bạn nhỏ.

Bờm muốn biết số lần mở hộp ít nhất để lấy được X chiếc bánh trung thu. Vì Bờm vẫn chưa biết có bao nhiêu bạn nhỏ tham gia tiệc trung thu nên để không tốn thời gian tính toán, Bờm sẽ chuẩn bị trước nhiều phương án.

Yêu cầu: Cho M phương án, với phương án thứ j (1 ≤ j ≤ M) cần X_j bánh trung thu, bạn hãy giúp Bờm tính xem cần ít nhất bao nhiêu lần mở hộp?

Dữ liệu: Vào từ thiết bị vào chuẩn theo khuôn dạng sau:

Dòng đầu tiên chứa hai số nguyên N và M (1 ≤ N, M ≤ 3×10⁵) là cấp của hộp bánh của Bờm và số phương án cần tính toán;
Dòng thứ hai chứa N số nguyên a_i (1 ≤ a_i ≤ 10⁹; 1 ≤ i ≤ N) mô tả hộp bánh cấp i sẽ chứa a_i hộp bánh cấp i − 1;
Dòng thứ ba chứa M số nguyên X_j (1 ≤ X_j ≤ 10¹²; 1 ≤ j ≤ M) tương ứng với số bánh trung thu cần lấy ra trong mỗi phương án.

Kết quả: Ghi ra thiết bị ra chuẩn gồm M dòng, dòng thứ j in ra số lần mở hộp ít nhất để lấy được X_j bánh trung thu.

Dữ liệu vào	Kết quả ra
3 3 3 3 3 2 8 13	3 5 8

Giải thích: Hộp bánh cấp 1 có 3 bánh trung thu. Hộp bánh cấp 2 chứa 3 hộp bánh cấp 1. Hộp bánh cấp 3 chứa 3 hộp bánh cấp 2.

Để lấy được 2 bánh trung thu thì phải mở 1 hộp bánh cấp 3, được 3 hộp bánh cấp 2. Sau đó, mở 1 hộp bánh cấp 2, được 3 hộp bánh cấp 1. Tiếp theo, mở 1 hộp bánh cấp 1, được 3 bánh trung thu. Vậy phải mở hộp 3 lần.
Để lấy được 8 bánh trung thu thì mở 1 hộp bánh cấp 3, được 3 hộp cấp 2. Sau đó, mở 1 hộp cấp 2, được 3 hộp cấp 1. Tiếp theo, mở 3 hộp cấp 1, được 9 bánh trung thu. Vậy phải mở hộp 5 lần.

Ràng buộc:

Có 60% số lượng test ứng với 60% số điểm có N, M ≤ 1000;
Có 40% số lượng test còn lại với 40% số điểm không có ràng buộc thêm.

Bài 2. Bảng quảng cáo (100 điểm)

Trên quảng trường trung tâm thành phố, người ta đặt một bảng quảng cáo điện tử hình vuông kích thước 10⁹ × 10⁹ được chia làm lưới ô vuông đơn vị. Các hàng của bảng đánh số từ 1 tới 10⁹ từ trên xuống dưới và các cột của bảng đánh số từ 1 tới 10⁹ từ trái qua phải. Ô nằm trên giao của hàng i và cột j gọi là ô (i, j).

Có n hàng đăng ký quảng cáo đánh số từ 1 tới n, hãng thứ i đăng ký quảng cáo trong một cửa sổ hình chữ nhật có cạnh song song với cạnh bảng, hình chữ nhật này có ô ở góc trên bên trái là ô (a_i, b_i) và ô góc dưới bên phải là ô (c_i, d_i). Trên cửa sổ, hãng có thể chiếu lên bảng những đoạn video giới thiệu sản phẩm của mình.

Khi hiện lên bảng, cửa sổ quảng cáo của một số hãng có thể giao nhau làm ảnh hưởng tới sự chú ý của người xem, người ta muốn thống kê số cặp (i,j) với 1 ≤ i < j ≤ n mà cửa sổ quảng cáo của hai hãng i và j có chung ít nhất một ô, để từ đó thông báo cho các hãng có kế hoạch thay đổi vị trí và kích thước cửa sổ quảng cáo của mình cho phù hợp.

Yêu cầu: Hãy xác định số lượng những cặp (i,j) với 1 ≤ i < j ≤ n mà cửa sổ quảng cáo của hai hãng i và j có chung ít nhất một ô.

Dữ liệu: Vào từ thiết bị vào chuẩn theo khuôn dạng sau:

Dòng đầu chứa số nguyên dương T ≤ 1000 là số bộ dữ liệu;
T nhóm dòng tiếp theo, mỗi nhóm mô tả một test: dòng đầu của nhóm chứa số nguyên dương n ≤ 2×10⁵; n dòng tiếp theo, dòng thứ i chứa bốn số nguyên dương a_i, b_i, c_i, d_i cách nhau bởi dấu cách (1 ≤ a_i ≤ c_i ≤ 10⁹; 1 ≤ b_i ≤ d_i ≤ 10⁹). Tổng các giá trị n trong tất cả các test không vượt quá 2×10⁵.

Kết quả: Ghi ra thiết bị ra chuẩn gồm T dòng, ứng với mỗi bộ dữ liệu, ghi ra một số nguyên duy nhất trên một dòng là số lượng cặp (i,j) mà cửa sổ quảng cáo giao nhau.

Dữ liệu vào	Kết quả ra
2 2 1 1 2 2 2 2 3 3 5 1 3 2 5 2 2 6 3 2 6 7 9 3 5 6 10 6 3 7 7	1 5

Ràng buộc:

Có 20% số lượng test ứng với 20% số điểm có n = 2;
Có 15% số lượng test khác ứng với 15% số điểm có n ≤ 10³ và T ≤ 50;
Có 30% số lượng test khác ứng với 30% số điểm có 1 ≤ a_i, c_i ≤ 100; 1 ≤ b_i, d_i ≤ 100 trong tất cả các bộ dữ liệu;
Có 35% số lượng test còn lại không có ràng buộc thêm.

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