tuna's blog

Sierpinski Triangle Problem
By tuna, history, 9 years ago, In English

I need help with this problem Triangles Problem Idea: The given input is N the level of the triangle, how can I calculate the number of all fragments(lines that contain one or more line segments in the triangle)? Do you have any ideas? I tried N!/2 but it is not efficient and probably incorrect becase 1<= N=2m < 64000.

Sample Input:

3 (number of tests)

1

2

4

Sample Output:

3

12

60

  • Vote: I like it
  • +4
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
9 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

The answer is equal to

Unable to parse markup [type=CF_TEX]

→ Reply
»
9 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

For a line of N matches answer is N + (N - 1) + ... + 1 = N * (N + 1) / 2.
We have three type of lines — horizontal and two oblique.
Let's find the answer to one type, then multiply by 3. Is the sum of the answers to the lengths of the lines 1, 2, ..., N,
i.e. 1/2 * (1 * 2 + 2 * 3 + ... + N * (N + 1)) = N * (N + 1) * (N + 2) / 6 (it can be proved by induction).
The final answer is N * (N + 1) * (N + 2) / 2.
p.s. sorry for bad English

→ Reply