trang chủ / đề bài / icpc24_nat_a

Ghép tam giác

Đề bài

Mô tả

Bash có n đoạn thẳng. Đoạn thẳng thứ i có độ dài 2ai. 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 t (1≤t≤105): số bộ test. Tiếp theo là t bộ test, mỗi bộ gồm hai dòng:

  • Dòng thứ nhất chứa số nguyên n (3≤n≤3·105).
  • Dòng thứ hai chứa n số nguyên a1,a2,…,an (0≤ai≤109).

Tổng n trên tất cả các bộ test không vượt quá 3·105.

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

  • 1≤t≤105
  • 3≤n≤3·105, tổng n không vượt quá 3·105
  • 0≤ai≤109

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 2, 4 và 8 không ghép được tam giác. Bộ test thứ hai: bốn đoạn đều dài 2, 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 8 (1 cách), hoặc hai đoạn dài 8 cùng đoạn dài 2 hoặc 1 (3·2=6 cách). Bộ test thứ hai: 32+32=64 không lớn hơn 64 nên không có tam giác.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0