Время

14:46:51
24 May 2012
Версия для печати

Смешная функция

   Мы любим рекурсию!  Не так ли?

   Рассмотрим рекурсивную функцию w(a, b, c) с тремя параметрами:

if a <= 0 or b <= 0 or c <= 0, then w(a, b, c) returns:

      1

 if a > 20 or b > 20 or c > 20, then w(a, b, c) returns:

      w(20, 20, 20)

 if a < b and b < c, then w(a, b, c) returns:

      w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)

 otherwise it returns:

     w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1)

   Здесь приведена самая простая реализация. Проблема состоит в том, что если указанную функцию реализовать напрямую, то даже для небольших значений a, b и c (например a = 15, b = 15, c = 15), программа будет работать часами из-за присутствующей рекурсии.


Технические условия

   Входные данные

   Каждая строка содержит три числа a, b, c. Последняя строка содержит -1 -1 -1 и не обрабатывается. Для каждой входной тройки Вам следует эффективно вычислить значение w(a, b, c).

   Выходные данные

   Для каждой тройки вывести значение w(a, b, c).


Информация о задаче

Лимит времени: 1 секунда
Лимит памяти: 64 MB
Баллы за пройденный тест: 50
Сложность: 7% 27/29
Классификация: Рекурсия

Пример

Пример входных данных

1 1 1
2 2 2
10 4 6
50 50 50 
-1 7 18
-1 -1 -1

Пример выходных данных

w(1, 1, 1) = 2
w(2, 2, 2) = 4
w(10, 4, 6) = 523
w(50, 50, 50) = 1048576
w(-1, 7, 18) = 1

Пояснение: Остерегайтесь долгого выполнения программы!



← Нумерация деревьев Список задач Двоичное умножение →