Тема 26. Обработка целочисленной информации с использованием сортировки

26.09 Прочие прототипы

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела обработка целочисленной информации с использованием сортировки

Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 41#63604Максимум баллов за задание: 2

В салоне красоты работают A количество мастеров. У каждого человека есть свой номер, начиная с единицы. Директору салона нужно записать B клиентов на следующий день. Порядок записи следующий: клиент звонит в салон и называет время в которое каждый клиент хочет прийти в салон, и в какое время он хочет завершить прием. Директор записывает клиента к мастеру с наименьшим номером, который свободен в тот промежуток, который нужен клиенту. Мастера могут принимать клиентов со следующей минуты после предыдущего клиента. Если таких мастеров нет, то директор сразу во время звонка просит прощения у клиента и сообщает, что он не может записать его.

Длительность рабочего дня салона составляет 600 минут.

Определите сколько клиентов смог записать директор и номер мастера, к которому записался последний клиент.

Входные данные. В первой строке входного файла находится число А – количество мастеров в салоне (натуральное число, не превышающее 1000). Во второй строке находится число В – количество клиентов, которые хотят записаться. В следующих В строках находятся два значения: минута с которой клиент хочет записаться и минута, до которой клиент планирует записаться, отсчёт ведётся от начала рабочего дня салона (все числа положительные, не превышающие 600), для каждого клиента – в отдельной строке. Данные в файле даны в том порядке, в котором клиенты звонили в салон.

Запишите в ответе два целых числа через пробел: сначала количество клиентов, которое сможет записать директор, затем номер мастера, к которому записался последний клиент.

Вложения к задаче

26_5.txt

Показать ответ и решение

f = open(’26_5.txt’)
k = int(f.readline()) # Кол-во мастеров
n = int(f.readline()) # Кол-во клиентов

# Список с записями клиентов по времени
times=[list(map(int, f.readline().split())) for _ in range(n)]
# Массив, в который будут по порядку заноситься номера мастеров
clients = []

# Список с графиком времени каждого специалиста
# Единицей будут помечаться занятые минуты мастера
specialists=[[0]*601 for _ in range(k)]
for start, end in times:
    # Пробегаемся по каждому специалисту,
    # если график свободен для клиента, то добавляем его
    for num in range(k):
        if sum(specialists[num][start:end+1])==0:
            # Добавляем в список номер мастера, к которому обратился клиент
            # (прибавляем единицу, так как нумерация мастеров с единицы, а не с нуля)
            clients.append(num+1)
            # Помечаем занятый период в графике мастера
            for time in range(start, end+1):
                specialists[num][time]=1
            # Прерываем перебор, так как текущий клиент занял место у мастера
            break

# len(clients) — сколько раз клиенты обращались к мастерам
# clients[-1] — номер последнего мастера, к которому обратились
print(len(clients), clients[-1])

Ответ: 328 1

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 42#63608Максимум баллов за задание: 2

На складе хранятся контейнеры в форме куба различного размера. Чтобы сократить занимаемое при хранении место, контейнеры вкладывают друг в друга. Один контейнер можно вложить в другой, если размер стороны внешнего контейнера превышает размер стороны внутреннего на 3 и более условных единиц. Группу вложенных друг в друга контейнеров называют блоком. Количество контейнеров в блоке может быть любым. Каждый блок, независимо от количества и размера входящих в него контейнеров, а также каждый одиночный контейнер, не входящий в блоки, занимает при хранении одну складскую ячейку.

Зная количество контейнеров и их размеры, определите минимальное количество ячеек для хранения всех контейнеров и максимально возможное количество контейнеров в одном блоке.

Вложения к задаче

26_9.txt

Показать ответ и решение

f = open(’26_9.txt’)
n = f.readline()
cubes = sorted([int(i) for i in f], reverse=True)
cklad=[]
while len(cubes)>0:
    block = [cubes.pop(0)]
    for i in range(len(cubes)):
        if (block[-1]-cubes[i])>=3:
            block.append(cubes[i])
            cubes[i]=’’
    cubes=[x for x in cubes if x!=’’]
    cklad.append(block)
print(len(cklad),max(len(c) for c in cklad))

Ответ: 13 2767

Ошибка.
Попробуйте повторить позже

Задача 43#63611Максимум баллов за задание: 2

Длительность рабочего дня салона составляет 900 минут.

Определите сколько клиентов смог записать директор и номер мастера, к которому записался последний клиент.

Входные данные. В первой строке входного файла находится число А – количество мастеров в салоне (натуральное число, не превышающее 1000). Во второй строке находится число В – количество клиентов, которые хотят записаться. В следующих В строках находятся два значения: минута с которой клиент хочет записаться и минута, до которой клиент планирует записаться, отсчёт ведётся от начала рабочего дня салона (все числа положительные, не превышающие 900), для каждого клиента – в отдельной строке. Данные в файле даны в том порядке, в котором клиенты звонили в салон.

Вложения к задаче

26_12.txt

Показать ответ и решение

f = open(’26_12.txt’)
k = int(f.readline()) # Кол-во мастеров
n = int(f.readline()) # Кол-во клиентов

# Список с записями клиентов по времени
times=[list(map(int, f.readline().split())) for _ in range(n)]

# Массив, в который будут по порядку заноситься номера мастеров
clients = []

# Список с графиком времени каждого специалиста
# Единицей будут помечаться занятые минуты мастера
specialists=[[0]*901 for _ in range(k)]
for start, end in times:
    # Пробегаемся по каждому специалисту,
    # если график свободен для клиента, то добавляем его
    for num in range(k):
        if sum(specialists[num][start:end+1])==0:
            # Добавляем в список номер мастера, к которому обратился клиент
            # (прибавляем единицу, так как нумерация мастеров с единицы, а не с нуля)
            clients.append(num+1)
            # Помечаем занятый период в графике мастера
            for time  in range (start, end+1):
                specialists[num][time]=1
            # Прерываем перебор, так как текущий клиент занял место у мастера
            break
# len(clients) — сколько раз клиенты обращались к мастерам
# clients[-1] — номер последнего мастера, к которому обратились
print(len(clients), clients[-1])

Ответ: 314 10

Ошибка.
Попробуйте повторить позже

Задача 44#63613Максимум баллов за задание: 2

N абитуриентов поступают на некое направление на М мест. Абитуриенты сдали ЕГЭ по трем экзаменам: русскому языку, профильной математике, физики и/или информатике. В зачет идет 3 экзамена. Если сданы и физика, и информатика, то в зачет идёт максимальный балл из двух предметов. Часть выпускников еще не подала оригиналы документов, что отмечено в исходных данных первым полем (0 либо 1). Необходимо определить гарантированно проходной балл.

Входные данные: в первой строке N – кол-во выпускников, M – кол-во мест на направление и далее N строк для каждого абитуриента, в которых первое число 0/1 (отсутствие/наличие оригиналов документов) и далее 3 или 4 оценки: баллы по русскому, профилю, физике и/или информатике.

Выходные данные: проходной балл с учетом наличия оригиналов документов (на момент запроса); проходной балл без учета наличия оригиналов документов (верхняя оценка). Числа в ответе запишите через пробел.

Вложения к задаче

26_14.txt

Показать ответ и решение

f = open(’С:/26_14.txt’)
# n — кол-во абитуриентов, m — кол-во мест на направлении
n,m=map(int, f.readline().split())

# Список с данными об общем балле и наличии оригиналов у каждого абитуриента
a=[]
for i in range(n):
    p,r,ma,*fi=map(int,f.readline().split())
    a.append((r+ma+max(fi),p))
a.sort(reverse=True)
orig = [] # Список абитуриентов с учётом наличия оригиналов
bez = [] # Список без учёта наличия оригиналов

for i in range(len(a)):
    bez.append(a[i][0])
    # Если оригиналы есть, то добавляем в соответствующий список
    if a[i][1] == 1:
        orig.append(a[i][0])
orig.sort(reverse=True)
bez.sort(reverse=True)

# Те же списки, но в них добавляем с учётом ограничения по местам
a1 = []
a2 = []
for i in range(m):
    a2.append(bez[i])
    if i < len(orig):
        a1.append(orig[i])
    else:
        a1.append(bez[len(orig) - i])
print(min(a1), min(a2))

Ответ: 176 231

Ошибка.
Попробуйте повторить позже

Задача 45#63943Максимум баллов за задание: 2

Источник: https://kpolyakov.spb.ru/

В операционном зале есть N банкоматов, работающих круглосуточно. Все банкоматы пронумерованы. В течение дня M клиентов хотят воспользоваться банкоматом. Клиенты обслуживаются в порядке общей очереди. Если в один момент подошли несколько клиентов, то они становятся в очередь в порядке расположения данных в файле. Клиент, стоящий первым в очереди, подходит к первому освободившемуся банкомату (если таких несколько – к банкомату с наименьшим номером). Обслуживание очередного клиента может начаться в ту же минуту, когда банкомат станет свободным. Известно время в минутах от начала суток, когда клиент подошёл к банкомату, и время его обслуживания.

Определите наименьшее количество клиентов, которые были обслужены одним банкоматом за 24 часа, и время начала обслуживания последнего клиента этим банкоматом. Последним обслуженным клиентом считается тот, который подошёл к банкомату до окончания суток (его обслуживание могло закончиться в следующие сутки).

Входные данные

В первой строке входных данных задается два числа: N - количество банкоматов и M – количество клиентов. В каждой из последующих M строк содержится информация по одному клиенту: время начала обслуживания клиента (в минутах с начала суток) и время обслуживания (в минутах).

Выходные данные

Запишите в ответе два числа: наименьшее количество клиентов, которые были обслужены одним банкоматом за 24 часа, и время начала обслуживания последнего клиента этим банкоматом (если таких несколько – банкомата с наименьшим номером).

Пример входного файла:

$2 5$

$1 8$

$6 12$

$8 4$

$8 14$

$8 9$

При таких исходных данных наименьшее число клиентов (2) обслужит 2-й банкомат: это клиенты со временем обслуживания 12 и 8. Последний из них начинает работу с банкоматом на 18-й минуте. Ответ: 2 18.

Вложения к задаче

Задание 25.txt

Показать ответ и решение

Решение 1

with open(’26.txt’) as F:
  N, M = map( int, F.readline().split() )
  data = []
  for _ in range(M):
    t0, delta = map(int, F.readline().split())
    data.append( (t0, delta) )

data.sort( key = lambda x: x[0] )

tFree = [0]*N
stats = [(0,0)]*N

TMAX = 24*60
i = 0
queue = []
for t in range(TMAX):
  while i < len(data) and data[i][0] <= t:
    queue.append( data[i][1] )
    i += 1
  while queue:
    delta, placed = queue[0], False
    for k in range(N):
      if tFree[k] <= t:
        tFree[k] = t + delta
        stats[k] = (stats[k][0]+1, t)
        placed = True
        queue.pop(0)
        break
    if not placed: break

print( *min( stats, key = lambda x: x[0] ) )

Решение 2

f = open(’26.txt’)
n, m = map(int, f.readline().split())
a = [list(map(int, f.readline().split())) for i in range(m)]
a = sorted(a, key = lambda x: x[0])
banks = [-1] * n
banks_start = [-1]*n
cnt_banks = [0] * n
for start, time in a:
    f = 0
    end = start + time
    for j in range(len(banks)):
        if start <= 1440:
            if start >= banks[j]:
                banks[j] = end
                cnt_banks[j] += 1
                f = 1
                banks_start[j] = start
                break
    if f == 0:
        min_t = min(banks)
        if min_t < 1440:
            ind = banks.index(min_t)
            banks[ind] += time
            banks_start[ind] = min_t
            cnt_banks[ind] += 1

print(min(cnt_banks), banks_start[cnt_banks.index(min(cnt_banks))])

Ответ: 75 1438

Ошибка.
Попробуйте повторить позже

Задача 46#63981Максимум баллов за задание: 2

Длительность рабочего дня салона составляет 1000 минут.

Определите сколько клиентов смог записать директор и номер мастера, к которому записался последний клиент.

Вложения к задаче

26_9.txt

Показать ответ и решение

f = open(’C:/26_9.txt’)
k = int(f.readline()) # Кол-во мастеров
n = int(f.readline()) # Кол-во клиентов

# Список с записями клиентов по времени
times = [list(map(int, f.readline().split())) for _ in range(n)]

# Массив, в который будут по порядку заноситься номера мастеров
clients = []

# Список с графиком времени каждого специалиста
# Единицей будут помечаться занятые минуты мастера
specialists = [[0]*1001 for _ in range(k)]

for start, end in times:
    # Пробегаемся по каждому специалисту,
    # если график свободен для клиента, то добавляем его
    for num in range(k):
        if sum(specialists[num][start:end+1])==0:
            # Добавляем в список номер мастера, к которому обратился клиент
            # (прибавляем единицу, так как нумерация мастеров с единицы, а не с нуля)
            clients.append(num+1)
            # Помечаем занятый период в графике мастера
            for time in range(start, end+1):
                specialists[num][time]=1
            # Прерываем перебор, так как текущий клиент занял место у мастера
            break

# len(clients) — сколько раз клиенты обращались к мастерам
# clients[-1] — номер последнего мастера, к которому обратились
print(len(clients), clients[-1])

Ответ: 161 10

Курсы

Всё необходимое для достижения цели

Ошибка.
Попробуйте повторить позже

Задача 47#81228Максимум баллов за задание: 2

Администратор игрового клуба N, работающего с 05:00 до 23:00 заполняет расписание посещений клиентов на завтра. Отсчёт компьютеров начинается с 1. В течении дня клиенты звонили администратору и говорили, в какой период они хотят прийти и на сколько они хотят забронировать компьютер. Если в данный период все компьютеры заняты, то администратор не записывает данного человека в расписание на следующий день. На следующую минуту после освобождения компьютера происходит уборка и проверка оборудования. Данные процедуры длятся 10 минут. На следующую минуту после уборки и проверки следующий клиент может занять данный компьютер.

Входные данные: В первой строке файла находится натуральное число K, не превышающее 5000 – количество клиентов. Во второй строке файла записано натуральное число N – количество компьютеров в игровом клубе. В последующих строках записаны по два числа, не превышающих 1440 в каждой строке: время, когда клиент хочет прийти в игровой клуб и на сколько минут он хочет забронировать компьютер.

Запишите в ответ два числа через пробел: количество клиентов, которые смогли забронировать компьютер и количество человек, которое сидело за 7-ым компьютером.

Вложения к задаче

26_5.txt

Показать ответ и решение

file = open(’26_5__3cjxc.txt’)
count_client = int(file.readline()) #количество клиентов
count_computers = int(file.readline()) #количество компьютеров
array_clients = list(list(map(int,i.split())) for i in file) #считываем время прихода клиента и
                                                             #желаемое время брони

#для каждого компьютера инициализируем нулями все свободное время
computers = [[0 for i in range(1440)] for j in range(count_computers)]
count = [0]*count_computers #количество игроков, сидевших за каждым компьюетром

for start,duration in array_clients: #пробегаемся по списку клиентов
    for i in range(len(computers)): #пробегаемся по списку компьютеров
        #если время прихода клиента попадает в диапазон от 5 утра до 23 вечера и все желаемое время
         #компьютер будет свободен
        if 60*23 >= start + duration and start >= 60 * 5 and sum(computers[i][start:start+duration+12]) == 0:
            #если ни одна минута не занята в протяжении от начала до конца сеанса
            count[i] += 1
            #пробегаемся циклом по только что забронированному времении
            for time in range(start,start+duration+12):
                computers[i][time] = 1 #инициализируем все единицами, то есть помечаем, что занято
            break

print(sum(count),count[6])

Ответ: 215 6

Ошибка.
Попробуйте повторить позже

Задача 48#87925Максимум баллов за задание: 2

На складе требуется разместить $N$ контейнеров различного размера, каждый из которых имеет форму куба. Контейнеры имеют разные цвета, которые обозначаются латинскими буквами. Чтобы сэкономить место, контейнеры вкладывают друг в друга. Один контейнер можно вложить в другой, если выполнены следующие условия:

а) размер стороны внешнего контейнера превышает размер стороны внутреннего на $K$ и более условных единиц.

б) цвета внешнего и внутреннего контейнеров различны. Группу вложенных друг в друга контейнеров называют блоком. Количество контейнеров в блоке может быть любым.

Каждый блок, независимо от количества и размера входящих в него контейнеров, а также каждый одиночный контейнер, не входящий в блоки, занимает при хранении одну складскую ячейку.

Определите минимальное количество ячеек, которые потребуются для хранения всех контейнеров, и количество контейнеров цвета А в блоке с максимальным количеством контейнеров. Если таких блоков несколько, выведите максимальное встреченное в них количество контейнеров цвета А.

При распределении контейнеров по ячейкам пользуются следующим правилом: если два и более контейнеров одинакового размера имеют разные цвета, то их рассматривают в порядке следования латинских букв, обозначающих цвета, в алфавите.

Входные данные:

В первой строке входного файла записано натуральное число $N$ $(1 ≤ N ≤ 30000)$ – количество контейнеров, натуральное число $K$ $(1 ≤ K ≤ 1000)$ – наименьшая допустимая разница размеров вложенных соседних контейнеров

Каждая из следующих $N$ строк содержит натуральное число, не превышающее $10000$ – длину стороны очередного контейнера, и латинскую букву, обозначающую цвет этого контейнера.

Вложения к задаче

26_dif_5.txt

Показать ответ и решение

f = open(’26_dif_5.txt’)

n, k = map(int, f.readline().split())

containers = []
for s in f:
    size, color = s.split()
    containers.append([int(size), color])
# Сортируем по убыванию первого и возрастанию второго элемента.
# Сортировка по возрастанию второго элемента для того,
# чтобы в первую очередь рассматривались контейнеры A.
containers.sort(key=lambda x: (-x[0], x[1]))

# Количество собранных блоков
cnt = 0
# Количество контейнеров цвета А в максимальном блоке
color_A = 0
# Размер максимального блока
mx = 0

while len(containers) > 0:
    cnt += 1
    # Выбранные контейнеры
    chosen = [containers[0]]
    # Не выбранные контейнеры
    not_chosen = []
    # Количество контейнеров А
    A = 1 if containers[0][1] == ’A’ else 0
    for cont in range(1, len(containers)):
        size, color = containers[cont]
        # Если размер предыдущего отличается от размера текущего не менее чем на k
        # А также цвета различны
        if chosen[-1][0] - size >= k and chosen[-1][1] != color:
            chosen.append(containers[cont])
            if color == ’A’:
                A += 1
        else:
            not_chosen.append(containers[cont])

    if len(chosen) > mx:
        mx = len(chosen)
        color_A = A
    elif len(chosen) == mx:
                                                                                                  
                                                                                                  
        color_A = max(color_A, A)

    # Обновляем список, чтобы в нём не было выбранных уже контейнеров
    containers = list(not_chosen)

print(cnt, color_A)

Ответ: 1128 12

Ошибка.
Попробуйте повторить позже

Задача 49#87926Максимум баллов за задание: 2

На кондитерской фабрике имеется N коржей для приготовления тортов, которые накладываются в виде пирамиды. Клиент попросил приготовить на заказ торт-пирамиду максимальной высоты из поставленных друг на друга коржей, такую, чтобы разность диаметра каждого следующего коржа с диаметром предыдущего была четна и составляла более двух единиц.

Определите количество коржей, которое необходимо использовать для создания такого торта, и максимально возможный диаметр коржа, который будет находиться на вершине такого торта-пирамиды.

Входные данные

В первой строке входного файла 26_1.txt находится число N – количество коржей для приготовления торта (натуральное число, не превышающее 1000). В следующих N строках находятся значения диаметров коржей (все числа натуральные, не превышающие 10000), каждое – в отдельной строке.

Запишите в ответе два целых числа: сначала наибольшее количество коржей, которое можно использовать для сборки необходимого торта, затем максимально возможный диаметр самого маленького коржа в таком торте.

Вложения к задаче

26_1.txt

Показать ответ и решение

Откроем текстовый документ, скопируем его и перенесем в столбец А таблицы Excel. Первую строку таблицы можно удалить, она нам не понадобится.

Сортируем столбец А по убыванию. В ячейку B1 копируем значение из ячейки A1. В ячейку B2 вставляем формулу:

=ЕСЛИ(И(ОСТАТ(B1-A2;2)=0;B1-A2>2);A2;B1)

и растягиваем вниз до конца таблицы.

В ячейку C1 вставим 1. В ячейку C2 вставляем формулу:

=ЕСЛИ(B2<>B1;C1+1;C1)

и растягиваем вниз до конца таблицы.

В любую свободную ячейку записываем формулу: =МАКС(C:C). Получаем ответ на первый вопрос: 469.

последнее значение из столбца A, для которого меняется значение в столбцах B и C и будет ответом на второй вопрос: 4.

Ответ: 469 4

Ошибка.
Попробуйте повторить позже

Задача 50#87927Максимум баллов за задание: 2

На кондитерской фабрике имеется N коржей для приготовления тортов, которые накладываются в виде пирамиды. Клиент попросил приготовить на заказ торт-пирамиду максимальной высоты из поставленных друг на друга коржей, такую, чтобы в пирамиде использовались коржи, диаметры которых в партии повторяются, при этом сам корж определенного диаметра используется один раз и выбирается наиболее пышный. Пирамида строится так, чтобы разность диаметра каждого следующего коржа с диаметром предыдущего была положительной.

Определите максимальную высоту торта, которую можно составить и максимально возможный диаметр коржа, который будет находиться на вершине такого торта-пирамиды.

Входные данные

В первой строке входного файла 26_2.txt находится число N – количество коржей для приготовления торта (натуральное число, не превышающее 10000). В следующих N строках находятся два числа: значение диаметра коржа (все числа натуральные, не превышающие 10000) и значение высоты коржа, каждое – в отдельной строке.

Запишите в ответе два целых числа: максимальную высоту торта, которую можно составить, затем максимально возможный диаметр самого маленького коржа в таком торте.

Вложения к задаче

26_2.txt

Показать ответ и решение

Переходим в раздел «Данные», «Текст по столбцам» и разделим первый столбец на два по разделителю «пробел».

Выделим столбцы А и В, перейдем в раздел настраиваемая сортировка и отсортируем сначала столбец А по убыванию, затем столбец В по убыванию.

В ячейку C2 запишем формулу:

=ЕСЛИ(И(A2<>A1;A2=A3);B2;””)

Таким образом мы отсортировали список коржей так, чтобы как минимум два коржа имели одинаковый диаметр, а также высота выбранного коржа была максимальна.

Выделяем столбец С и видим, что сумма по нему равна 186886. Это будет первым ответом.

Спускаемся на самую нижнюю строчку нашего списка и ищем последнюю строку, имеющую в столбце С значение 95. Значит, это последний корж, который находится на верхнем ярусе пирамиды. В столбце А находим его диаметр, он равен 3. Это будет вторым ответом.

Решение (Python)

f = open (’26_2.txt’)
n = f.readline()
cakes = [list(map(int, i.split())) for i in f] # Считываем все строки из файла

cakes = sorted(cakes, key = lambda x: (-x[0], -x[1]))
# Сортируем по убыванию диаметра и убыванию высоты коржа
dm = [i[0] for i in cakes] # Все диаметры коржей
cake_pyramid = [] # Торт - пирамида, который мы составляем

for i in cakes:
# Проверяем, что диаметр текущего коржа встречается в файле больше 1 раза
# Чтобы добавить корж в пирамиду, проверяем, что его диаметр меньше предыдущего
    if dm.count(i[0]) > 1 and (not(cake_pyramid) or (i[0] < cake_pyramid[-1][0])):
        cake_pyramid.append(i)

print(sum(i[1] for i in cake_pyramid)) # Высота торта - пирамиды
print(cake_pyramid[-1][0]) # Диаметр самого маленького коржа в пирамиде

Ответ: 186886 3

Ошибка.
Попробуйте повторить позже

Задача 51#87931Максимум баллов за задание: 2

Система наблюдения ежеминутно фиксирует вход и выход посетителей магазина (в минутах, прошедших от начала суток). Считается, что в моменты фиксации входа и выхода посетитель находится в магазине. Нулевая минута соответствует моменту открытия магазина, который работает 24 ч в сутки без перерыва. Менеджер магазина анализирует данные системы наблюдения за прошедшие сутки, и выявляет отрезки времени наибольшей длины, в течение которых число посетителей, находящихся в магазине, не изменялось. Далее менеджер выбирает пики посещаемости – промежутки времени, когда количество посетителей в магазине было наибольшим. Пиков посещаемости в течение суток может быть несколько.

Входной файл содержит время входа и выхода каждого посетителя магазина. Определите, сколько пиков посещаемости было в течение суток, и укажите число посетителей в момент пика посещаемости. Входные данные представлены в файле 26_6.txt следующим образом. Первая строка входного файла содержит натуральное число N $(1 ≤ N ≤ 10000)$ – количество посетителей магазина. Следующие N строк содержат пары чисел, обозначающих соответственно время входа и время выхода посетителя (все числа натуральные, не превышающие 1440).

Запишите в ответе два натуральных числа: сначала найденное количество пиков посещаемости, а затем число посетителей в момент пика посещаемости.

Примечание: пиком в этой задаче назовём глобальный максимум.

Вложения к задаче

26_6.txt

Показать ответ и решение

f = open(’26_6.txt’)
n = int(f.readline())
stat = [0] * 1441
for i in range(n):
    a, b = map(int, f.readline().split())
    for j in range(a, b + 1):
        stat[j] += 1
print(max(stat))
for i in range(1441):
    # 3716 - число посетителей в пик посещаемости
    if stat[i] != 3716:
        stat[i] = ’ ’
    else:
        stat[i] = ’1’
s = ’’.join(stat)
s = s.split()
print(len(s))

Ответ: 1 3716

Интенсивы

Глубокий разбор тем, требующих дополнительного внимания

Ошибка.
Попробуйте повторить позже

Задача 52#106890Максимум баллов за задание: 2

Во время сессии студенты сдают 4 экзамена, за каждый из которых можно получить от 2 до 5 баллов. Студенты, получившие хотя бы одну «двойку», считаются не сдавшими сессию. Результаты сессии публикуются в виде рейтингового списка, в котором сначала указаны идентификационные номера студентов (ID), сдавших сессию, в порядке убывания среднего балла за сессию, а в случае равенства средних баллов – в порядке возрастания ID. Затем располагаются ID студентов, не сдавших сессию: сначала – получивших одну «двойку», затем – две «двойки», потом ID студентов с тремя «двойками» и, наконец, ID студентов, получивших по 2 балла за каждый из экзаменов. Если студенты имеют одинаковое количество «двоек», то их ID в рейтинге располагаются в порядке возрастания.

Повышенную стипендию получают студенты, занявшие в рейтинговом списке первые 20% мест, при условии отсутствия у них «двоек». Гарантируется, что без «двоек» сессию сдали не менее 20% студентов.

Найдите ID первого в рейтинговом списке студента, не получившего повышенную стипендию, а также ID последнего в рейтинговом списке студента, который имеет одну «двойку».

В ответе запишите два целых положительных числа: сначала ID студента, который занимает первое место среди студентов не получивших повышенную стипендию, затем ID последнего в рейтинговом списке студента, который имеет одну «двойку».

Входные данные

В первой строке входного файла находится число $N$ , обозначающее количество студентов (целое положительное число, не превышающее 10 000). Каждая из следующих $N$ строк содержит 5 чисел через пробел: ID студента (целое положительное число, не превышающее 100 000) и четыре оценки, полученные им за сессию. Гарантируется, что общее число студентов N кратно 5 и хотя бы один студент имеет одну «двойку». Во входном файле все ID различны.

Выходные данные

Два натуральных числа: искомые ID студентов в порядке, указанном в условии задачи.

Типовой пример организации данных во входном файле

4 4 4 4 4

7 5 5 5 2

10 3 4 4 5

1 4 4 4 3

6 3 5 5 3

2 2 2 2 2

13 2 2 2 3

3 3 3 3 3

5 2 4 5 3

15 2 3 3 3

При таких исходных данных рейтинговый список ID имеет вид: 4 6 10 1 3 5 7 15 13 2. Ответ: 10 15.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

Вложения к задаче

26_2.txt

Показать ответ и решение

Решение с помощью электронных таблиц

Скопируем данные из файла в пустую таблицу. Разделим их по столбцам, для этого выделим столбец $A$ , перейдём во вкладку Данные, раздел «Текст по столбцам» и разделим наши данные, указав символом-разделителем пробел. Значение из первой строки (количество студентов) запишем в любом месте таблицы.

Озаглавим колонки, а также добавим еще 2 колонки: «Средний балл» и «Количество двоек», которые дальше пригодятся.

Заполним колонку «Средний балл», для этого в ячейку $F2$ запишем формулу и растянем ее на все строки:

=СРЗНАЧ(B2:E2)

Колонку «Количество двоек» заполним с помощью формулы и так же растянем на все строки:

=СЧЁТЕСЛИ(B2:E2;”=2”)

Дальше сформируем рейтинговый список. Для этого выделяем столбцы $A : G$ и нажимаем на «Сортировка и фильтр» $⇒$ «Пользовательская сортировка».

Первым параметром сортировки указываем «Количество двоек» – по возрастанию, вторым параметром «Средний балл» – по убыванию и третьим «ID» – по возрастанию. Однако, у студентов, не сдавших сессию, рейтинговый список формируется немного иначе – без учета параметра «Средний балл». Поэтому выделяем строки, содержащие студентов, не сдавших сессию, и применяем к ним фильтр снова, удалив этот параметр.

Таким образом мы сформировали рейтинговый список, остается найти в нем ответы на вопросы задачи.

Для ответа на первый вопрос – ID студента, который занимает первое место среди студентов не получивших повышенную стипендию, нужно сначала определить количество студентов получивших повышенную стипендию: $9635⋅0.2 = 1927$ . Тогда ID нужного студента находится в строке 1929. Первый ответ – 9429.

Для ответа на второй вопрос – ID последнего в рейтинговом списке студента, который имеет одну «двойку» отфильтруем данные. Для этого нажимаем «Сортировка и фильтр» $⇒$ «Фильтр», в колонке «Количество двоек» оставим только значение 1. В самой последней строке отфильтрованной таблицы будет значение искомого ID. Второй ответ – 9998.

Решение с помощью программы

Идея решения заключается в том, чтобы сохранять только нужные значения о нужных категориях студентов, а затем просто отфильтровать полученные массивы, чтобы найти в них нужные значения.

f = open("26_2.txt")
n = int(f.readline())

without_2 = [] # массив студентов, которые не получили двоек
with_one_2 = [] # массив студентов, у которых одна двойка

for i in f:
    id, mark1, mark2, mark3, mark4 = map(int, i.split()) # считываем данные со строки файла
    sr = (mark1 + mark2 + mark3 + mark4) / 4 # вычисляем средний балл
    if [mark1, mark2, mark3, mark4].count(2) == 0: # если двоек нет
        without_2.append([id, sr]) # сохраняем в массив студентов, которые не получили двоек
    if [mark1, mark2, mark3, mark4].count(2) == 1:
        with_one_2.append([id]) # сохраняем в массив студентов, у которых одна двойка

# остальных студентов сохранять не обязательно, так как они в любом случае
# будут ниже в рейтинге, а значит не нужны для ответов на вопросы

# сортируем массивы сначала по убыванию среднего балла, а затем по ID
sorted_without_2 = sorted(without_2, key=lambda x: (-x[1], x[0]))
sorted_with_one_2 = sorted(with_one_2, key=lambda x: (x[0]))

# вычисляем количество студентов, которые получили повышенную стипендию
proc = int(n * 0.2)

# выводим нужные данные
print(sorted_without_2[proc][0], sorted_with_one_2[-1][0])

Ответ: 9429 9998

Ошибка.
Попробуйте повторить позже

Задача 53#117808Максимум баллов за задание: 2

Для освещения туристической тропы необходимо установить фонари. Установка фонаря возможна только в заранее определённых точках вдоль тропы — на специальных столбах. Известно расстояние от начала тропы до каждого такого столба.

По техническим требованиям, чтобы избежать перекрытия световых зон и сэкономить электроэнергию, любые два соседних фонаря должны находиться на расстоянии не менее $8$ метров друг от друга.

Администрация заказала установить максимально возможное количество фонарей, не нарушая требований, а также хочет узнать, максимально возможное расстояние от начала тропы до ближайшего установленного фонаря при таком размещении.

Входные данные

В первой строке входного файла находится число $N$ (натуральное, не превышает $10000$ ) — количество столбов, на которые можно установить фонари. В следующих $N$ строках — расстояния (в метрах) от начала тропы до каждого столба (все числа натуральные, не превышающие $10000$ ), каждое в отдельной строке.

Выходные данные

В ответе два целых числа через пробел: максимально возможное количество фонарей и максимально возможное расстояние от начала тропы до ближайшего установленного фонаря при таком размещении.

Пример входного файла:

$6$

$10$

$17$

$26$

$19$

$5$

$30$

При таких исходных данных мы можем установить фанарь на столбы $5$ , $17$ , $26$ или на $30$ , $19$ , $10$ . Максимальное количество фонарей - $3$ , а максимальное расстояние до ближайшего фонаря - $10$ . Ответ: $3$ $10$ .

Вложения к задаче

26_1.txt

Показать ответ и решение

f = open(’26_1.txt’)
n = int(f.readline())
a = [int(f.readline()) for x in range(n)]
a.sort(reverse=True)
b = [a[0]]
for i in range(1,n):
    if b[-1] - a[i] >= 8:
        b.append(a[i])
print(len(b), min(b))

Ответ: 1214 6

Ошибка.
Попробуйте повторить позже

Задача 54#117810Максимум баллов за задание: 2

Для обеспечения безопасности на шоссе устанавливаются камеры видеонаблюдения. Установка возможна только в заранее определённых точках — на мачтах вдоль дороги. Известны расстояния от начала шоссе до каждой мачты.

По нормативам, чтобы камеры не мешали друг другу и не дублировали зоны наблюдения, любые две установленные камеры должны находиться на расстоянии не менее $10$ метров друг от друга.

Необходимо установить максимально возможное количество камер, не нарушая нормативов и определить максимально возможное расстояние от начала шоссе до ближайшей установленной камеры при этом размещении.

Входные данные

В первой строке — число $N$ (натуральное, не больше $10000$ ) — количество мачт. В следующих $N$ строках — расстояния от начала шоссе до каждой мачты (натуральные числа не больше $10000$ ), каждое в отдельной строке.

Выходные данные

Два целых числа через пробел: максимальное количество установленных камер и максимально возможное расстояние от начала шоссе до ближайшей установленной камеры

Пример входного файла:

$8$

$15$

$25$

$5$

$35$

$12$

$45$

$20$

$3$

При таких входных данных мы можем установить камеры на мачты $45$ , $35$ , $25$ , $15$ , $5$ или $2$ , $12$ , $25$ , $35$ , $45$ . Максимальное количество камер - 5, а максимальное расстояние до ближайшей камеры - 5.

Вложения к задаче

26_2.txt

Показать ответ и решение

f = open(’26_2.txt’)
n = int(f.readline())
a = [int(f.readline()) for x in range(n)]
a.sort(reverse=True)
b = [a[0]]
for i in range(1,n):
    if b[-1] - a[i] >= 10:
        b.append(a[i])
print(len(b), min(b))

Ответ: 946 2

Ошибка.
Попробуйте повторить позже

Задача 55#117811Максимум баллов за задание: 2

На складе есть длинная парковочная зона, разделённая на $M$ рядов (пронумерованных от 1 до $M$ сверху вниз) и $K$ мест в каждом ряду (пронумерованных от 1 до $K$ слева направо). Некоторые места уже заняты автомобилями или погрузчиками. Необходимо припарковать грузовик, занимающий 2 места так, чтобы: он стоял как можно дальше от входа (т.е. в ряду с максимальным номером) и над ним (во всех рядах выше в тех же местах) не было других транспортных средств. Если в ряду есть несколько подходящих вариантов, выбрать места с наименьшими номерами.

Входные данные:

Первая строка: $N$ - количество занятых мест, $M$ - ряды, $K$ - места в ряду. Следующие $N$ строк содержат два числа: номер ряда и номер места занятого транспортным средством.

Выходные данные:

Два целых положительных числа через пробел: номер ряда и наименьший номер места, куда можно поставить грузовик.

Пример входного файла:

$5$ $5$ $6$

$1$ $2$

$2$ $3$

$3$ $1$

$3$ $4$

$4$ $3$

Грузовик можно поставить в ряду $5$ на места $5$ и $6$ , условие "над ним пусто"выполняется. Ответ: $5$ $5$ .

Вложения к задаче

26_3.txt

Показать ответ и решение

Решение 1

f = open(’26_3.txt’)
n, m, k = map(int, f.readline().split())
a = sorted([list(map(int, i.split()))[::-1] for i in f])

places = [[] for i in range(k)]
for i in a:
    places[i[0]-1].append(i[1])
for i in range(k):
    if not(places[i]):
        places[i].append(m+1)
mx = x = 0
for i in range(k-1):
    current_min = min(places[i][0], places[i+1][0])
    if current_min > mx:
        mx = current_min
        x = i # Запоминаем индекс места
print(mx - 1, x + 1)

Решение 2

f = open(’26_3.txt’)
n, m, k = [int(x) for x in f.readline().split()]
field = [m+1]*(k+1)
for line in f:
    x, y = [int(i) for i in line.split()]
    field[y] = min(field[y], x)
res = [0, 0]
for i in range(1,k):
    mn = min(field[i], field[i+1]) - 1
    if mn > res[0] and mn > 0:
        res = [mn, i]
    elif mn == res[0] and mn > 0:
        res[1] = min(res[1], i)
print(*res)

Ответ: 57306 1

Ошибка.
Попробуйте повторить позже

Задача 56#119215Максимум баллов за задание: 2

На горном хребте необходимо установить метеостанции для мониторинга погодных условий. Установка возможна только в заранее определённых точках вдоль хребта. Известно расстояние от начала хребта до каждой такой точки. По техническим требованиям, чтобы избежать помех в измерениях, любые две соседние метеостанции должны находиться на расстоянии не менее 12 метров друг от друга. Необходимо установить максимально возможное количество метеостанций и определить максимально возможное расстояние от начала хребта до ближайшей установленной метеостанции при таком размещении.

Входные данные

В первой строке входного файла находится число $N$ (натуральное, не превышает $10000$ ) — количество точек, в которых можно установить метеостанции. В следующих $N$ строках — расстояния (в метрах) от начала хребта до каждой точки (все числа натуральные, не превышающие $10000$ ), каждое в отдельной строке.

Выходные данные

Два целых числа через пробел: максимально возможное количество метеостанций и максимально возможное расстояние от начала хребта до ближайшей установленной метеостанции при таком размещении.

Пример входного файла:

$5$

$10$

$25$

$15$

$5$

$37$

Метеостанции можно установить в точках $37$ , $25$ , $5$ или $25$ , $10$ . Максимальное количество метеостанций — $3$ , а максимальное расстояние до ближайшей метеостанции — $10$ .

Ответ: $3$ $10$ .

Вложения к задаче

26_meteo.txt

Показать ответ и решение

f = open(’26_meteo.txt’)
n = int(f.readline())
a = [int(f.readline()) for x in range(n)]
a.sort(reverse=True)
b = [a[0]]
for i in range(1, n):
    if b[-1] - a[i] >= 12:
        b.append(a[i])
print(len(b), min(b))

Ответ: 775 13

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 57#119216Максимум баллов за задание: 2

На складе есть площадка, разделённая на $M$ рядов (пронумерованных от 1 до $M$ сверху вниз) и $K$ мест в каждом ряду (пронумерованных от 1 до $K$ слева направо). Некоторые места уже заняты другими ящиками. Необходимо разместить новый ящик, занимающий два соседних места в одном ряду, так, чтобы он находился как можно дальше от входа (в ряду с максимальным номером), и в тех же местах во всех рядах выше него не было других ящиков. Если в ряду есть несколько подходящих вариантов, выбрать места с наименьшими номерами.

Входные данные

Первая строка входного файла содержит три числа: $N$ — количество занятых мест ( $N$ — натуральное, не превышает $100 000$ ), $M$ — количество рядов, $K$ — количество мест в ряду. В следующих $N$ строках — по два числа: номер ряда и номер места, занятого ящиком (натуральные числа, не превышающие $M$ и $K$ соответственно).

Выходные данные

Два целых положительных числа через пробел: номер ряда и наименьший номер места, куда можно поставить ящик.

Пример входного файла:

$4$ $5$ $5$

$1$ $1$

$2$ $2$

$3$ $3$

$4$ $4$

Ящик можно поставить в ряду $3$ на места $4$ и $5$ , так как над этими местами нет занятых клеток. Ответ: $3$ $4$ .

Вложения к задаче

26_boxes.txt

Показать ответ и решение

Решение 1

f = open(’26_boxes.txt’)
n, m, k = map(int, f.readline().split())
a = sorted([list(map(int, i.split()))[::-1] for i in f])

places = [[] for i in range(k)]
for i in a:
    places[i[0]-1].append(i[1])
for i in range(k):
    if not(places[i]):
        places[i].append(m+1)
mx = x = 0
for i in range(k-1):
    current_min = min(places[i][0], places[i+1][0])
    if current_min > mx:
        mx = current_min
        x = i # Запоминаем индекс места
print(mx - 1, x + 1)

Решение 2

f = open(’26_boxes.txt’)
n, m, k = [int(x) for x in f.readline().split()]
field = [m + 1] * (k + 1)
for line in f:
    x, y = [int(i) for i in line.split()]
    field[y] = min(field[y], x)
res = [0, 0]
for i in range(1, k):
    mn = min(field[i], field[i + 1]) - 1
    if mn > res[0] and mn > 0 and not (field[i] == mn or field[i + 1] == mn):
        res = [mn, i]
    elif mn == res[0] and mn > 0 and not (field[i] == mn or field[i + 1] == mn):
        res[1] = min(res[1], i)
print(*res)

Ответ: 4033 35

Ошибка.
Попробуйте повторить позже

Задача 58#119217Максимум баллов за задание: 2

На выставочной площадке есть зоны, разделённые на $M$ рядов (пронумерованных от 1 до $M$ сверху вниз) и $K$ мест в каждом ряду (пронумерованных от 1 до $K$ слева направо). Некоторые места уже заняты другими рекламными щитами. Необходимо установить новый щит, занимающий два соседних места в одном ряду, так, чтобы он находился как можно дальше от входа (в ряду с максимальным номером), и в тех же местах во всех рядах выше него не было других щитов. Если в ряду есть несколько подходящих вариантов, выбрать места с наименьшими номерами.

Входные данные

Первая строка входного файла содержит три числа: $N$ — количество занятых мест ( $N$ — натуральное, не превышает $100 000$ ), $M$ — количество рядов, $K$ — количество мест в ряду. В следующих $N$ строках — по два числа: номер ряда и номер места, занятого щитом (натуральные числа, не превышающие $M$ и $K$ соответственно).

Выходные данные

Два целых положительных числа через пробел: номер ряда и наименьший номер места, куда можно поставить щит.

Пример входного файла:

$3$ $4$ $6$

$1$ $2$

$2$ $3$

$3$ $4$

Щит можно поставить в ряду $4$ на места $5$ и $6$ , так как над этими местами нет занятых клеток. Ответ: $4$ $5$ .

Вложения к задаче

26_billboards.txt

Показать ответ и решение

f = open(’26_billboards.txt’)
n, m, k = [int(x) for x in f.readline().split()]
field = [m + 1] * (k + 1)
for line in f:
    x, y = [int(i) for i in line.split()]
    field[y] = min(field[y], x)
res = [0, 0]
for i in range(1, k):
    mn = min(field[i], field[i + 1]) - 1
    if mn > res[0] and mn > 0 and not (field[i] == mn or field[i + 1] == mn):
        res = [mn, i]
    elif mn == res[0] and mn > 0 and not (field[i] == mn or field[i + 1] == mn):
        res[1] = min(res[1], i)
print(*res)

Ответ: 1015 704

Ошибка.
Попробуйте повторить позже

Задача 59#119549Максимум баллов за задание: 2

Входной файл содержит информацию о заказах на использование фотостудии в течение суток. Каждый заказ включает время начала и окончания съёмки (в минутах от начала суток), а также сумму, которую клиент готов заплатить за аренду студии. Съемки можно проводить только со следующей минуты после окончания предыдущей.

Определите максимальный доход, который можно получить за аренду студии, а также общую продолжительность съёмок, которые будут проведены в этом случае. Если максимальный доход можно получить несколькими способами, то в ответ нужно записать минимальную общую продолжительность съёмок, при которой будет получен максимальный доход.

Входные данные

В первой строке файла записано натуральное число $N$ ( $1 ≤ N ≤ 1000$ ) — количество заказов. Каждая из следующих N строк содержит по три числа: время начала, время окончания съёмки (натуральные числа, не превышающие $1440$ ), и сумму оплаты.

Выходные данные

Два числа через пробел: максимальный доход и суммарная продолжительность выбранных съёмок.

Пример входного файла:

$5$

$50$ $100$ $2$

$90$ $130$ $4$

$110$ $140$ $5$

$135$ $180$ $3$

$170$ $210$ $6$

Максимальный доход достигается при выборе заказов $1$ , $3$ , $5$ . Общая продолжительность: $(100− 50 +1) +(140− 110 + 1) + (210 − 170 + 1) = 123$ . Ответ: $13$ $123$ .

Вложения к задаче

26_1.txt

Показать ответ и решение

f = open(’26_1.txt’)
n = int(f.readline()) # Kоличество заявок
# Записываем времена начала, окончания съемок и их стоимость
a = [list(map(int, i.split())) for i in f]
a.sort(key=lambda x:x[1]) # Сортировка по времени окончания съемки
price = [i[2] for i in a] # Cписок стоимостей аренды
tm = [i[1]-i[0]+1 for i in a] # Список длительностей аренды
cnt = [1]*n # Список количества аренд

for i in range(1, n): # Перебираем заявки
    for j in range(i): # Все предыдущие заявки до текущей
    # Если съемка j заканчивается до начала съемки i
        if a[j][1] < a[i][0]:
            # Если сумма оплаты i-й и j-й заявок больше текущей максимальной
            if price[j]+a[i][2] > price[i]:
                # Обновляем максимальную сумму оплаты для i-й заявки
                price[i] = price[j]+a[i][2]
                # Обновляем общую длительность съемок
                tm[i] = tm[j]+a[i][1]-a[i][0] + 1
                # Обновляем количество съемок
                cnt[i] = cnt[j]+1
            elif price[i] == price[j]+a[i][2] and tm[i] > (tm[j]+a[i][1]-a[i][0] + 1):
                tm[i] = tm[j] + a[i][1] - a[i][0] + 1
mx = max(price) # Mаксимальная сумма оплаты за день
print(mx)
for i in range(n):
    if price[i] == mx:
        print(tm[i]) # Длительность всех выбранных съемок

Ответ: 593 971

Ошибка.
Попробуйте повторить позже

Задача 60#119551Максимум баллов за задание: 2

Входной файл содержит сведения о заявках на бронирование помещения для проведения консультаций. Каждая заявка содержит время начала и окончания консультации (в минутах от начала суток), а также сумму, которую готовы заплатить за проведение консультации. Два мероприятия можно провести, если время окончания одного меньше или равно времени начала другого.

Определите максимальную сумму оплаты, которую можно получить за день, а также общую длительность всех выбранных консультаций. Если максимальный доход можно получить несколькими способами, то в ответ нужно записать минимальную общую продолжительность консультаций, при которой будет получен максимальный доход.

Входные данные:

В первой строке входного файла — натуральное число $N$ ( $1 ≤ N ≤ 1000$ ) —количество заявок. В каждой из следующих $N$ строк записаны три числа: время начала и окончания консультации (в минутах от начала суток, от $1$ до $1440$ ) и сумма оплаты.

Выходные данные:

Два числа через пробел: максимальную сумму оплаты за день и суммарную длительность всех выбранных консультаций.

Пример входного файла:

$5$

$10$ $60$ $5$

$60$ $100$ $6$

$110$ $150$ $7$

$160$ $200$ $8$

$100$ $180$ $15$

Максимальный доход достигается при выборе заявок $1$ , $2$ , $5$ . Общая продолжительность: $(60− 10 +1) +(100− 60 + 1)+ (180 − 100 + 1) = 173$ . Ответ: $26$ $173$ .

Вложения к задаче

26_3.txt

Показать ответ и решение

f = open(’26_3.txt’)
n = int(f.readline())
requests = sorted([list(map(int, line.split())) for line in f])
max_profit = [0] * 1441
total_duration = [0] * 1441

for start, end, payment in requests:
    max_prev_profit = max(max_profit[:start + 1])
    time_min = 10 ** 10
    for i in range(start + 1):
        if max_profit[i] == max_prev_profit:
            if total_duration[i] < time_min:
                time_min = total_duration[i]
                time_with_max_profit = i
    new_profit = max_prev_profit + payment
    if new_profit > max_profit[end]:
        max_profit[end] = new_profit
        current_duration = end - start + 1
        total_duration[end] = current_duration + total_duration[time_with_max_profit]
    elif new_profit == max_profit[end]:
        current_duration = end - start + 1
        if current_duration < total_duration[end]:
            total_duration[end] = current_duration + total_duration[time_with_max_profit]
final_profit = max(max_profit)
final_time = total_duration[max_profit.index(final_profit)]
print(final_profit, final_time)

Ответ: 629 969