Giấy Domino (DHHV 2021)
Xem PDF
Điểm:
550 (p)
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Một mảnh giấy kích thước \(n× n\) ô (với \(n\) là số chẵn), được chia theo dạng domino. Cụ thể, trên mảnh giấy chia ra làm \((n× n)/2\) hình domino. Các hình được đánh số hiệu từ 1 đến \((n× n)/2\) và có kích thước \(1× 2\) ô hoặc \(2× 1\) ô, mỗi ô ghi số hiệu của thanh đó.
Cần cắt một hình chữ lớn nhất thỏa mãn các điều kiện sau:
- Các cạnh của hình chữ nhật song song với các cạnh của mảnh giấy;
- Hình chữ nhật nằm hẳn bên trong mảnh giấy;
- Hình chữ nhật chứa nguyên vẹn các hình domino.
Ví dụ, mảnh giấy kích thước 6×6.
Yêu cầu: Cho thông tin mảnh giấy, tìm diện tích hình chữ nhật lớn nhất thỏa mãn yêu cầu.
Input
- Dòng đầu chứa số nguyên dương \(n\);
- Tiếp theo là \(n\) dòng, mỗi dòng chứa \(n\) số mô tả mảnh giấy. Các số có giá trị từ 1 đến \((n× n)/2\) và mỗi số xuất hiện đúng hai lần.
Output
- Ghi ra một số nguyên duy nhất là diện tích hình chữ nhật lớn nhất tìm được.
Constraints
- \(n\leq 1000\)
Scoring
- Subtask \(1\) (\(45\%\) số điểm): \(n\leq 100\)
- Subtask \(2\) (\(20\%\) số điểm): \(n\leq 500\)
- Subtask \(3\) (\(35\%\) số điểm): Không có ràng buộc gì thêm
Example
Test 1
Input
6
1 1 4 4 13 14
2 3 3 5 13 14
2 6 7 5 12 12
9 6 7 10 10 15
9 8 8 11 11 15
16 16 17 17 18 18 Output
8Note
- Hình chữ nhật chứa các domino có số hiệu \(3, 6, 7\) và \(8\).
Bình luận
sory.
khó kinh khủng
Sao bài này độ khó 300 nhỉ = )))
Mình thấy nó phải hơn chứ
how to ac 🙁