Tất cả thử thách
Trung bình 1 đã giải Tỷ lệ chấp nhận 100.0%

Tích Cạnh Tam Giác Vuông

Tìm tích lớn nhất của các cạnh của một tam giác vuông có cạnh là số nguyên với chu vi cho trước.

Bạn sẽ học được gì

  • Tìm tam giác vuông nguyên theo chu vi
  • Giảm ba vòng lặp còn hai
  • Kiểm tra điều kiện Pythagore

Đề bài

Xem bản gốc (English)

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ụ

Ví dụ 1
Đầ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.

Ví dụ 2
Đầ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.

Lời giải đạt tốt nhất của mỗi người. Lời giải nhanh hơn, tốn ít bộ nhớ hơn và được đánh giá cao hơn sẽ đứng trên.

# Người giải Ngôn ngữ Thời gian Bộ nhớ AI đánh giá Lời giải
1 ННикита Python 957 ms - 4/5 Xem code

Học hỏi từ người khác

Giải pháp cộng đồng

Cảnh báo: Có 1 lời giải đầy đủ bên dưới Hãy thử tự giải trước. Bạn vẫn có thể xem mã của người khác và đánh giá AI. Đăng nhập và giải thử thách để tham gia thảo luận.