Bánh sinh nhật
Đề bài
Mô tả
Bob tổ chức sinh nhật cùng bạn bè và muốn cắt chiếc bánh sinh nhật để chia cho mọi người.
Chiếc bánh là một hình chữ nhật kích thước làm từ nhiều loại nguyên liệu. Gọi là lượng calo của ô ở hàng , cột ; tổng calo của một miếng bánh là tổng calo các ô của nó.
Bữa tiệc có người bạn. Vì sợ béo nên họ không muốn ăn quá nhiều: người bạn thứ chỉ chấp nhận miếng bánh có tổng calo không vượt quá .
Bob cắt bánh đúng lần để được miếng, theo quy tắc sau:
- Ở lần cắt thứ , Bob cắt miếng bánh hiện tại (là một hình chữ nhật) theo chiều ngang hoặc chiều dọc, dọc theo đường kẻ giữa các ô, thành hai miếng hình chữ nhật, mỗi miếng có kích thước ít nhất .
- Nếu cắt ngang, miếng phía trên được đưa cho người bạn thứ , miếng phía dưới được dùng cho lần cắt tiếp theo.
- Nếu cắt dọc, miếng bên trái được đưa cho người bạn thứ , miếng bên phải được dùng cho lần cắt tiếp theo.
- Sau lần cắt, miếng còn lại được đưa cho người bạn thứ , không thừa phần nào.
- Miếng bánh của người bạn thứ phải có tổng calo không vượt quá .
Ví dụ với , và chiếc bánh có hàng trên là và hàng dưới là :
- Cách : cắt ngang trước, người thứ nhất nhận hàng trên (), phần còn lại được cắt dọc thành và . Các miếng có calo , không hợp lệ vì .
- Cách : cắt dọc trước, người thứ nhất nhận cột trái (), phần còn lại là cột được cắt ngang thành và . Các miếng có calo , thỏa mãn cả ba người.
Hãy đếm số cách cắt bánh khác nhau tuân theo quy tắc và làm hài lòng tất cả mọi người. Hai cách khác nhau nếu ở một lần cắt nào đó chúng khác hướng cắt hoặc khác vị trí cắt.
Dữ liệu vào
Dòng đầu tiên chứa ba số nguyên , và (, ).
Mỗi dòng trong dòng tiếp theo chứa số nguyên ().
Dòng cuối cùng chứa số nguyên ().
Dữ liệu ra
In ra số cách cắt bánh thỏa mãn, chia lấy dư cho .
Ràng buộc
- , .
- .
- .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 2 2 3 1 5 2 8 5 10 15 |
1 | Chỉ có cách ở trên là hợp lệ. |
| 3 3 2 10 8 6 8 4 10 1 1 0 78 25 |
3 | Cắt ngang sau hàng (các miếng , ), cắt ngang sau hàng (, ) hoặc cắt dọc sau cột (, ). |
Bình luận