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

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

Вспоминай формулы по каждой теме
Решай новые задачи каждый день
Вдумчиво разбирай решения
ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!
Подтемы раздела программирование - обработка целочисленной информации с использованием сортировки
Решаем задачу:

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

Задача 1#18476

Во многих компьютерных системах текущее время хранится в формате «UNIX-время» – количестве секунд от начала суток 1 января 1970 года. В одной компьютерной системе проводили исследование загруженности. Для этого в течение месяца с момента UNIX-времени 1632930743 фиксировали и заносили в базу данных моменты старта и финиша всех процессов, действовавших в этой системе.

Вам необходимо определить, какое наибольшее количество процессов выполнялось в системе одновременно на двух неделях, начавшихся в момент UNIX-времени 1632932743, и в течение какого суммарного времени (в секундах) выполнялось такое наибольшее количество процессов.

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

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

Если в качестве времени старта указан ноль, это означает, что процесс был активен в момент начала исследования. Если в качестве времени завершения указан ноль, это означает, что процесс не завершился к моменту окончания исследования.

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

В ответе запишите два целых числа: сначала максимальное количество процессов, которые выполнялись одновременно на двух неделях, начиная с момента UNIX-времени 1632932743, затем суммарное количество секунд, в течение которых на этих неделях выполнялось такое максимальное количество процессов.

Вложения к задаче
Показать ответ и решение
start = 1632932743  
finish = start + 2 * 7 * 24 * 60 * 60  
file = open("26_3.txt", "r")  
lines = file.readlines()  
n = int(lines[0])  
# Перебираем каждую стоку кроме первой (в которой N) и берем по одному числу из каждой  
start_array = [int(line.split()[0]) for line in lines[1:]]  
finish_array = [int(line.split()[1]) for line in lines[1:]]  
for i in range(len(finish_array)):  
    if finish_array[i] == 0:  
        finish_array[i] = start + 20000000000000000000000000  
 
start_array = sorted(start_array)  
finish_array = sorted(finish_array)  
 
i = 0  
j = 0  
maxim = 0  
k = 0  
 
while i < n and j < n:  
    if start_array[i] < finish_array[j]:  
        k += 1  
        if k > maxim and start_array[i] >= start and start_array[i] < finish:  
            maxim = k  
        i += 1  
    else:  
        k -= 1  
        j += 1  
 
while j < n:  
    k -= 1  
    j += 1  
 
i = 0  
j = 0  
k = 0  
ans_count = 0  
 
for sec in range(start, finish):  
    while i < len(start_array) and start_array[i] <= sec:  
        k += 1  
        i += 1  
    while j < len(finish_array) and finish_array[j] <= sec:  
        k -= 1  
        j += 1  
    if k == maxim:  
        ans_count += 1  
 
print(maxim, ans_count)

Ответ: 51396 43

Специальные программы

Все специальные программы

Программа
лояльности v2.0

Приглашай друзей в Школково и получай вознаграждение до 10%!

Крути рулетку
и выигрывай призы!

Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.

Бесплатное онлайн-обучение

Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.

Налоговые вычеты

Узнай, как получить налоговый вычет при оплате обучения в «Школково».

Специальное предложение
для учителей

Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!

Вернём деньги за курс
за твою сотку на ЕГЭ

Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!

cyberpunkMouse
cyberpunkMouse
Рулетка
Вы можете получить скидку в рулетке!