Альпинист планирует маршрут, проходящий через несколько горных лагерей. Каждый лагерь характеризуется своей высотой над уровнем моря. Из одного лагеря можно перейти в другой, если высота второго лагеря меньше высоты первого не более чем на 48 метров. Альпинист может не более десяти раз за весь маршрут воспользоваться страховочной системой, позволяющей выполнить переход, при котором высота второго лагеря меньше высоты первого не более чем на 75 метров. Каждый лагерь может быть посещён не более одного раза. Маршрут может быть начат в любом из лагерей и считается завершённым, если из текущего лагеря невозможно выполнить допустимый переход ни обычным способом, ни с использованием страховочной системы.
Определите наибольшее возможное количество лагерей, которые может включать маршрут, а также максимально возможную высоту лагеря, на котором маршрут завершается, при таком количестве лагерей.
Входные данные
Задание 26
В первой строке входного файла находится число N — количество горных лагерей (натуральное число, не превышающее 100 000). В следующих N строках находятся значения высот лагерей в метрах (все числа натуральные, не превышающие 1 000 000), каждое — в отдельной строке. Запишите в ответе два целых числа: сначала наибольшее возможное количество лагерей, которые может включать один маршрут, а затем максимально возможную высоту лагеря, на котором маршрут завершается, при таком количестве лагерей.
Типовой пример организации данных во входном файле
6
20
12
15
8
10
5
Пример входного файла приведён для шести горных лагерей. Минимальная допустимая разница для обычного перехода составляет 3 метра, при этом один раз разрешён переход до 6 метров с использованием страховочной системы. При этих данных маршрут с максимальным количеством лагерей включает 6 лагерей с высотами 20, 15, 12, 10, 8, 5, а высота завершающего лагеря равна 5.
Спец-переход использован один раз (20 → 15).
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.
Ответ:
Определите наибольшее возможное количество лагерей, которые может включать маршрут, а также максимально возможную высоту лагеря, на котором маршрут завершается, при таком количестве лагерей.
Входные данные
Задание 26
В первой строке входного файла находится число N — количество горных лагерей (натуральное число, не превышающее 100 000). В следующих N строках находятся значения высот лагерей в метрах (все числа натуральные, не превышающие 1 000 000), каждое — в отдельной строке. Запишите в ответе два целых числа: сначала наибольшее возможное количество лагерей, которые может включать один маршрут, а затем максимально возможную высоту лагеря, на котором маршрут завершается, при таком количестве лагерей.
Типовой пример организации данных во входном файле
6
20
12
15
8
10
5
Пример входного файла приведён для шести горных лагерей. Минимальная допустимая разница для обычного перехода составляет 3 метра, при этом один раз разрешён переход до 6 метров с использованием страховочной системы. При этих данных маршрут с максимальным количеством лагерей включает 6 лагерей с высотами 20, 15, 12, 10, 8, 5, а высота завершающего лагеря равна 5.
Спец-переход использован один раз (20 → 15).
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.
Ответ:
💡 Пошаговый разбор и решение:
Приведём решение на языке Python.
f = open('26.txt')
n = int(f.readline())
a = sorted([int(x) for x in f])[::-1]
otv = []
for vl in range(n):
strax_system = 0
lager = [a[vl]]
for nl in range(vl+1, n):
if (lager[-1] - a[nl]) > 75:
break
if 75 > (lager[-1] - a[nl]) > 48:
strax_system += 1
if strax_system > 10:
break
lager.append(a[nl])
otv.append([len(lager), lager[-1]])
print(*max(otv))
Ответ: 3434 302293.
f = open('26.txt')
n = int(f.readline())
a = sorted([int(x) for x in f])[::-1]
otv = []
for vl in range(n):
strax_system = 0
lager = [a[vl]]
for nl in range(vl+1, n):
if (lager[-1] - a[nl]) > 75:
break
if 75 > (lager[-1] - a[nl]) > 48:
strax_system += 1
if strax_system > 10:
break
lager.append(a[nl])
otv.append([len(lager), lager[-1]])
print(*max(otv))
Ответ: 3434 302293.
Правильный ответ:
3434&302293
📚 Похожие разобранные задания по предмету:
ID 34036 • Задание №24
На обработку поступает последовательность из четырёх целых чисел. Нужно написать программу, которая выводит на...
ID 30560 • Задание №7
Дан фрагмент электронной таблицы:
A
B
C
1
2
3
2
=(A1-5)/B1
=A2+C1
=A2
[рис.] Какое целое число должно быт...
🔗 Другие задания линии №26 по предмету Информатика:
ID 34439
Системный администратор раз в неделю создаёт архив пользовательских файлов. Однако объём диска,...
ID 34440
Системный администратор раз в неделю создаёт архив пользовательских файлов. Однако объём диска,...
ID 34441
Системный администратор раз в неделю создаёт архив пользовательских файлов. Однако объём диска,...
ID 34442
Системный администратор раз в неделю создаёт архив пользовательских файлов. Однако объём диска,...
ID 34443
Системный администратор раз в неделю создаёт архив пользовательских файлов. Однако объём диска,...