11866 - Triangle

[Angeh]

How To solve this Problem ...
any idea ??????

[sonyckson]

Basically, its easy to count the number of triples you can form with tree numbers between X and Y considering triples as sets (i mean considering (1,2,3) the same as (2,1,3) ). Then you only have to count the number of those triples that can not form a triangle. This means the numbers of triples x, y, z, such that X <= x <= y <= z <= Y such that x + y >= z. Think how can you get a formula for this (i used pre-calculated some values).

Eric.

[Angeh]

Thanks for your replay
the number of Triples Between X,Y . is
n=Y-X...
Triples Between X,Y = n*(n+1)*(2n+1)/6
am i right ????????

[4085293]

OH! I SEE IT'S WRONG BUT I haven't KNOW WHY yet TOO! HELP ME TOO!

[phars_alnmr]

plz could any one post some test cases & its answers

[peratu]

I have solved that problem, but the judge says "TLE" because I have three loops. I think this problem should be reduced to a "simple" combinatory operation if you want to solve it within the time limit.

[peratu]

plz could any one post some test cases & its answers

Sample Input

Code: Select all

10
1 10
5 10
5 15
10 20
100 400
100 1000
200 1500
500 10000
1000 15000
1 1000000

Sample Output

Code: Select all

125
55
252
285
3898600
79243850
256184575
82185463000
274340382250
83333708333750000