Chia bánh
Đề bài
Mô tả
Kỳ thi Hunter đã bắt đầu!
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?
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í.
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:
- Nếu không thể chia chiếc bánh thỏa mãn các điều kiện trên, in ra đúng một dòng chứa NO.
- Ngược lại, in ra một dòng chứa YES, tiếp theo là dòng. 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ứ . Phần thứ phải chứa hạt sô-cô-la thứ .
Nếu có nhiều cách chia, in ra cách bất kỳ.
Ràng buộc
- , .
- , , , các hạt sô-cô-la ở các vị trí khác nhau.
- 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 5 5 5 1 3 3 3 -1 |
YES 1 1 1 4 5 5 5 1 1 5 5 5 YES 1 1 1 5 5 5 |
Ở bộ thứ nhất, phần thứ nhất gồm các khối có từ đến , phần thứ hai gồm các khối có . Một cách chia khác cũng đúng là và . Ở bộ thứ hai, cả chiếc bánh là một phần. |
| 3 1 3 3 2 1 1 2 1 3 1 1 2 -1 |
YES 2 1 1 3 1 2 2 1 3 3 1 3 1 1 1 1 1 3 |
Ví dụ bổ sung (không có trong đề gốc). Hạt thứ ba nhận lớp ; lớp từ đến được chia tiếp theo cho hai hạt còn lại. |
Bình luận