Question

Клиппи и Мерлин грабят банк 100 БАЛЛОВ! Клиппи и Мерлин решили грабить банк, который представляет собой N расположенных в ряд банковских ячеек, пронумерованных последовательно числами от 1 до N.С помощью своего друга Ровера, который работал в банке сторожевым псом, они добыли ключи от всех ячеек, а также узнали, как много ценностей хранится в каждой ячейке.Чтобы не вызывать лишних подозрений, Клиппи и Мерлин решили ограбить всего две ячейки — по одной на каждого. Также, чтобы охрана банка не почуяла неладного, они решили работать далеко друг от друга — между ними должно быть не меньше K банковских ячеек.Входные данныеВ первой строке вводятся два числа — N ( 2 ≤N≤ 105) и K (0 ≤KВыходные данныеВыведите два числа в возрастающем порядке — номера ячеек, которые нужно ограбить, чтобы суммарно украсть как можно более дорогие ценности, не вызвав при этом лишних подозрений. Если вариантов несколько, выберите тот, в котором меньший номер вскрываемой ячейки был бы как можно ближе к единице, чтобы в экстренном случае покинуть банк как можно скорее. Если и таких вариантов несколько, выберите тот, в котором и больший номер вскрываемой ячейки был бы как можно меньше.ПримерыВвод6 2 2 4 3 1 4 4____вывод2 5

Answer 1

Ответ:

Решение

def linear(cells): max_a = 0 max_a_i = 0 max_sum = 0 # Перебираем все возможные левые ячейки - 'a' for a_i, a in enumerate(cells[:-distance - 1]): # Находим ближайшую правую ячейку b_i = a_i + distance + 1 b = cells[b_i] # Запоминаем левую ячейку с максимальным значением. if a > max_a: max_a = a max_a_i = a_i # По условию для текущей правой ячейки ('b') подойдёт любая # левая, стоящая от неё на расстоянии больше, чем 'k'. # Логично, что надо выбрать левую ячейку с максимальным значением. # Таким образом, сложив правую ячейку с максимальной левой, получаем # лучшую сумму для данной правой ячейки. if max_a + b > max_sum: max_sum = max_a + b # После проверки всех ячеек, в 'answer' будут номера # 'a' и 'b' с лучшей суммой answer = (max_a_i, b_i) print(answer[0] + 1, answer[1] + 1)

Тестирование

# Содержимое файлов с тестами $ tail -n +1 -- input_* ==> input_1.txt <== 6 0 2 9 9 1 4 4 ==> input_2.txt <== 6 1 5 7 6 8 0 0 ==> input_3.txt <== 6 1 5 9 9 1 4 6 ==> input_4.txt <== 10 1 1 1 4 1 1 1 3 1 3 1

Команда на bash для проверки тестов:

$ for f in input*; do echo "${f}"; ./source.py < "${f}"; echo; done

Output

input_1.txt 2 3 input_2.txt 2 4 input_3.txt 2 6 input_4.txt 3 7