Ограничение времени 1 секунда
Ограничение памяти 256Mb
Ввод стандартный ввод или input.txt
Вывод стандартный вывод или output.txt
Петя - начинающий программист. Сегодня он написал код из
n
строк.
К сожалению оказалось, что этот код трудно читать. Петя решил исправить это, добавив в различные места пробелы. А точнее, для
i
-й строки ему нужно добавить ровно
a
i
пробелов.
Для добавления пробелов Петя выделяет строку и нажимает на одну из трёх клавиш: Space, Tab, и Backspace. При нажатии на Space в строку добавляется один пробел. При нажатии на Tab в строку добавляются четыре пробела. При нажатии на Backspace в строке удаляется один пробел.
Ему хочется узнать, какое наименьшее количество клавиш придётся нажать, чтобы добавить необходимое количество пробелов в каждую строку. Помогите ему!
Формат ввода
Первая строка входных данных содержит одно целое положительное число
n
(
1
≤
n
≤
1
0
5
)
– количество строк в файле.
Каждая из следующих
n
строк содержит одно целое неотрицательное число
a
i
(
0
≤
a
i
≤
1
0
9
)
– количество пробелов, которые нужно добавить в
i
-ю строку файла.
Формат вывода
Выведите одно число – минимальное количество нажатий, чтобы добавить в каждой строке необходимое количество пробелов.
C/C++
Петя - начинающий программист.
int n;
cin >> n;
cout i / 4 табуляции + 0 пробелов + 0 BS
i % 4 == 1 -> i / 4 табуляции + 1 пробел + 0 BS
i % 4 == 2 -> i / 4 табуляции + 2 пробела + 0 BS
i % 4 == 3 -> i / 4 + 1 табуляция + 0 пробелов + 1 BS
А дальше берём школьную формулу суммы арифметической прогрессии и добавляем учёт неравномерности кол-ва символов.
Валера Веренич
А чем плох такой вариант?
Для решения этой задачи можно использовать жадный алгоритм: для каждой строки попробуем добавлять пробелы так, чтобы сначала использовать максимально возможное число Tab, затем оставшееся количество пробелов заполнить Spaces и, наконец, удалить лишние Spaces при помощи Backspace.
Код решения задачи на Python:
```python
n = int(input())
spaces = [int(input()) for _ in range(n)]
tabs = []
spaces_left = []
for s in spaces:
t, s = divmod(s, 4) # сколько целых Tab можно добавить
tabs.append(t)
spaces_left.append(s)
ans = sum(tabs) # нажатий за добавление Tab
for i in range(n-1):
diff = spaces_left[i] - tabs[i] # сколько пробелов нужно ещё добавить в i-ю строку
if diff > spaces_left[i+1]: # если не хватает пробелов в следующей строке, нужно добавить ещё нажатий
ans += diff - spaces_left[i+1]
spaces_left[i+1] = diff
spaces_left[i+1] -= diff # добавим отставшиеся пробелы в следующую строку
ans += sum(spaces_left) # нажатий за добавление Spaces
ans += max(0, sum(spaces_left) - sum(tabs)) # нажатий за удаление Spaces
print(ans)
```
Время работы алгоритма O(n) (если не учитывать вызовы функций `divmod` и `max`, время которых можно считать постоянным), поэтому он должен корректно работать на всех возможных входных данных.
Код решения задачи на Python:
```python
n = int(input())
spaces = [int(input()) for _ in range(n)]
tabs = []
spaces_left = []
for s in spaces:
t, s = divmod(s, 4) # сколько целых Tab можно добавить
tabs.append(t)
spaces_left.append(s)
ans = sum(tabs) # нажатий за добавление Tab
for i in range(n-1):
diff = spaces_left[i] - tabs[i] # сколько пробелов нужно ещё добавить в i-ю строку
if diff > spaces_left[i+1]: # если не хватает пробелов в следующей строке, нужно добавить ещё нажатий
ans += diff - spaces_left[i+1]
spaces_left[i+1] = diff
spaces_left[i+1] -= diff # добавим отставшиеся пробелы в следующую строку
ans += sum(spaces_left) # нажатий за добавление Spaces
ans += max(0, sum(spaces_left) - sum(tabs)) # нажатий за удаление Spaces
print(ans)
```
Время работы алгоритма O(n) (если не учитывать вызовы функций `divmod` и `max`, время которых можно считать постоянным), поэтому он должен корректно работать на всех возможных входных данных.
Похожие вопросы
- Сложен ли С (С#) в изучении, начинающему программисту?
- С++ Петя успевает по математике лучше всех в классе, поэтому учитель задал ему сложное домашнее задание,
- Вопрос к программистам
- На какие технологии с/с++ обратить внимание для трудоустройства программистом?
- Стоит ли учиться на программиста чтобы создавать игры?
- Товарищи программисты,помогите решить задачу для 1 курса .
- Совет по обучению на программиста.
- У меня вот такой вопрос, к опытным программистам. По поводу c++, и математики.
- Программисты, нужна помощь
- Как стать программистом с нуля и тяжело ли это?