11866 - Triangle

All about problems in Volume 118. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
Angeh
Experienced poster
Posts: 108
Joined: Sat Aug 08, 2009 2:53 pm

11866 - Triangle

Post by Angeh » Sat Oct 09, 2010 6:37 pm

How To solve this Problem ...
any idea ??????
>>>>>>>>> A2
Beliefs are not facts, believe what you need to believe;)

sonyckson
New poster
Posts: 49
Joined: Tue Feb 06, 2007 9:29 pm
Location: Cordoba, Argentina

Re: 11866 - Triangle

Post by sonyckson » Sun Oct 10, 2010 5:17 am

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
Experienced poster
Posts: 108
Joined: Sat Aug 08, 2009 2:53 pm

Re: 11866 - Triangle

Post by Angeh » Sun Oct 10, 2010 8:04 am

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 ????????
>>>>>>>>> A2
Beliefs are not facts, believe what you need to believe;)

4085293
New poster
Posts: 5
Joined: Sun Oct 10, 2010 9:52 am

Re: 11866 - Triangle

Post by 4085293 » Sun Oct 10, 2010 10:17 am

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

phars_alnmr
New poster
Posts: 2
Joined: Wed Aug 18, 2010 2:03 am

Re: 11866 - Triangle

Post by phars_alnmr » Wed Oct 13, 2010 8:01 am

plz could any one post some test cases & its answers

peratu
New poster
Posts: 7
Joined: Sat Jul 10, 2010 9:22 am

Re: 11866 - Triangle

Post by peratu » Sat Oct 30, 2010 2:02 pm

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
New poster
Posts: 7
Joined: Sat Jul 10, 2010 9:22 am

Re: 11866 - Triangle

Post by peratu » Sat Oct 30, 2010 2:13 pm

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

Post Reply

Return to “Volume 118 (11800-11899)”