Tiêu đề HSG-Lop-12-Ho-Chi-Minh- 2023-2024.pdf ✅

Trang 3 có độ dài A, một đầu của thanh ngang thứ j được đặt tại điểm có tọa độ (0; bj), đầu còn lại nằm trên điểm (A; bj), 0 < bj < B. Cách bố trí các thanh dọc, ngang như trên chia hình chữ nhật ban đầu thành (N+1)(M+1) khu vực khép kín. Tại những điểm giao nhau, ta cắt thanh dọc và thanh ngang để tạo ra những đoạn nhỏ hơn. Nhiệm vụ của người chơi là cần bỏ đi các đoạn sao cho tất cả khu vực trong vùng chơi thông với nhau và tổng độ dài các đoạn bỏ đi là ít nhất. Có thể hiểu rằng khi tất cả khu vực thông nhau thì trong vùng chơi từ một khu vực ta có thể di chuyển đến một khu vực bất kỳ. Hình minh họa ví dụ bên dưới: cần bỏ các đoạn nét đứt để các khu vực thông nhau. Yêu cầu: Hãy viết một chương trình cho biết tổng độ dài ít nhất các đoạn cần bỏ đi để tất cả khu vực trong vùng chơi thông nhau. Dữ liệu: Vào từ tập tin văn bản RUTVAN.INP, dòng đầu chứa 4 số nguyên A, B, N, M. Mỗi dòng trong N dòng tiếp theo chứa một số nguyên lần lượt là vị trí của các thanh dọc a1, a2, .., aN. Mỗi dòng trong M dòng tiếp theo chứa một số nguyên lần lượt là vị trí của các thanh ngang b1, b2, .., bM. Kết quả: Ghi ra tập tin văn bản RUTVAN.OUT một số nguyên cho biết tổng độ dài ít nhất các đoạn cần bỏ đi để tất cả các khu vực trong vùng chơi thông nhau. Ràng buộc:  30% số điểm của bài: 0 ≤ N, M ≤ 3  60% số điểm của bài: 0 ≤ N, M ≤ 1 000  100% số điểm của bài: 0 ≤ N, M ≤ 25 000 Ví dụ: RUTVAN.INP RUTVAN.OUT 5 5 2 2 1 3 3 4 10 --- HẾT --- (Cán bộ coi thi không giải thích gì thêm) Họ và tên thí sinh:..................................................Số báo danh:............................ TECHACADEMY.EDU.VN