trang chủ / đề bài / icpc19_nat_c

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 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?

Năm nay có 109+7 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 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í.
  • m dòng tiếp theo mô tả bài làm của một thí sinh: dòng thứ i (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,yi,vi,zi,wi≤106): (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.

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, 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ứ i chứa hạt sô-cô-la thứ i.
  • 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 0.
  • 1≤xi≤ui≤a, 1≤yi≤vi≤b, 1≤zi≤wi≤c.

Ngược lại, in ra NO.

Lưu ý: không có gì đảm bảo chiếc bánh chia được thành m 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

  • 1≤a,b,c≤106, 1≤m≤103.
  • 1≤xi≤a, 1≤yi≤b, 1≤zi≤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 [1,106].
  • 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
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 z=1 và các lớp z từ 2 đến 5, mỗi phần chứa đúng hạt của mình. Ở bộ thứ hai, phần duy nhất có w=6>c=5.
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 (2,1,1).

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