Работа с массивами.

[Katmandu]

Пусть имеется массив, состоящий из $N$ чисел: $A[1],...,A[N]$
Необходимо построить массив $B$, состоящий из $N$ чисел, по следующему правилу:
$B[i] = A[1] \cdot ...\cdot A[i-1]\cdot A[i+1]\cdot ...\cdot A[N]$

Ограничения:
Время работы алгоритма: $O(N)$
Память: $O(N)$
Нельзя использовать операцию деления.


Подскажите, хотя бы идею, чтобы достичь время работы O(N)

Самое простое, что приходит в голову. Это просто перебрать, для каждого нового элемента $B$, $N-1$ элемент из массива $A$. Но тогда сложность будет $O(N^2)$

[12d3]

Строите два вспомогательных массива
$C[i]=A[1]\cdot...\cdot A[i]$
$D[i]=A[i+1]\cdot...\cdot A[N]$
Делается это линейно.
Потом перемножаете нужные элементы этих двух массивов, получаете $B[i]$.
Не очень-то олимпиадная задачка, как мне кажется.