프로그램 명: coci_planina
제한시간: 1 초
[요약]
정사각형의 꼭지점에 4 개의 점으로 시작 해서 한 번의 동작 후에는 4 점의 중점에 새로운 점을 찍어 나가는
과정을 반복할 때 n 번 반복 후 점의 개수를 구하는 문제.
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:
-
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.
-
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.
입력
The first and only line of input contains one integer N (1 ≤ N ≤ 15), number of
iterations.
출력
The first and only line of output should contain one number, the number of points
stored after N iterations.
입출력 예
입력
1
출력
9
입력
2
출력
25
입력
5
출력
1089
출처:coci 2009-2010 contest4 2/6
[질/답]
[제출 현황]
[푼 후(0)]