trang chủ / đề bài / icpc19_nat_b

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 a×b×c, có thể chia thành các khối lập phương đơn vị kích thước 1×1×1.

Bên trong chiếc bánh có m khối lập phương đơn vị chứa hạt sô-cô-la. Khối thứ i nằm ở vị trí (xi,yi,zi).

Thí sinh phải chia chiếc bánh thành đúng m 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 0.
  • Mỗi phần chứa đúng một hạt sô-cô-la.
  • Tọa độ các đỉnh của cả m 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 4 số nguyên dương a, b, c và m (1≤a,b,c≤106, 1≤m≤103).
  • m dòng tiếp theo, dòng thứ i chứa đúng 3 số nguyên dương xi, yi và zi là tọa độ của hạt sô-cô-la thứ i (1≤xi≤a, 1≤yi≤b, 1≤zi≤c). Không có hai hạt sô-cô-la nào ở cùng một vị trí.

Tổng m của mọi bộ dữ liệu trong một file không vượt quá 5·104.

Dòng cuối cùng của dữ liệu vào chứa một số −1.

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à m dòng. Dòng thứ i+1 (1≤i≤m) chứa đúng 6 số nguyên xi, yi, zi, ui, vi và wi mô tả phần thứ i (1≤xi≤ui≤a, 1≤yi≤vi≤b, 1≤zi≤wi≤c): (xi,yi,zi) và (ui,vi,wi) 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ứ i. Phần thứ i phải chứa hạt sô-cô-la thứ i.

Nếu có nhiều cách chia, in ra cách bất kỳ.

Ràng buộc

  • 1≤a,b,c≤106, 1≤m≤103.
  • 1≤xi≤a, 1≤yi≤b, 1≤zi≤c, các hạt sô-cô-la ở các vị trí khác nhau.
  • Tổng m trong một file không vượt quá 5·104.

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ó x từ 1 đến 4, phần thứ hai gồm các khối có x=5. Một cách chia khác cũng đúng là 1 1 1 5 5 1 và 1 1 2 5 5 5. Ở 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 x=1; lớp x từ 2 đến 3 được chia tiếp theo z cho hai hạt còn lại.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0