e-olymp 6264. Энергетический магнат

Задача

Маленький Вася играет в новую компьютерную игру — пошаговую стратегию «Энергетический магнат».

Правила игры достаточно просты:

    • Доска содержит [latex]n[/latex] слотов, расположенных в линию.
    • Имеется набор электростанций, каждая из которых занимает один или два слота подряд, и производит одну единицу энергии.
    • Каждый ход игры позволяет построить одну новую электростанцию, ее можно расположить на доске в любом месте по Вашему усмотрению. Если для новой электростанции нет места, Вы можете удалить некоторые старые электростанции.
    • После выполнения каждого хода компьютер вычисляет количество энергии, производимой расположенными на доске электростанциями, и добавляет его к общему количеству очков в игре.

Пример №1.

Вася уже знает все типы электростанций, которые он сможет построить на каждом шаге игры. Он хочет знать, какое максимальное количество очков он сможет получить в игре. Можете ли Вы ему помочь?

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

Первая строка содержит число [latex]n \left(1\leqslant n\leqslant 1000 \right)[/latex] — количество слотов на доске. Вторая строка содержит строку [latex]s[/latex]. [latex]i[/latex]-ый символ строки равен [latex]1[/latex], если Вы можете построить однослотовую электростанцию в [latex]i[/latex]-ом раунде, и символ [latex]2[/latex], если Вы можете построить двуслотовую электростанцию в [latex]i[/latex]-ом раунде. Количество раундов в игре не превосходит [latex]100000[/latex].

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

Вывести одно число — наибольшее количество очков, которое можно достичь.

Тесты

Вхлодные данные Выходные данные
1 3

21121

10
2 2

12

2
3 2

211

4

Код программы

Решение задачи

Будем увеличивать num на 1, если встречается двуслотовая электростанция. Если нет свободных слотов [latex]temp — c\lt0[/latex] и [latex]num\geqslant1[/latex], то вместо двуслотовой ставим станцию, которая в этом ходе должна быть [latex]temp += (2 — c)[/latex] и вычитаем одно очко. В итоге смотрим, если двуслотовых электростанций нет [latex]num\gt 1[/latex], то считаем однослотовые: [latex]n — temp[/latex], а если они есть, то: [latex]n — temp — num[/latex].

Ссылки

  • Условие задачи на e-olymp
  • Код программы ideone

Добавить комментарий