Editorial for Bedao Mini Contest 07 - ARCHITECT


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Author: bedao

Nhận xét:

  • Đa phần các bạn khi nhìn vào đề bài này đều sẽ lầm tưởng để giải được bài này cần ~8~ đến ~9~ mảng cộng dồn cho từng loại một nhưng làm thế thì vô cùng phức tạp. Vì vậy muốn tạo thành một kim tự tháp thì luôn luôn phải thỏa mãn điều kiện rằng , ~X -[ 2 \times (k -1)] > 0~ và ~Y -[ 2 \times (k -1)] > 0~, từ đó, ta chứng minh được ~1 \leq k < \sqrt[3]{5\times10^{5}}~
  • Khi chứng minh được ~k~ rất bé như trên bài toán thu về đơn giản chỉ cần xét điều kiện để có thể tạo thành hình kim tự tháp ~X -[ 2 * (k -1)] > 0~ và ~Y -[ 2 * (k -1)] > 0~.

Từ nhận xét, ta thấy khi thỏa mãn điều kiện của kim tự tháp thì chỉ cần chạy từng tầng của kim tự tháp để tính tổng tiền tố với tầng đáy tính từ dưới lên là ~1~. Ở tầng thứ ~i~ ~(1\leq i \leq Z)~ ta tính tổng các ô lập phương tạo thành hình hộp chữ nhật có góc trái trên là {~{ x + (i -1) ; y + (i -1 ) ; z + (i -1) }~} có chiều rộng là ~X -[ 2 * (k -1)]~ , chiều dài là ~Y -[ 2 * (k -1)]~ và chiều cao là ~1~.

Bạn có thể tham khảo cách tính bằng mảng cộng dồn hai chiều tại đây


Comments

Please read the guidelines before commenting.


There are no comments at the moment.