COCI 2009/2010, Contest #4

Task PLANINA

Mirko and Slavko are filming a movie adaptation of the popular SF novel "Chicks in space 13". The script requires them to present a lot of different worlds so they decided to film the entire movie in front of a green screen and add CGI backgrounds later. Mirko heard that the best way to generate artificial terrain is to use midpoint displacement algorithm.

To start the algorithm, Mirko selects 4 points forming a perfect square. He then performs the following steps:

1. On each side of the square, he adds a new point in the exact middle of the side. The height of this new point is the average height of the two points on that side.
2. In the exact center of the square he adds a new point whose height is the average height of all 4 square vertices, plus a small random value.

After those two steps are performed, he now has 4 new squares. He performs the same steps on the newly created squares again and again until he is pleased with the results. The following diagram illustrates 2 iterations of the algorithm.

Mirko noticed that some of the points belong to more than one square. In order to decrease memory consumption, he stores calculates and stores such points only once. He now wonders how many points in total will he need to store in memory after N iterations.

Input

The first and only line of input contains one integer N (1 ≤ N ≤ 15), the number of iterations.

Output

The first and only line of output should contain one number, the number of points stored after N iterations.

Sample Tests

1

9

2

25

5

1089

All Submissions
Best Solutions

Point Value: 5
Time Limit: 1.00s
Memory Limit: 32M
Added: Jul 14, 2013

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

for anyone thats stuck, its a algorithm dealing with powers of 2, some thinking and you will get it