Ghép tam giác
Đề bài
Mô tả
Bash có đoạn thẳng. Đoạn thẳng thứ có độ dài . Bash muốn chọn ba đoạn thẳng khác nhau để ghép thành một tam giác.
Bash tự hỏi: có bao nhiêu cách chọn ba đoạn thẳng ghép được thành một tam giác? Lưu ý rằng ba đoạn thẳng ghép được thành một tam giác khi và chỉ khi tổng độ dài hai đoạn bất kỳ lớn hơn độ dài đoạn còn lại.
Dữ liệu vào
Dòng đầu tiên chứa số nguyên (): số bộ test. Tiếp theo là bộ test, mỗi bộ gồm hai dòng:
- Dòng thứ nhất chứa số nguyên ().
- Dòng thứ hai chứa số nguyên ().
Tổng trên tất cả các bộ test không vượt quá .
Dữ liệu ra
Với mỗi bộ test, in ra một dòng chứa số cách chọn ba đoạn thẳng ghép được thành một tam giác.
Ràng buộc
- , tổng không vượt quá
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 2 3 1 2 3 4 1 1 1 1 |
0 4 |
Bộ test thứ nhất: ba đoạn dài , và không ghép được tam giác. Bộ test thứ hai: bốn đoạn đều dài , chọn ba đoạn bất kỳ đều ghép được tam giác. |
| 3 5 3 3 1 3 0 3 5 5 6 6 0 1 1 2 2 2 |
7 0 11 |
Bộ test thứ nhất: chọn ba đoạn dài ( cách), hoặc hai đoạn dài cùng đoạn dài hoặc ( cách). Bộ test thứ hai: không lớn hơn nên không có tam giác. |
Bình luận