trang chủ / đề bài / icpc25_mb_c

Thuốc tẩy

Đề bài

Mô tả

Bé Khoai Tây Mìn đang làm việc trong một phòng thí nghiệm sinh học và gặp rắc rối lớn. Đĩa thí nghiệm chia ngăn của cậu là một khối hộp kích thước a×b×c. Để tiện cho thí nghiệm, nó được chia thành a×b×c khối lập phương đơn vị 1×1×1, và (i,j,k) được dùng để chỉ một khối lập phương đơn vị.

Chiếc đĩa đã lâu không được sử dụng. Giờ Khoai Tây Mìn được yêu cầu làm sạch một số vùng của khối (mỗi vùng có thể được làm sạch nhiều lần). Cậu sẽ dùng một loại thuốc tẩy đặc biệt để làm sạch. Loại thuốc tẩy này rất kỳ lạ: mỗi lần làm sạch một vùng hình hộp chữ nhật kích thước x×y×z (gồm x×y×z khối đơn vị), lượng thuốc tẩy cần dùng là min(x,y,z) đơn vị. Thuốc tẩy không hề rẻ, điều này khiến Khoai Tây Mìn thấy không thoải mái. Hãy giúp cậu tìm lượng thuốc tẩy ít nhất cần dùng để làm sạch mọi khối đơn vị cần làm sạch.

Dữ liệu vào

Dòng đầu tiên chứa số bộ dữ liệu T (T≤3).

Với mỗi bộ dữ liệu: dòng đầu tiên chứa 3 số nguyên dương X,Y,Z là kích thước của đĩa thí nghiệm (X·Y·Z≤5000).

Tiếp theo là X ma trận 0/1, mỗi ma trận gồm Y dòng, mỗi dòng Z số cách nhau bởi dấu cách, mô tả trạng thái của từng khối đơn vị (0 nghĩa là khối đó không cần làm sạch, 1 nghĩa là khối đó cần được làm sạch): số ở dòng thứ j, cột thứ k của ma trận thứ i mô tả trạng thái của khối (i,j,k).

Dữ liệu ra

Với mỗi bộ dữ liệu, in trên một dòng lượng thuốc tẩy ít nhất cần dùng.

Ràng buộc

  • 1≤T≤3.
  • X,Y,Z≥1, X·Y·Z≤5000.

Ví dụ

Input Output Giải thích
1
4 4 4
1 0 1 1
0 0 1 1
0 0 0 0
0 0 0 0
0 0 1 1
1 0 1 1
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
1 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
1 0 0 0
3 Ví dụ của đề gốc. Làm sạch vùng (1,1,3)−(2,2,4) tốn 2 đơn vị và vùng (1,1,1)−(4,4,1) tốn 1 đơn vị thuốc tẩy.
3
2 3 3
0 1 0
1 1 1
0 1 0
0 0 0
0 0 0
0 0 0
1 1 1
0
3 2 2
0 1
0 0
0 0
1 0
0 1
0 0
1
0
2
Ví dụ bổ sung (không có trong đề gốc). Bộ thứ nhất: mọi ô cần làm sạch đều thuộc ma trận thứ nhất, làm sạch vùng (1,1,1)−(1,3,3) tốn 1 đơn vị. Bộ thứ hai: không có ô nào cần làm sạch. Bộ thứ ba: ba ô (1,1,2), (2,2,1), (3,1,2) cần làm sạch; vùng (1,1,2)−(3,1,2) và vùng (2,2,1)−(2,2,1) tốn tổng cộng 2 đơn vị.

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