Page 1 of 1
11866 - Triangle
Posted: Sat Oct 09, 2010 6:37 pm
by Angeh
How To solve this Problem ...
any idea ??????
Re: 11866 - Triangle
Posted: Sun Oct 10, 2010 5:17 am
by 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.
Re: 11866 - Triangle
Posted: Sun Oct 10, 2010 8:04 am
by 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 ????????
Re: 11866 - Triangle
Posted: Sun Oct 10, 2010 10:17 am
by 4085293
OH! I SEE IT'S WRONG BUT I haven't KNOW WHY yet TOO! HELP ME TOO!
Re: 11866 - Triangle
Posted: Wed Oct 13, 2010 8:01 am
by phars_alnmr
plz could any one post some test cases & its answers
Re: 11866 - Triangle
Posted: Sat Oct 30, 2010 2:02 pm
by 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.
Re: 11866 - Triangle
Posted: Sat Oct 30, 2010 2:13 pm
by peratu
phars_alnmr wrote: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