eolymp
bolt
Try our new interface for solving problems
Məsələlər

Зоны на плоскости

Зоны на плоскости

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Рассмотрим зоны z_i на плоскости, состоящие из треугольников. Первая зона z_1 состоит из двух прямоугольных равнобедренных треугольников, образующих квадрат. Зона z_{n+1} получается из зоны z_{n }так: на катетах каждого треугольника из зоны z_n строятся два равнобедренных прямоугольных треугольника. Если при этом новый треугольник попадает в зону с меньшим номером, то он не берется. Объединение получившихся треугольников и составляет зону z_{n+1}.

Ваша задача - найти количество простых многоугольников, из которых состоит зона z_n.

Giriş verilənləri

Во входном файле записано число n (1n2000).

Çıxış verilənləri

В выходной файл выведите единственное число - количество простых многоугольников, из которых состоит зона z_n.

Nümunə

Giriş verilənləri #1
1
Çıxış verilənləri #1
1
Müəllif Dmitry Gozman
Mənbə Dmitry Gozman Contest 1, Petrozavodsk training camp, January 2007