Đề bài
Tìm các số nguyên dương a < b < c sao cho a² + b² = c² và a + b + c = perimeter. Trả về tích lớn nhất a × b × c trong số các tam giác thỏa mãn, hoặc −1 nếu không có tam giác nào. Bài toán này tổng quát hóa bài toán chu vi cố định và xử lý rõ ràng trường hợp có nhiều đáp án.
Cài đặt hàm pythagorean_product(perimeter).
Đầu vào
perimeter: Tổng ba cạnh yêu cầu.
Đầu ra
Trả về tích lớn nhất, hoặc −1 nếu không có tam giác nào thỏa mãn.
Ràng buộc
3 ≤ perimeter ≤ 100.000. Tích nằm trong phạm vi số nguyên có dấu 64-bit.
Ví dụ
Đầu vào:
perimeter = 30
Kết quả mong đợi:
expected = 780Đầu vào:
long long perimeter = 30;
Kết quả mong đợi:
long long expected = 780;Đầu vào:
long perimeter = 30;
Kết quả mong đợi:
long expected = 780;Giải thích
Tam giác là (5, 12, 13): 25 + 144 = 169 và 5 + 12 + 13 = 30. Tích của nó là 780.
Đầu vào:
perimeter = 11
Kết quả mong đợi:
expected = -1Đầu vào:
long long perimeter = 11;
Kết quả mong đợi:
long long expected = -1;Đầu vào:
long perimeter = 11;
Kết quả mong đợi:
long expected = -1;Giải thích
Không có bộ ba cạnh tam giác vuông nguyên dương tăng dần nào có tổng bằng 11.
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Chỉ một số chu vi nhất định mới tạo được tam giác vuông, nên hãy thu hẹp tìm kiếm trước bằng ràng buộc tổng cạnh.
Gợi ý 2
Với mỗi cạnh nhỏ nhất có thể, suy ra hai cạnh còn lại từ chu vi và kiểm tra điều kiện tam giác vuông.
Gợi ý 3
Có thể có nhiều hơn một tam giác thỏa; hãy giữ tích lớn nhất và trả về no-solution khi không có trường hợp hợp lệ.
Độ phức tạp mong đợi
thời gian O(perimeter^2), bộ nhớ phụ O(1)
Tham khảo
Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.