Hướng dẫn cho HackDream Blue 02-B: Ghép hình chữ nhật
Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Điều kiện để tồn tại 4 nhánh cây có thể ghép được thành một hình chữ nhật là tồn tại 2 cặp số bằng nhau.
Ví dụ: ~[1, 1, 2, 2]~, ~[1, 1, 1, 1]~.
Để kiểm tra yêu cầu đề bài, ta cần thử từng bộ 2 cặp số bằng nhau có thể tồn tại trong 5 số ~a~, ~b~, ~c~, ~d~, ~e~.
Dựa theo thứ tự từ điển, có tất cả ~15~ trường hợp ~([a==b, c==d], [a==b, d==e], ...)~. Khi tìm ra trường hợp đúng, ta gán kết quả bằng diện tích của hình chữ nhật đó (Vì chỉ có 5 số nên không tồn tại 2 hình chữ nhật có dạng khác nhau trong đó, nên có thể gán trực tiếp kết quả với mỗi lần tìm ra 1 bộ số đúng thay vì lấy max).
Độ phức tạp: ~O(1)~.
Bình luận