Try to derive recurrent formula f(n), where f(n) is number of distinct triangles using rods 1, 2 .. n.
f(n) can be calculated using f(n - 1). Make precalculation for all n.
11401 - Triangle Counting
Moderator: Board moderators
Re: 11401 - Triangle Counting
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman
-
- New poster
- Posts: 49
- Joined: Mon Jun 16, 2014 7:40 pm
Re: 11401 - Triangle Counting
Will someone plz explain the problem. I am having a difficulty in understanding this problem.
Re: 11401 - Triangle Counting
For n = 3. We have rods of length: 1, 2, 3. We can't make any triangle from these rods because they don't satisfy triangle inequality:You are given n rods of length 1, 2…, n. You have to pick any 3 of them & build a triangle. How many distinct triangles can you make? Note that, two triangles will be considered different if they have at least 1 pair of arms with different length.
Code: Select all
a + b > c
a + c > b
b + c > a
For n = 5: 1, 2, 3, 4, 5. We can make 3 triangles using rods: (2, 3, 4), (2, 4, 5), (3, 4, 5).
For n = 6: 1, 2, 3, 4, 5, 6. We can make 7 triangles using rods: (2, 3, 4), (2, 4, 5), (2, 5, 6), (3, 4, 5), (3, 4, 6), (3, 5, 6), (4, 5, 6).
And so on..
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman
-
- New poster
- Posts: 49
- Joined: Mon Jun 16, 2014 7:40 pm
Re: 11401 - Triangle Counting
Thank u so much.
Accepted
Accepted
Re: 11401 - Triangle Counting
For the fastest time, try to find the function f(n) for even n, and for odd n. They have different f(n).