VOI 18 Bài 3 - Trò chơi khối hộp

Điểm: 1,50 (OI)

Giới hạn thời gian: 3.0s

Giới hạn bộ nhớ: 256M

Input: stdin

Output: stdout

Dạng bài

Ngôn ngữ cho phép

C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Trong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài

Đọc đề gốc tại đây.

Trò chơi khối hộp là một trò chơi với một khối hộp chữ nhật kích thước ~a \times b \times c~ đơn vị trên lưới hình chữ nhật ~H~ được chia thành ~m \times n~ ô vuông đơn vị. Các hàng của lưới được đánh số từ ~1~ tới ~m~ từ trên xuống dưới và các cột của lưới được đánh số từ ~1~ tới ~n~ từ trái qua phải. Ô nằm trên giao của hàng ~i~ và cột ~j~ được gọi là ô ~(i, j)~. Ban đầu, khối hộp được đặt ở góc trái trên của lưới ~H~, cụ thể mặt đáy khối hộp chiếm đúng ~a \times b~ ô của lưới, là các ô nằm trong hình chữ nhật con của lưới ~H~ với ô ở góc trái trên là ~(1, 1)~ và ô ở góc phải dưới là ~(a, b)~. Mỗi bước, người chơi có thể thực hiện một trong các loại thao tác sau:

Đẩy khối hộp tịnh tiến lên trên, xuống dưới, sang trái hoặc sang phải một ô;
Lật khối hộp lên trên, xuống dưới, sang trái hoặc sang phải một ô.

Ví dụ, các hình vẽ trong Hình ~2~ dưới đây mô tả vị trí của khối hộp kích thước ~1 \times 2 \times 1~ sau khi thực hiện từng loại thao tác.

Khi bắt đầu chơi, tất cả các ô mà khối hộp đè lên được bật sáng màu xanh và có ~k~ ô khác trên lưới được bật sáng màu đỏ, các ô còn lại ở trạng thái tắt. Một thao tác được gọi là hợp lệ, nếu sau khi thực hiện thao tác này, khối hộp vẫn nằm gọn trên lưới ~H~ và không đè lên ô sáng màu đỏ nào. Sau khi một thao tác được thực hiện, những ô bị khối hộp đè lên đang ở trạng thái tắt sẽ được bật sáng màu xanh, những ô đang sáng xanh vẫn giữ nguyên trạng thái bật sáng màu xanh. Nhiệm vụ của người chơi là tìm cách thực hiện dãy các thao tác hợp lệ để bật được nhiều ô sáng màu xanh nhất.

VOI 18 Bài 3 - Trò chơi khối hộp

Input

Output

Giới hạn

Sample Input

Sample Output

Note

Bình luận