Задача 7: Удаление данных
Случилась беда — шпиона Сергея раскрыли, и теперь ему нужно срочно бежать! Но перед побегом он должен удалить все компрометирующие данные со своего компьютера.
На компьютере Сергея сохранены N файлов, пронумерованных числами от 1 до N. У каждого из файлов есть размер в байтах: a1, a2, ..., aN. Все данные на компьютере Сергея хорошо зашифрованы. Шпион определил, что для удаления файла с номером i понадобится минимум из ai−1 и ai+1 секунд (для удаления первого файла потребуется a2 секунд, а для удаления последнего — aN−1 секунд). Когда остается всего один файл, он удаляется мгновенно. После удаления файла с номером i остальные файлы перенумеровываются последовательно.
У Сергея осталось очень мало времени, а ему еще нужно собрать вещи, поэтому он просит у вас помощи. Определите, какое минимальное время понадобится шпиону, чтобы удалить все файлы. Сергей может удалять файлы последовательно в любом порядке.
Входные данные
В первой строке выходных данных записано одно целое число N (1 ≤ N ≤ 105) — количество файлов на компьютере шпиона.
В каждой из следующих N строк записано по одному целому числу ai (1 ≤ ai ≤ 104) — размер файла с номером i на компьютере Сергея.
Выходные данные
В единственной строке выведите одно число — минимальное время, которое понадобится Сергею для удаления всех файлов.
Система оценки
Решения, правильно работающие только для случаев, когда N не превосходит 10, будут оцениваться в 20 баллов.
Решения, правильно работающие только для случаев, когда N не превосходит 1000, будут оцениваться в 60 баллов.
Примеры
Ввод
Вывод
Пояснение
5
1
2
3
1
100
4
У Сергея есть файлы с размерами 1, 2, 3, 1, 100. Один из вариантов решения приведен ниже:
1. Удалим последний файл. Это займет одну секунду.
2. Затем удалим файл размера 2 за одну секунду.
3. Далее удалим файл размера 3 за одну секунду.
4. Теперь удалим любой из оставшихся двух файлов за одну секунду.
5. Последний файл моментально удалится сам.
Итого, Сергею понадобится 1 + 1 + 1 + 1 = 4 секунды.
1
1
0
У Сергея изначально есть всего один файл, который сразу же удалится.
Случилась беда — шпиона Сергея раскрыли, и теперь ему нужно срочно бежать! Но перед побегом он должен удалить все компрометирующие данные со своего компьютера.
На компьютере Сергея сохранены N файлов, пронумерованных числами от 1 до N. У каждого из файлов есть размер в байтах: a1, a2, ..., aN. Все данные на компьютере Сергея хорошо зашифрованы. Шпион определил, что для удаления файла с номером i понадобится минимум из ai−1 и ai+1 секунд (для удаления первого файла потребуется a2 секунд, а для удаления последнего — aN−1 секунд). Когда остается всего один файл, он удаляется мгновенно. После удаления файла с номером i остальные файлы перенумеровываются последовательно.
У Сергея осталось очень мало времени, а ему еще нужно собрать вещи, поэтому он просит у вас помощи. Определите, какое минимальное время понадобится шпиону, чтобы удалить все файлы. Сергей может удалять файлы последовательно в любом порядке.
Входные данные
В первой строке выходных данных записано одно целое число N (1 ≤ N ≤ 105) — количество файлов на компьютере шпиона.
В каждой из следующих N строк записано по одному целому числу ai (1 ≤ ai ≤ 104) — размер файла с номером i на компьютере Сергея.
Выходные данные
В единственной строке выведите одно число — минимальное время, которое понадобится Сергею для удаления всех файлов.
Система оценки
Решения, правильно работающие только для случаев, когда N не превосходит 10, будут оцениваться в 20 баллов.
Решения, правильно работающие только для случаев, когда N не превосходит 1000, будут оцениваться в 60 баллов.
Примеры
Ввод
Вывод
Пояснение
5
1
2
3
1
100
4
У Сергея есть файлы с размерами 1, 2, 3, 1, 100. Один из вариантов решения приведен ниже:
1. Удалим последний файл. Это займет одну секунду.
2. Затем удалим файл размера 2 за одну секунду.
3. Далее удалим файл размера 3 за одну секунду.
4. Теперь удалим любой из оставшихся двух файлов за одну секунду.
5. Последний файл моментально удалится сам.
Итого, Сергею понадобится 1 + 1 + 1 + 1 = 4 секунды.
1
1
0
У Сергея изначально есть всего один файл, который сразу же удалится.
Ответ
4
(83 оценки)
92
Wolfram3387
2 года назад
Светило науки - 28 ответов - 0 раз оказано помощи
Ответ:
n = int(input())
min = 10**5
for i in range(n):
element = int(input())
if element < min:
min = element
print((n-1) * min)
Пошаговое объяснение:
Язык python 3, самое быстрое решение без массивов и долгих поисков. Берём и удаляем все элементы всегда возле самого минимального числа.
Ответ
3
(31 оценка)
42
ExeRhythm
2 года назад
Светило науки - 36 ответов - 109 раз оказано помощи
Ответ:
n = int(input())
ints = []
for i in range(n):
ints.append(int(input()))
min_val = min(ints)
print(min_val * (n - 1))
Берем минимальное число из списка и удаляем все числа рядом с ним. Это будет минимальное время
гг Сергею
F Сергею
все попался шаранойд
Бедный Серёга, плакали всем детдомом =( F