Bảng B 2024 - Tỉnh Quảng Ninh

HỘI THI TIN HỌC TRẺ QUẢNG NINHLẦN THỨ XXV - NĂM 2024ĐỀ CHÍNH THỨC

ĐỀ THI BẢNG B - KHỐI THCS Thời gian làm bài: 120 phút
(Đề thi có 03 trang)

Tổng quan đề thi

Bài	Tên bài	Tệp dữ liệu	Tệp kết quả	Bộ nhớ (MB)	Thời gian (giây)	Điểm
1	Số yêu thích	Thiết bị vào chuẩn	Thiết bị ra chuẩn	512	1	100
2	Bình đẳng	Thiết bị vào chuẩn	Thiết bị ra chuẩn	512	1	100
3	Bội số	Thiết bị vào chuẩn	Thiết bị ra chuẩn	512	1	100
4	Xem thể thao	Thiết bị vào chuẩn	Thiết bị ra chuẩn	512	1	100

Hãy lập trình giải các bài toán sau:

Bài 1. Số yêu thích (100 điểm)

An rất thích hai số nguyên n và k. Bây giờ anh ta muốn tìm số nguyên x nhỏ nhất sao cho x > n và x chia hết cho k.

Dữ liệu: Gồm một dòng chứa hai số nguyên n và k (1 ≤ n, k ≤ 10⁹).

Kết quả: In ra số nguyên x nhỏ nhất sao cho x > n và x chia hết cho k.

Ví dụ:

input	output
`5 3`	`6`
`26 13`	`39`

Subtasks:

Subtask 1 (50%): 1 ≤ n, k ≤ 10⁷;
Subtask 2 (50%): Không có thêm ràng buộc nào.

Bài 2. Bình đẳng (100 điểm)

Cho một xâu s độ dài n, chỉ bao gồm k chữ cái đầu tiên của bảng chữ cái tiếng Anh. Tất cả các chữ cái trong xâu s là viết hoa.

Một dãy con của xâu s là một xâu nhận được từ việc xóa một số (có thể bằng 0) chữ cái của s và không thay đổi thứ tự của các chữ cái còn lại. Ví dụ: “ADE”, “BD” và “ABCDE” là các dãy con của “ABCDE”, nhưng “DEA” thì không là dãy con.

Một dãy con của xâu s được gọi là dãy con tốt nếu số lần xuất hiện của mỗi chữ cái trong k chữ cái đầu tiên của bảng chữ cái tiếng Anh là bằng nhau.

Hãy tìm độ dài của dãy con tốt dài nhất của xâu s.

Dữ liệu: Dòng đầu tiên chứa hai số nguyên n và k (1 ≤ n ≤ 10⁵; 1 ≤ k ≤ 26). Dòng thứ hai chứa xâu s độ dài n. Xâu s chỉ bao gồm k chữ cái đầu tiên viết hoa của bảng chữ cái tiếng Anh.

Kết quả: In ra một số nguyên là độ dài của dãy con tốt dài nhất của xâu s.

Ví dụ:

input	output
`9 3` `ACAABCCAB`	`6`
`9 4` `ABCABCABC`	`0`

Trong ví dụ đầu tiên, “ACBCAB” (“ACAABCCAB”) là một dãy con có số lần xuất hiện các chữ cái ‘A’, ‘B’ và ‘C’ bằng nhau, nên nó là dãy con tốt. Hơn nữa nó lại là dãy con tốt dài nhất, vì không có dãy con tốt nào khác dài hơn nó.

Trong ví dụ thứ hai, không có dãy con nào chứa chữ cái ‘D’, do đó câu trả lời là 0.

Subtasks:

Subtask 1 (25%): 1 ≤ n ≤ 10;
Subtask 2 (25%): 1 ≤ n ≤ 10²;
Subtask 3 (25%): 1 ≤ n ≤ 10³;
Subtask 4 (25%): Không có thêm ràng buộc nào.

Bài 3. Bội số (100 điểm)

Xét k số nguyên tố đầu tiên p₁, p₂, …, pₖ. Chúng ta tạo dãy số a₁, a₂, …, aₙ, … theo thứ tự tăng dần gồm tất cả các số nguyên lớn hơn 1 và chỉ là bội số của một hoặc nhiều số trong k số nguyên tố đầu tiên p₁, p₂, …, pₖ, chứ không được là bội số của các số nguyên tố khác.

Hãy tìm phần tử thứ n của dãy số a, tức là aₙ, với n cho trước.

Dữ liệu: Gồm một dòng chứa hai số nguyên k và n (1 ≤ k ≤ 10³; 1 ≤ n ≤ 2 × 10⁵).

Kết quả: In ra một số nguyên là giá trị của aₙ. Dữ liệu đảm bảo rằng aₙ ≤ 10¹⁸.

Ví dụ:

input	output
`2 7`	`12`

Hai số nguyên tố đầu tiên là 2 và 3. Dãy số gồm các số chỉ là bội của 2, hoặc chỉ là bội của 3, hoặc chỉ là bội của 2 và 3 theo thứ tự tăng dần là: 2, 3, 4, 6, 8, 9, 12, 16, … Số ở vị trí thứ 7 là 12.

Subtasks:

Subtasks 1 (20%): k < 10 và n < 3000;
Subtasks 2 (20%): aₙ ≤ 10⁴;
Subtasks 3 (20%): aₙ ≤ 10⁵;
Subtasks 4 (20%): k × n < 10⁷;
Subtasks 5 (20%): Không có thêm ràng buộc nào.

Bài 4. Xem thể thao (100 điểm)

Tối nay n trận đấu thể thao được đánh số từ 1 đến n, sẽ được chiếu trên các kênh khác nhau. Trận đấu i bắt đầu vào thời điểm lᵢ và kết thúc vào thời điểm rᵢ.

An muốn xem các trận đấu từ đầu đến cuối càng nhiều càng tốt. Hơn nữa, nếu trận đấu nào đó kết thúc vào thời điểm rᵢ, thì sau đó anh ấy có thể xem bất kỳ trận đấu j nào bắt đầu không sớm hơn thời gian rᵢ, tức là lⱼ ≥ rᵢ (An có thể ngay lập tức chuyển kênh khi kết thúc trận đấu và bắt đầu xem một trận đấu mới). An cũng muốn nghỉ giải lao ít nhất là t giữa hai trận đấu để ăn tối, nghĩa là phải có hai trận i và j mà An sẽ xem liên tiếp thỏa mãn điều kiện lⱼ − rᵢ ≥ t. Thời gian nghỉ không thể diễn ra trước hoặc sau tất cả các trận đấu đã xem.

Bạn hãy giúp An tìm một tập chứa số lượng trận đấu tối đa mà anh ấy có thể xem đầy đủ, đồng thời nghỉ giải lao ít nhất là t giữa một số trận đấu hoặc xác định rằng tập đó không tồn tại.

Dữ liệu: Dòng đầu tiên chứa số nguyên n (2 ≤ n ≤ 10⁵) là số trận đấu. Dòng thứ hai chứa số nguyên t (1 ≤ t ≤ 10⁹) là độ dài tối thiểu của thời gian nghỉ mà An sẽ thực hiện. Dòng thứ i trong n dòng tiếp theo chứa hai số nguyên lᵢ và rᵢ (1 ≤ lᵢ < rᵢ ≤ 10⁹) tương ứng là thời điểm bắt đầu và kết thúc của trận đấu thứ i.

Kết quả: Dòng đầu tiên in ra số nguyên m là số trận đấu tối đa mà An có thể xem. Dòng thứ hai in ra m số nguyên là chỉ số các trận đấu theo thứ tự mà An sẽ xem. Nếu An không thể tạo ra lịch xem cho ít nhất hai trận đấu để có ít nhất t thời gian nghỉ giữa hai trận đấu, thì hãy in số −1.

Ví dụ:

input	output
`6` `3` `8 13` `1 5` `4 6` `4 7` `10 12` `2 4`	`3` `6 3 5`
`2` `5` `1 5` `9 13`	`-1`

Trong ví dụ đầu tiên, câu trả lời sẽ là dãy các trận đấu 6, 3, 5. Đầu tiên An sẽ xem trận đấu 6, kết thúc ở thời điểm 4, sau đó anh ấy chuyển sang trận 3, kéo dài từ thời điểm 4 đến 6. Sau đó anh ấy sẽ nghỉ giải lao từ thời điểm 6 đến 10, sau đó sẽ xem trận đấu 5 từ thời điểm 10 đến 12. Kết quả An xem được 3 trận đấu và có thời gian nghỉ giải lao là 4. Lưu ý rằng trong ví dụ này, câu trả lời đúng cũng sẽ là dãy các trận đấu 6, 4, 5 với thời gian nghỉ giữa trận đấu 4 và 5 bằng 3.

Trong ví dụ thứ hai chỉ có hai trận đấu, trận đấu 1 kết thúc vào thời điểm 5 và trận đấu 2 bắt đầu vào thời điểm 9, nghĩa là không thể tạo ra lịch xem có thời gian nghỉ ít nhất là t = 5.

Subtasks:

Subtask 1 (20%): n ≤ 15;
Subtask 2 (40%): n ≤ 10³;
Subtask 3 (30%): rᵢ ≤ 10⁵;
Subtask 4 (10%): Không có thêm ràng buộc nào.

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