Блог пользователя tuna

Sierpinski Triangle Problem
Автор tuna, история, 9 лет назад, По-английски

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

  • Проголосовать: нравится
  • +4
  • Проголосовать: не нравится

»
9 лет назад, # |
← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

The answer is equal to (n - 1) * n * (n + 1)

→ Ответить
»
9 лет назад, # |
← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить