Bảng B 2021 - Chung kết toàn quốc

HỘI THI TIN HỌC TRẺ TOÀN QUỐC
Năm 2021

ĐỀ THI CHUNG KẾT - BẢNG B – TRUNG HỌC CƠ SỞ
Thời gian làm bài: 150 phút, không kể thời gian phát đề
Ngày thi: 21/11/2021

Tổng quan:

Tên bài	File chương trình	Điểm
Bài 1	`sort.*`	100 điểm
Bài 2	`tasks.*`	100 điểm
Bài 3	`dtask.*`	100 điểm
Bài 4	`robot.*`	100 điểm

Dấu * được thay thế bởi pas/cpp/py tương ứng với ngôn ngữ lập trình Pascal/C++/Python mà thí sinh sử dụng.

Bài 1. Sắp xếp (100 điểm)

Xâu x được gọi là lớn hơn xâu y nếu xâu y là đoạn đầu của xâu x, hoặc xét kí tự đầu tiên khác nhau thì kí tự của x lớn hơn kí tự của y (so sánh từ điển).

Từ hai số nguyên dương a, b (a < b), tạo ra dãy số gồm b − a + 1 số: a, a+1, …, b. Sắp xếp lại các số theo thứ tự từ điển (coi mỗi số là một xâu) bằng thao tác: mỗi lần chọn và lấy ra một số trong dãy rồi chèn lại vào dãy ở vị trí bất kì.

Ví dụ, nếu a = 9, b = 11 ta có dãy 9, 10, 11; dãy sắp theo thứ tự từ điển là 10, 11, 9 và cần ít nhất 1 thao tác (rút số 9 ra và chèn vào cuối dãy).

Yêu cầu: Cho a, b (a < b), tính số thao tác ít nhất để sắp xếp a, a+1, …, b theo thứ tự từ điển.

Dữ liệu: Một dòng chứa hai số nguyên dương a, b (a < b ≤ 10⁹).

Kết quả: Một số nguyên là số thao tác ít nhất.

Ví dụ:

Dữ liệu vào	Kết quả ra
`9 11`	`1`

Ràng buộc:

20% số test có b − a = 1;
20% số test có b − a ≤ 10;
30% số test có b − a ≤ 1000;
30% số test còn lại có b − a ≤ 10⁵.

Bài 2. Bài tập (100 điểm)

Hồng đã soạn n bài tập, bài thứ i có độ khó là số nguyên dương cᵢ. Cần gửi m bài tập lên hệ thống: nếu m < n, phải loại bỏ n − m bài; nếu m > n, phải soạn thêm m − n bài với độ khó là số nguyên dương bất kỳ. Sau khi có m bài, sắp xếp theo độ khó tăng dần; gọi d là chênh lệch độ khó lớn nhất giữa hai bài liên tiếp. Cần d nhỏ nhất có thể.

Yêu cầu: Cho n bài tập với độ khó c₁,…,cₙ và số m, tìm giá trị d nhỏ nhất.

Dữ liệu: Dòng 1: n, m (2 ≤ m, n ≤ 10⁵; m ≠ n). Dòng 2: n số nguyên dương c₁,…,cₙ (cᵢ ≤ 10⁹).

Kết quả: Một số nguyên d.

Ví dụ:

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

Kiểm tra lại với ví dụ: (5,4,[8,5,9,10,10]) → 1; (3,4,[8,6,9]) → 1. Khớp với đề bài.

Bài 3. Bài khó (100 điểm)

Một bài toán khó trong danh sách các bài mà Hồng lựa chọn để tập huấn cho các em học sinh khóa dưới như sau:

Cho hai số nguyên dương n, t, cần tìm một bộ gồm ít số nguyên dương nhất, giả sử bộ tìm được gồm k số nguyên dương a₁, a₂, …, aₖ thì:

(a₁+t) × (a₂+t) × ... × (aₖ+t) = n × a₁ × a₂ × ... × aₖ

Yêu cầu: Cho hai số nguyên dương n, t, hãy tìm số nguyên dương k nhỏ nhất thỏa mãn.

Dữ liệu: Vào từ thiết bị vào chuẩn gồm một dòng chứa hai số nguyên n, t (n, t ≤ 1000).

Kết quả: Ghi ra thiết bị ra chuẩn gồm một dòng chứa một số nguyên k là số lượng số ít nhất để tồn tại bộ gồm k số nguyên dương thỏa mãn, nếu không tồn tại ghi số −1.

Ví dụ:

Dữ liệu vào	Kết quả ra
`4 1`	`2`

Bài 4. Thử nghiệm robot (100 điểm)

Công ty HP vừa thiết kế một loại robot thông minh mới. Để đánh giá khả năng tự vận hành của robot, người ta tạo ra một bức tường từ n cột các khối lập phương, các cột đặt cạnh nhau, bề dày bức tường là 1, độ cao cột thứ i là aᵢ (do aᵢ khối lập phương tạo lên). Có m robot tham gia thử nghiệm. Trước tiên người ta chia n cột thành m đoạn bằng m−1 điểm cắt k₁, k₂, …, k(m-1) (k₀=0 < k₁ < … < k(m-1) < kₘ=n). Robot thứ i được giao nhiệm vụ xếp lại đoạn từ cột k(i-1)+1 đến cột kᵢ sao cho các cột trong đoạn có độ cao bằng nhau. Robot chỉ có thể thực hiện một trong hai loại thao tác, mỗi thao tác mất 1 đơn vị thời gian:

Thao tác 1: Lấy khối trên cùng của một cột trong đoạn được giao để bỏ đi;
Thao tác 2: Lấy một khối mới, đặt khối đó lên trên cùng của một cột trong đoạn được giao.

Thời gian kết thúc thử nghiệm là thời gian mà robot cuối cùng hoàn thành xong nhiệm vụ.

Yêu cầu: Cho a₁, a₂, …, aₙ và m. Hãy tìm m−1 điểm cắt để chia n cột thành m đoạn sao cho thời gian thử nghiệm là nhanh nhất, biết các robot đều thực hiện các thao tác tối ưu.

Dữ liệu: Vào từ thiết bị nhập chuẩn:

Dòng đầu chứa hai số nguyên n, m;
Dòng thứ hai gồm n số nguyên không âm a₁, a₂, …, aₙ (aᵢ ≤ 10⁶).

Kết quả: Ghi ra thiết bị ra chuẩn một dòng chứa một số nguyên là thời gian ít nhất để thử nghiệm.

Ràng buộc:

Có 25% số test ứng với 25% số điểm của bài thỏa mãn: m=1; n≤10;
Có 25% số test khác ứng với 25% số điểm của bài thỏa mãn: m=2; n≤1000;
Có 25% số test khác ứng với 25% số điểm của bài thỏa mãn: m≤n; n≤100;
Có 25% số test còn lại ứng với 25% số điểm của bài thỏa mãn: m≤n; n≤1000.

Ví dụ:

Dữ liệu vào	Kết quả ra
`6 2` `1 1 2 3 4 3`	`1`

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