|
||||||||||||||
МИОО, МЦНМО, Оргкомитет Московской олимпиады по информатике
Дистанционные семинары
по подготовке к олимпиадам по информатике
Задача 02-4. "Лесенки"
(Разбор)
Переформулируем нашу задачу на язык математики. В каждом следующем слое (считая сверху вниз) кубиков больше, чем в предыдущем, а в сумме их n. Значит, нам требуется представить n в виде суммы возрастающих натуральных слагаемых.
---
1 | |
---------
4 | | | | |
-----------
5 | | | | | |
-----------------
8 | | | | | | | | |
-----------------
n=1+4+5+8
Пусть в качестве первого слагаемого мы взяли L, тогда нам требуется n-L разбить на слагаемые. Но теперь добавляется дополнительное условие - слагаемые должны быть больше либо равны L+1. Значит, нам достаточно научиться считать число разбиений числа n на слагаемые не меньшие k (обозначим an,k). Есть два случая: слагаемое k либо входит в разбиение (таких способов an-k,k+1), либо нет (таких способов an,k+1). Так как никакое разбиение не подходит одновременно под оба эти случая, то an,k=an-k,k+1+an,k+1 Заметим, что для единицы существует единственное разбиение: 1 = 1. Значит a1,0 = a1,1 = 1, a1,f = 0, где f >= 2. an,k удобно вычислять в порядке невозрастания k. При равных k - в произвольном порядке.
Данный алгоритм выполняет порядка N2 действий.