Задача 98013

Темы:    [ Процессы и операции ] [ Теория алгоритмов (прочее) ]

Сложность: 3+ Классы: 8,9,10

Условие

Автор: Фомин С.В.

Даны 1000 линейных функций:  f_k(x) = p_kx + q_k  (k = 1, 2, ..., 1000).  Нужно найти значение их композиции  f(x) = f₁(f₂(f₃(...f₁₀₀₀(x)...)))  в точке x₀. Докажите, что это можно сделать не более чем за 30 стадий, если на каждой стадии можно параллельно выполнять любое число арифметических операций над парами чисел, полученных на предыдущих стадиях, а на первой стадии используются числа  p₁, p₂, ..., p₁₀₀₀,  q₁, q₂, ..., q₁₀₀₀,  x₀.

Решение

    f(x) = p₁p₂ ... p₁₀₀₀x₀ + p₁p₂ ... p₉₉₉q₁₀₀₀ + p₁p₂ ...p₉₉₈q₉₉₉ + ... + p₁q₂ + q₁.
  Самое "длинное" из слагаемых – произведение 1001 числа  p₁p₂ ...p₁₀₀₀x₀  – вычисляется за 10 стадий, поскольку  1001 < 2¹⁰:  на первой стадии вычисляем 500 произведений  p₁p₂, p₃p₄, ..., p₉₉₉p₁₀₀₀,  на второй – 250 произведений  (p₁p₂)(p₃p₄), ..., (p₉₉₇p₉₉₈)(p₉₉₉p₁₀₀₀)
и т. д. Параллельно вычислим все остальные слагаемые.
  Аналогично за 10 следующих стадий можно вычислить сумму  f(x)  1001 слагаемого.

Замечания

5 баллов

Источники и прецеденты использования

олимпиада
Название	Турнир городов
Турнир
Дата	1988/1989
Номер	10
вариант
Вариант	весенний тур, основной вариант, 9-10 класс
Задача
Номер	3