MCAKE - Luộc bánh Chưng
Xem dạng PDF
Như thường lệ, cứ vào dịp tết Nguyên Đán, nhà trường lại tổ chức cho các lớp gói bánh Chưng đón tết. Sau công đoạn gói là tới công đoạn luộc. Do có nhiều lớp tham gia gói nên nhà trường phải có kế hoạch chia khu vực cho các lớp luộc bánh. Để đảm bảo mỹ quan và có không khí tết, nhà trường chuẩn bị một dải đất có chiều dài ~L~ để chia cho các lớp làm địa điểm luộc. Dải đất được chia ra thành ~L~ ô đánh số từ ~1~ đến ~L~. Có ~n~ lớp tham gia gói và luộc bánh. Nhà trường dự kiến chia cho lớp thứ ~i~ các ô từ ~a_i~ đến ~b_i~ ~(1 ≤ i ≤ n)~. Các lớp sẽ nhận địa điểm luộc bánh theo thứ tự từ ~1~ đến ~n~. Tuy nhiên các đoạn được dự kiến chia cho các lớp có thể có những ô trùng nhau nên nếu đến lượt lớp nào nhận mà có ô đã bị lớp trước đó nhận rồi thì sẽ không được nhận ô đó nữa.
Yêu cầu: Hãy tính số ô nhiều nhất mà một lớp có thể nhận được theo dự kiến và số ô nhiều nhất mà một lớp nhận được trên thực tế.
Input
- Dòng đầu chứa hai số nguyên dương ~n~ và ~L~;
- ~n~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên dương ~a_i, b_i~.
Hai số liên tiếp trên một dòng được ghi cách nhau một dấu cách.
Giới hạn:
- Trong tất cả các test: ~1 ≤ n, L ≤ 1000; 1 ≤ a_i ≤ b_i ≤ L~.
Output
Ghi trên một dòng hai số nguyên theo thứ tự là số ô nhiều nhất mà một lớp nhận được theo dự kiến và số ô nhiều nhất mà một lớp nhận được trên thực tế. Hai số liên tiếp được ghi cách nhau một dấu cách.
Sample
Input #1
3 10
2 4
7 8
6 9
Output #1
4 3
Hint
(Lớp số ~1~ nhận được ~3~ ô màu xanh, lớp số ~2~ nhận được ~2~ ô màu vàng, lớp số ~3~ nhận được ~2~ ô màu đỏ do hai ô màu vàng đã bị lớp số ~2~ nhận trước rồi).
- Theo dự kiến thì lớp số ~3~ nhận được nhiều ô nhất là ~4~ ô.
- Thực tế thì lớp số ~1~ nhận được nhiều nhất là ~3~ ô (hình trên).
Problem source: Chuyên Sơn La Online Judge
Bình luận
Mình xin đóng góp thêm test:
INPUT:
3 100
20 30
60 70
5 100
OUTPUT:
96 74
Các bạn có thể sử dụng thêm test này để check bài mình nhé.
Dễ thấy số ô nhiều nhất mà một lớp nhận được theo dự kiến sẽ là b - a + 1. Cái khó là phải đi tìm số ô mà một lớp nhận được thực tế. Ta sẽ thực hiện công việc đếm + đánh dấu để tìm, cụ thể.
Mình sẽ lấy sample input 1 để minh hoạ: n = 3, L = 10: Khi đó ta có 1 mảng (vector) là: 0 0 0 0 0 0 0 0 0 0 (đại loại là đánh dấu vị trí chưa bị chiếm).
Thứ nhất ta có cặp (a, b) = (2, 4): Khi đó ta bắt đầu duyệt từ vị trí 2 -> 4 xem có bao nhiêu ô trống, nếu trống thì đánh dấu ngay = 1.
Khi đó mảng của ta sẽ là: 0 1 1 1 0 0 0 0 0 0 (ta chiếm ngay các ô từ 2 -> 4 và ta có số ô nhận được thực tế là 3)
Tiếp cặp (a, b) = (7, 8), tương tự thôi và mảng của ta sẽ là: 0 1 1 1 0 0 1 1 0 0 (số ô nhận được thực tế là 2)
Cặp cuối cùng (a, b) = (6, 9), lúc này ta thấy ngay 6 -> 9 bị cặp (7, 8) chặn ở giữa, vậy ta sẽ duyệt từ 6 -> 9. Nếu ô nào trống (= 0) thì số ô nhận được thực tế += 1 và đánh dấu = 1 ngay. mảng của ta sẽ là 0 1 1 1 0 1 1 1 1 0.
Áp dụng cách đó ta đếm được số ô nhận được thực tế chỉ là 2 (ô 6 và ô 9).
Tương tự với các trường hợp khác, các bạn cần chú ý câu sau trong đề: "Tuy nhiên các đoạn được dự kiến chia cho các lớp có thể có những ô trùng nhau nên nếu đến lượt lớp nào nhận mà có ô đã bị lớp trước đó nhận rồi thì sẽ không được nhận ô đó nữa".
Nếu các bạn hiểu ý tưởng và AC thành công, mình xin 1 up vote nhé. Việc code các bạn chịu khó, nếu hiểu được ý tưởng thì cũng chỉ sử dụng for và if else chứ không hề sử dụng cấu trúc hay thuật toán gì phức tạp.
Chúc các bạn ăn Bánh chưng ngon miệng.