Kiểm tra cách chia
Đề bài
Mô tả
Như bạn đã biết từ bài "Chia bánh", vòng đầu tiên của Kỳ thi Hunter đã bắt đầu. Dưới đây là phần mô tả được chép lại từ đề bài "Chia bánh":
Vòng thi đầu tiên của Kỳ thi Hunter là một bài kiểm tra giải quyết vấn đề thực tế: mỗi thí sinh được phát một chiếc bánh hình hộp chữ nhật kích thước , có thể chia thành các khối lập phương đơn vị kích thước .
Bên trong chiếc bánh có khối lập phương đơn vị chứa hạt sô-cô-la. Khối thứ nằm ở vị trí .
Thí sinh phải chia chiếc bánh thành đúng phần, mỗi phần là một hình hộp chữ nhật, thỏa mãn tất cả các điều kiện sau:
- Với hai phần bất kỳ, phần không gian chung của chúng có thể tích bằng .
- Mỗi phần chứa đúng một hạt sô-cô-la.
- Tọa độ các đỉnh của cả phần đều là số nguyên.
- Để tránh lãng phí thức ăn, thí sinh không được bỏ đi bất kỳ phần nào của chiếc bánh.
Bạn có thể chia chiếc bánh thỏa mãn mọi điều kiện và vượt qua vòng đầu tiên của Kỳ thi Hunter không?
Năm nay có thí sinh tham gia vòng đầu tiên của Kỳ thi Hunter! Rõ ràng Hiệp hội Hunter, ban tổ chức kỳ thi, không thể tự tay kiểm tra bài làm của tất cả thí sinh. Là lập trình viên duy nhất của Hiệp hội Hunter, bạn được giao viết một chương trình tự động kiểm tra xem bài làm của các thí sinh có hợp lệ hay không.
Dữ liệu vào
Dữ liệu vào gồm nhiều bộ dữ liệu. Mỗi bộ dữ liệu được mô tả như sau:
- Dòng đầu tiên chứa đúng số nguyên dương , , và (, ).
- dòng tiếp theo, dòng thứ chứa đúng số nguyên dương , và là tọa độ của hạt sô-cô-la thứ (, , ). Không có hai hạt sô-cô-la nào ở cùng một vị trí.
- dòng tiếp theo mô tả bài làm của một thí sinh: dòng thứ () chứa đúng số nguyên , , , , và mô tả phần thứ (): và là tọa độ của hai khối lập phương đơn vị ở hai góc đối diện của phần thứ .
Tổng của mọi bộ dữ liệu trong một file không vượt quá .
Dòng cuối cùng của dữ liệu vào chứa một số .
Dữ liệu ra
Với mỗi bộ dữ liệu, in ra đúng một dòng chứa YES nếu bài làm của thí sinh thỏa mãn tất cả các điều kiện sau:
- Phần thứ chứa hạt sô-cô-la thứ .
- Thí sinh không bỏ đi phần nào của chiếc bánh.
- Thể tích phần giao của hai phần bất kỳ bằng .
- , , .
Ngược lại, in ra NO.
Lưu ý: không có gì đảm bảo chiếc bánh chia được thành phần thỏa mãn mọi điều kiện. Khi không chia được, đáp án của bộ dữ liệu đó là NO.
Ràng buộc
- , .
- , , với tọa độ các hạt sô-cô-la, các hạt ở các vị trí khác nhau.
- Mọi tọa độ trong bài làm của thí sinh nằm trong đoạn .
- Tổng trong một file không vượt quá .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 5 5 5 2 1 1 1 5 5 5 1 1 1 5 5 1 1 1 2 5 5 5 5 5 5 1 3 3 3 1 1 1 5 5 6 -1 |
YES NO |
Ở bộ thứ nhất, hai phần là lớp và các lớp từ đến , mỗi phần chứa đúng hạt của mình. Ở bộ thứ hai, phần duy nhất có . |
| 2 1 1 2 1 1 1 2 1 1 2 1 1 2 1 1 1 1 1 1 1 1 3 1 1 2 1 1 1 3 1 1 1 1 1 2 1 1 2 1 1 3 1 1 -1 |
NO NO |
Ví dụ bổ sung (không có trong đề gốc). Ở bộ thứ nhất, phần thứ nhất không chứa hạt thứ nhất (hai phần bị đổi chỗ). Ở bộ thứ hai, hai phần cùng chứa khối . |
Bình luận