4368. Triangular web

In front of you is an infinite triangular grid. It is arranged so that if a vertex is set on fire, then at time 0 that vertex ignites, after one second all vertices directly adjacent to it catch fire, then all vertices adjacent to the already burning ones, and so on. Assume that the fire never goes out.

Initially, one vertex is burning. Determine the number of burning vertices after n seconds.

Input. One integer n (0 ≤ n ≤ 10⁹).

Output. Print the number of burning vertices after n seconds.

Sample input 1	Sample output 1
1	7
Sample input 2	Sample output 2
1500	6754501

SOLUTION

combinatorics

Algorithm analysis

Let us consider how the fire spreads on an infinite triangular grid:

1. Initial vertex. At time , only the initial vertex is burning. This contributes the first unit to the total number of burning vertices.

2. First level (after 1 second). The vertices that are directly adjacent to the initial one catch fire after 1 second. In a triangular grid, each vertex has 6 neighbors. Therefore, the first level contains 6 vertices.

3. Second level (after 2 seconds). In the next second, the vertices that are adjacent to the already burning vertices of the first level, but are not yet burning, catch fire. The second level contains 12 vertices.

One can observe the following pattern: each new level adds 6 more vertices than the previous one.

· First level: 6 vertices

· Second level: 12 vertices

· Third level: 18 vertices

· … and so on.

Thus, we obtain an arithmetic progression with the first term a₁ = 6 and common difference d = 6.

After n seconds, the number of burning vertices is equal to

res = 1 + (6 + 12 + 18 + … + (6 + 6(n – 1)))

Using the formula for the sum of an arithmetic progression , we obtain that

res = 1 + = 1 + (6 + 3(n – 1))n = 1 + 3n(n + 1)

Algorithm implementation

Read the input value of n.

scanf("%lld",&n);

Compute and print the answer.

res = 1 + 3 * n * (n + 1);

printf("%lld\n",res);