u can do this by building up the triangles...
lets say i have a triangle of size n as its base that is its base has n+1
vertices...lets call this a triangle with size n
to make a triangle of size n+1 we overlap two triangles of size n. put a
single triangle on top..this completes a triangle of size n+1.
note that the overlapping section has size n-1.
/_\
/_\/_\
/_\/_\/_\ triangle of size 3 is made by
overapping two triangles of size 2
/_\ /_\
/_\/_\ /_\/_\ these two.... when we merge them we overlap with a size
1 /_\ and place a /_\ on top to complete
like this
/_\/_\
/_\/_\/_\ plus /_\ gives triangle of size
3
we have a formula T[n] = 2xT[n-1] + 1 - T[n-2] + triangles formed newly
upside down = (n-2)
therefore T[n] = 2xT[n-1] + 1 - T[n-2] + n-2
hope this helps somehow...
i am not sure I got the question right.
--
[Geekru2]
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"google-codejam" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/google-code?hl=en
-~----------~----~----~----~------~----~------~--~---
