Задача 24
Текстовый файл содержит не более 1 200 000 прописных символов латинского алфавита. Необходимо определить максимальное количество последовательных символов, среди которых любые два символа из набора {Q, U, A, S} не стоят рядом (с учётом повторений).
Решение: Заменим все символы из набора {Q, U, A, S} на один символ (например, «!»). Затем переберем символы строки, считая количество подряд идущих восклицательных знаков. Максимальное количество таких знаков — ответ.
f = open('24.py', 'r')
s = f.readline()
s = s.replace('Q', '!')
s = s.replace('U', '!')
s = s.replace('A', '!')
s = s.replace('S', '!')
k, max_k = 1, 1
for i in range(len(s) - 1):
if s[i] == s[i+1] == '!':
k += 1
else:
max_k = max(max_k, k)
k = 1
max_k = max(max_k, k)
print(max_k)Ответ: 544
Задача 25
Задана маска 12??36*1, где ? обозначает ровно одну произвольную цифру, а * — любую последовательность цифр произвольной длины (включая пустую). Необходимо найти все натуральные числа, не превышающие 10<sup>8</sup>, которые соответствуют данной маске и делятся на 273 без остатка. Результат: найденные числа в порядке возрастания и результат деления каждого числа на 273.
Решение: Перебираем числа, кратные 273, преобразуем их в строки и проверяем соответствие маске.
for i in range(0, 10**8, 273):
s = str(i)
if len(s) >= 7 and s[0:2] == '12' and s[4:6] == '36' and s[-1] == '1':
print(i, i // 273)Задача 26
Камера хранения в аэропорту содержит K ячеек (1…K). Багаж кладется в свободную ячейку с минимальным номером. Ячейка доступна для следующего багажа со следующей минуты после окончания срока хранения. Если свободных ячеек нет, багаж не принимается. Найти количество принятого багажа за 24 часа и номер ячейки, в которую сдал багаж последний пассажир.
Входные данные: K — количество ячеек, N — количество пассажиров, N пар чисел (время сдачи, время забора).
Решение: Моделируем работу камеры хранения. Сортируем данные по времени сдачи багажа. Создаем список storage для хранения времени освобождения каждой ячейки. Перебираем пассажиров, ищем свободную ячейку с минимальным номером и обновляем время освобождения этой ячейки.
with open('26.txt', 'r') as f:
k = int(f.readline())
n = int(f.readline())
data = []
for line in f:
data.append(list(map(int, line.split())))
data.sort()
storage = [0] * k
count, last = 0, 0
for i in range(n):
for j in range(k):
if data[i][0] > storage[j]:
storage[j] = data[i][1]
count += 1
last = j + 1
break
print(count, last)Задача 27
Станция ведет наблюдение за количеством осадков, показания записываются каждую минуту. Определить пару измерений, между которыми прошло не менее K минут, и сумма показаний которой максимальна.
Входные данные: N — количество измерений, K — минимальное количество минут между измерениями, N значений — показания.
Решение: Перебираем измерения, находим максимальное значение за K минут до текущего и считаем сумму.
with open('a.txt', 'r') as f:
n, k = map(int, f.readline().split())
a = list(map(int, f.readlines()))
max_sum = 0
max_val = 0
for i in range(k, n):
max_val = max(max_val, a[i - k])
max_sum = max(max_sum, max_val + a[i])
print(max_sum)