ACMP 631

Ссылка на задачу

• ACMP #631 — Отгадай число

Похожие задачи

• Интернет-олимпиада 25.03.2006, усложнённый уровень, E

Комментарии

Неоптимальное решение за O(N²):

Вид подзадачи: d[i] — минимальное количество конфет для отгадывания числа i.

Рекуррентная формула: d[i] = min(max(d[i - j] + 2, d[j] + 1)), где j ∈ 1..(i - 1).

База рекурсии: d[1] = 0.

Вид ответа: d[n]. Сложность O(N²).

Решение за O(N):

Вид подзадачи: d[i] — минимальное количество конфет для отгадывания числа i; m[j] — максимальное число, для отгадывания которого нужно j конфет.

Рекуррентная формула: d[i] = max(d[i - x] + 2, d[x] + 1), где x = m[d[i - 1] - 1]).

База рекурсии: d[] = {0, 0, 2, 3, ...}; m[] = {1, 0, 2, 3, ...}.

Вид ответа: d[n]. Сложность O(N).