trang chủ / đề bài / icpc21_mt_p

Jerry và thạch

Đề bài

Mô tả

Sinh nhật lần thứ 24 của Jerry sắp đến! Cũng như mọi chú chuột khác, tuổi 24 là một cột mốc rất quan trọng trong đời Jerry. Nhân dịp này, Jerry mời rất nhiều bạn bè đến nhà dự một bữa tiệc thật đặc biệt. Đợi Tom ngủ say, Jerry lặng lẽ lẻn vào tủ lạnh và tìm thấy một miếng thạch sương sáo rất to! Jerry lặng lẽ mang miếng thạch đi và... đến giờ vui vẻ rồi!

Miếng thạch Jerry lấy được là một hình hộp chữ nhật có ba kích thước lần lượt là x, y và z. Jerry muốn chia nó thành nhiều miếng nhỏ hơn bằng một số nhát cắt. Để các miếng thạch trông thật ngon mắt, mỗi nhát cắt của Jerry phải chia một miếng nào đó thành đúng hai miếng nhỏ hơn, cả hai đều là hình hộp chữ nhật có các kích thước nguyên. Ngoài ra, nhát cắt phải song song với ít nhất một mặt của miếng đang bị cắt.

Sau khi cắt xong, Jerry đặt các miếng thạch lên đĩa. Khi đặt một miếng, Jerry luôn xoay nó sao cho mặt lớn nhất nằm trên đĩa. Cụ thể, nếu các kích thước của một miếng là a, b và c với a≥b≥c thì diện tích mặt đáy của nó luôn là a×b và chiều cao luôn bằng c.

Jerry chỉ coi một miếng thạch là dễ thương khi chiều cao của nó ít nhất là u. Jerry chỉ đặt các miếng dễ thương lên đĩa và vứt bỏ mọi miếng không dễ thương. Để có một đĩa thạch thật đẹp, Jerry muốn tổng diện tích mặt đáy của các miếng thạch trên đĩa lớn nhất có thể.

Trước khi cắt miếng thạch ngon lành của mình, Jerry muốn biết giá trị lớn nhất của tổng diện tích mặt đáy của tất cả các miếng thạch dễ thương trên đĩa. Jerry rất giỏi trốn, chạy và trộm đồ, nhưng lại không giỏi lập trình. Hãy giúp Jerry!

Dữ liệu vào

  • Dòng đầu tiên chứa một số nguyên τ (1≤τ≤105) là số bộ dữ liệu.
  • Mỗi dòng trong τ dòng tiếp theo mô tả một bộ dữ liệu gồm 4 số nguyên dương x, y, z và u (1≤x,y,z,u≤100), trong đó x, y, z là các kích thước của miếng thạch Jerry lấy được và u là chiều cao nhỏ nhất của một miếng thạch dễ thương.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra trên một dòng một số nguyên là giá trị lớn nhất có thể của tổng diện tích mặt đáy của các miếng thạch trên đĩa.

Ràng buộc

  • 1≤τ≤105.
  • 1≤x,y,z,u≤100.

Ví dụ

Input Output Giải thích
2
5 4 3 2
4 3 2 1
30
24
Bộ thứ nhất: cắt miếng (5,4,3) thành hai miếng (5,2,3) và đặt cả hai lên đĩa; mỗi miếng có diện tích đáy 5×3=15 và chiều cao 2, tổng là 30. Bộ thứ hai: mọi miếng đều có chiều cao ít nhất 1 nên luôn dễ thương; cắt miếng (4,3,2) thành 4×3×2=24 khối lập phương cạnh 1, mỗi khối có diện tích đáy 1.
3
5 5 3 2
3 3 3 4
6 5 4 1
33
0
120
Bộ thứ nhất: cắt thành (2,5,3) (diện tích đáy 15) và (3,5,3), rồi cắt miếng sau thành (3,2,3) và (3,3,3) (mỗi miếng 9): tổng 33, nhiều hơn mọi cách chỉ cắt thành các lát song song. Bộ thứ hai: không miếng nào cao được tới 4. Bộ thứ ba: với u=1, cắt thành 120 khối lập phương cạnh 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