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

Автор YouKnowCipher, история, 7 дней назад, По-английски

Problem statement: You are given an integer $$$n$$$. There are n sticks of length $$$1, 2, 3, ..., n$$$. You find to find out how many incongruent triangles can be formed by using three of the given sticks. Output the result modulo $$$10^{12} + 9$$$.

Constraint: $$$4 < n < 10^{12}$$$, where $$$n$$$ is a positive integer.

My idea: I analyzed some base cases. After that, I transformed the problem into an equation with a nested loop. After resolving the nested loop, I determined the number of triangles, denoted as $$$x$$$, to be,

$$$x=\sum_{i=1}^{n} \left\lceil i \cdot \frac{i+1}{2} \right\rceil + 2 \cdot \sum_{i=1}^{n} \left\lceil \frac{i+1}{2} \right\rceil - \sum_{i=1}^{n} \left\lceil \frac{i+1}{2} \right\rceil^2 - n(n+1) $$$

I can't optimize it for the ceiling function. It is working on $$$O(n)$$$. But the constraint of the problem is: $$$4 < n < 10^{12}$$$. Therefore, we can't iterate over n. However, Can it be simplified? (Can we express this equation without using the summation sign?)

Thanks in advance for your assistance.

Полный текст и комментарии »

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