UniLecs135.py

# Задача UniLecs 135 Подсчёт пирамид
# Задача: представьте, что вы строите правую сторону пирамиды (см.на рисунке ниже) из N блоков (на плоскости). В пирамиде на каждом верхнем уровне блоков меньше, чем на нижнем. Необходимо определить, сколько различных пирамид можно построить из N блоков.
# Входные данные: N - натуральное число от 1 до 100.
# Вывод: кол-во всевозможных пирамид из N блоков
# Пример: 
# N = 3; Answer = 2
# N = 5; Answer = 3
# N = 6; Answer = 4
def count_pyramides_v1 ( n, maxb = -1 ):
    # Вариант 1, с рекурсией. Работает, но медленно
    # Подход "снизу вверх" -- оставляем на нижнем уровне от n до
    # минимально возможного 
    # n -- число кубиков
    # maxb -- максимальный базис
    # Для первого запуска, если базис по умолчанию меньше 0, то считаем его равным n
    if maxb <0:
        maxb = n
    # Пирамидку из меньше чем 1 кубика построить не получится
    if n < 1:
        return 0
    # Рассчитываем minb -- минимальный базис пирамидки
    # ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    # NB: Сильное колдунство в этой формуле получается следующим образом.
    # Если мы возьмём плотно забитую пирамидку, то есть такую у которой на
    # первом уровне один кубик, на втором два, на третьем три и так 
    # далее -- то сколько потребуется кубиков на её постройку?
    # Ответ нам дают *треугольные числа* (см. Википедию), a(n)=0.5*(n(n+1)) кубиков
    # для пирамидки на n уровней (и с нижним уровнем шириной n соответственно).
    # Для неполной пирамидки минимальное основание будет соотвествовать ближашей 
    # наибольшей полной пирамидке, наглядный пример для N=8, ближайшая an=10, n=4
    # .
    # O .
    # O O O
    # O O O O       O -- кирпичи, . -- пустые места до полной пирамидки
    # дальше просто из формулы a(n) выражаем n, выкидываем отрицательный корень 
    # и округляем вверх (для этого +0.5 перед int)
    # Можно воспользоваться последовательностью A000217 https://oeis.org/A000217
    # и выбирать из списка типа 
    # def get_n(N):
    #   A000217 = [0, 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120, 136, 153, 171, 190, 210, 231, 253, 276, 300, 325, 351, 378, 406, 435, 465, 496, 528, 561, 595, 630, 666, 703, 741, 780, 820, 861, 903, 946, 990, 1035, 1081, 1128, 1176, 1225, 1275, 1326, 1378, 1431]
    #   for i,an in enumerate(A000217):
    #     if an >= N:
    #       return i
    #   return -1
    # ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

    minb = int(0.5 + ((8*n+1)**0.5-1)/2)
    # s -- счётчик вариантов
    s = 0
    # Строим пирамидки на всех возможных базисах, от minb до n.
    # (В данном случае n+1 -- особенность цыклов в питоне, они бегают от a до <b)
    for i in range(minb, n + 1):
        # Если текущий базис пирамидки меньше или равен максимально разрешённому
        if i <= maxb:
            # ... то проверяем сколько кубиков можно сдвинуть на предыдущие уровни
            if (n - i)==0:  # строго говоря, тут можно написать if n==i:, но я оставил логику движения кубиков
                s = s + 1   # Если ничего не двигаем, считаем +1 вариант
            else:
                # Если можно сдвинуть, то считаем сколькими способами  можно построить пирамидку уровня
                # выше из n-i кубиков, учитывая, что базис должен быть меньше текущего, то есть i-1
                s = s + count_pyramides_v1(n - i, i - 1)
    return s

# Динамическая таблица, которая показывает сколькими способами можно построить пирамидку
# из n кубиков с базисом m. Так как из 0 кубиков пирамидку построить нельзя, то pyramides_nm[n][0]
# будет включать общее число вариантов = сумму по строке
global pyramides_nm
# инициализируем матрицу 100x100
pyramides_nm =[]
a = []
for i in range (0, 101):
    a.append(0)
for i in range (0, 101):
    pyramides_nm.append(a[0:101])

def count_pyramides_v2( n ):
    # Вариант 2, на основании динамического программирования. Так как запоминает предыдущие результаты,
    # то будет работать быстрее при повторных запусках
    # Если мы уже знаем сколько пирамидок можно построить, то возвращаем это число 
    if pyramides_nm[n][0] != 0: return pyramides_nm[n][0]
    # Рассчитываем minb -- минимальный базис пирамидки
    minb = int(0.5 + ((8*n+1)**0.5-1)/2)
    # Строим пирамидки на всех возможных базисах, от minb до n.
    for i in range (minb, n+1):
        if n==i:
            # Из n кубиков на базисе n можно построить только одну пирамидку -- в ряд
            pyramides_nm[n][i]=1
        else:
            # Иначе проверяем сколько пирамидок можно построить из оставшихся n-i кубиков
            # Проверяем знаем ли мы разложения для n-i, еслои нет -- считаем
            if pyramides_nm[n-i][0]==0: count_pyramides_v2( n-i )
            # сумируем все варианты пирамидок из n-i кубиков с базисами меньше i
            sum_minb = sum(pyramides_nm[n-i][1:i])
            # и запоминаем
            pyramides_nm[n][i]=sum_minb 

    # Суммируем все варианты, запоминаем число и возвращаем его
    pyramides_nm[n][0]=sum(pyramides_nm[n][1:101])
    return pyramides_nm[n][0]

tst = [3,5,6,50,70,80,90,100]
res = [2,3,4,3658,29927,77312,189586,444793]

for i,t in enumerate(tst):
    r1=count_pyramides_v1(t)
    r2=count_pyramides_v2(t)
    s = "Test for " + str(t) +" blocks. Expected: " + str(res[i]) + ", V1 " + str(r1) + " - " + str(r1==res[i]) + ", V2 " + str(r2) + " - " + str(r1==res[i]) 
    print(s)