Hướng dẫn cho Tam giác cân


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.

Mình xin chia sẻ lời giải bài toán này như sau:

  • Đầu tiên ta có một chú ý sau, một tam giác là tam giác cân khi và chỉ khi các cạnh của nó có dạng như sau \((a,a,b)\) với điều kiện \(a+a>b\) (Ta không cần xét \(a+b>a\) (vì điều này hiển nhiên đúng)) và ở đây \(b\) có thể bằng \(a\).
  • Do đó bài toán trên quy về đếm số bộ \((a,a,b)\) thỏa mãn \(a+a>b\) (hay \(b<=2 * a-1\))
  • Mình sẽ minh họa cách làm của mình thông qua một bài toán cụ thể, và từ đó ta tổng quát lên cho bài toán gốc như sau:
  • Giả sử ta có mảng a gồm 6 phần tử sau: \(\text{4 5 4 6 4 7}\)
  • Để dễ dàng cho việc đếm, ta có thể sắp xếp (tăng dần) lại các phần tử như sau: \(\text{4 4 4 5 6 7}\)
  • Ta nhận thấy rằng, khi sắp xếp lại như vậy, kết quả của bài toán không bị ảnh hưởng (vì ta chọn 3 phần từ bất kỳ không trùng nhau từng đôi một thì nó luôn tồn tại thứ tự chỉ số thỏa mãn $i


Bình luận

Không có bình luận nào.