trang chủ / đề bài / icpc25_mb_f

Cắt bánh

Đề bài

Mô tả

Sau rất nhiều nỗ lực, Thanh đã có một chiếc bánh hình hộp chữ nhật. Thanh dự định cắt chiếc bánh thành hai phần. Vì lý do thẩm mỹ, Thanh muốn mặt cắt càng trơn tru và hài hòa càng tốt.

Để đơn giản, ta xem chiếc bánh như một lưới khối lập phương có chiều dài P, chiều rộng Q và chiều cao R. Điểm (x,y,z) ở hàng x, cột y của tầng z có một giá trị độ bất hòa không âm v(x,y,z). Một nhát cắt hợp lệ thỏa mãn hai điều kiện sau:

  • Có một và chỉ một giao điểm với mỗi trục dọc (tổng cộng P×Q trục). Tức là mặt cắt là một hàm f(x,y): với mọi (x,y) (x∈[1,P], y∈[1,Q]), ta cần chỉ định một giao điểm f(x,y) (1≤f(x,y)≤R).
  • Mặt cắt cần thỏa mãn một yêu cầu về độ trơn, nghĩa là các điểm cắt trên hai trục dọc kề nhau không được cách nhau quá xa. Tức là với mọi 1≤x,x′≤P và 1≤y,y′≤Q, nếu |x−x′|+|y−y′|=1 thì |f(x,y)−f(x′,y′)|≤D, trong đó D là một số nguyên không âm cho trước.

Có thể có nhiều hàm cắt f thỏa mãn các điều kiện trên, và Thanh muốn tìm hàm có tổng độ bất hòa ∑x,yv(x,y,f(x,y)) nhỏ nhất.

Dữ liệu vào

Dòng đầu tiên chứa 3 số nguyên dương P,Q,R lần lượt là chiều dài, chiều rộng và chiều cao của chiếc bánh (1≤P,Q,R≤40).

Dòng thứ hai chứa độ trơn D. Tiếp theo là R ma trận kích thước P×Q (ma trận thứ z gồm P dòng, mỗi dòng Q số): số ở dòng x, cột y của ma trận thứ z là v(x,y,z) (1≤x≤P, 1≤y≤Q, 1≤z≤R, 0≤v(x,y,z)≤1000).

Dữ liệu ra

In ra một số nguyên là tổng độ bất hòa nhỏ nhất có thể.

Ràng buộc

  • 1≤P,Q,R≤40.
  • D là số nguyên không âm.
  • 0≤v(x,y,z)≤1000.

Ví dụ

Input Output Giải thích
2 2 2
1
6 1
6 1
2 6
2 6
6 Một nhát cắt tối ưu là f(1,1)=f(2,1)=2, f(1,2)=f(2,2)=1.
1 3 3
0
1 9 9
9 1 9
9 9 1
19 Ví dụ bổ sung (không có trong đề gốc). Với D=0 mặt cắt phải phẳng; mỗi tầng có tổng 19.

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