NOTATRI - Not a Triangle

You have N (3 ≤ N ≤ 2,000) wooden sticks, which are labeled from 1 to N. The i-th stick has a length of Li (1 ≤ Li ≤ 1,000,000). Your friend has challenged you to a simple game: you will pick three sticks at random, and if your friend can form a triangle with them (degenerate triangles included), he wins; otherwise, you win. You are not sure if your friend is trying to trick you, so you would like to determine your chances of winning by computing the number of ways you could choose three sticks (regardless of order) such that it is impossible to form a triangle with them.


The input file consists of multiple test cases. Each test case starts with the single integer N, followed by a line with the integers L1, ..., LN. The input is terminated with N = 0, which should not be processed.


For each test case, output a single line containing the number of triples.


4 2 10
1 2 3
5 2 9 6


For the first test case, 4 + 2 < 10, so you will win with the one available triple. For the second case, 1 + 2 is equal to 3; since degenerate triangles are allowed, the answer is 0.

hide comments
ntnguyen: 2020-01-29 07:06:11

Note: Do "not" print a new line after the output ends.
Cost me 3 WAs :((.

subodh898: 2019-11-08 15:27:48

upper_bound search

jvjplus: 2019-09-22 04:01:51

Simple calculation. The sum of the two sides < the third side

sanket17: 2019-08-06 11:12:18

my n*n*log(n) got tle
sort and use two pointer method

sanjay_thiru: 2019-06-29 11:29:08

Nice question!

nishit5: 2019-06-25 16:30:52

pls be aware of the input format it cost me one WA

abhimanyu_1998: 2019-03-25 18:15:33

AC in 1 go

y17prashant: 2019-03-22 03:15:55

SImple implementation can be done no need of bin search

ankur1999: 2019-02-02 14:48:32

Use upper_bound(Time: 0.14s) instead of binary search(Time: 0.18s),
(both works fine)

Last edit: 2019-02-02 14:49:40
sajalagrawal14: 2019-01-29 15:26:11

AC in one go!!!!!! n2logn complexicity

Added by:Neal Wu
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO