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 122 MiB

Группа математиков проводит бои между натуральными числами. Результаты боя между двумя натуральными числами, вообще говоря, случайны, однако подчиняются следующему правилу: если одно из чисел не менее чем в два раза превосходит другое, то большее число всегда побеждает; в противном случае победить может как одно, так и другое число.

Бой называется неинтересным, если его результат предопределён. Множество натуральных чисел называется мирным, если бой любой пары различных чисел из этого множества неинтересен. Силой множества называется сумма чисел в нём. Сколько существует мирных множеств натуральных чисел силы n?

Giriş verilənləri

Одно число n (1n2000).

Çıxış verilənləri

Выведите одно число - количество мирных множеств натуральных чисел силы n.

Nümunə

Giriş verilənləri #1
2
Çıxış verilənləri #1
1
Giriş verilənləri #2
5
Çıxış verilənləri #2
2
Müəllif Ivan Kazmenko
Mənbə SPbSU Group A1 Third Training - Dynamic Programming