Олимпиадная задача "Лазеры"

Question

Олимпиадная задача "Лазеры"

Аркадий Паровозов Ученик (59), на голосовании 6 дней назад

Маша учится в школе, но безумно любит посещать открытые лекции в МГТУ им. Н.Э. Баумана. Маша старается всегда использовать своё свободное время максимально продуктивно, потому она заранее скачивает расписание преподавателей, чтобы посетить по лекции минимум 50% преподавателей в день, которые она выбрала.

Преподаватели читают одну и ту же лекцию несколько раз в день, в разные промежутки времени. Но у преподавателей есть негласное правило – можно опоздать на лекцию не больше, чем на 5 минут от начала. Можно уйти с лекции на 5 минут раньше.

Но иногда преподаватели разбросаны по расписанию очень сильно, иногда их время пересекается с другими. Поэтому Маше нужна помощь, чтобы по входному расписанию преподавателей определить, во сколько ей нужно быть в университете, чтобы посетить лекции минимум 50% преподавателей (если преподавателей нечётное количество, то округляем вверх (1 округляется до 1, 3 до 2 и так далее), а также провести минимальное количество времени в ожидании между лекциями (если они не подряд).

Входные данные:
На первой строке подаётся целое число N (1 <= N <= 100) – количество преподавателей, на лекции которых хочет сходить Маша.
Далее подаётся N наборов строк в виде:

на одной строке указывается количество занятий для i-го преподавателя N_i (1 <= N_i <= 50);
на N_i строках далее указываются временные промежутки занятий преподавателя (без самопересечений) в виде hh:mm-hh:mm (например, 09:10-10:15).

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

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

Примечание:

для удобства расчёта считаем, что путь с одной лекции до другой не занимает времени;
время лекции у одного преподавателя всегда одинаковое;
гарантируется, что Маша сможет посетить лекцию минимум 50% преподавателей;
если задача имеет несколько ответов, то вывести тот, при котором Маша приедет как можно раньше;
Маша пытается приехать как можно раньше, поэтому, как только она посетит 50% преподавателей, то она может уезжать домой, но приоритетом в задаче является в первую очередь минимальное время проведённое в ожидании между занятиями.

Входные данные
3
2
10:05-11:50
17:00-18:45
1
11:45-12:30
2
13:00-14:00
16:00-17:00

Выходные данные
10:05
145
0

Маше требуется посетить лекции 50% преподавателей, поэтому достаточно посетить 2 преподавателей. Маша пытается найти самое минимальное время для ожидания между занятиями. В данном случае возможны два варианта, когда Маша проведёт между занятиями 0 минут времени:

посетив лекцию третьего преподавателя 16:00-17:00 и первого 17:00-18:45;
посетив лекцию первого преподавателя 10:05-11:50 и второго 11:45-12:30.

Так как время ожидания между лекциями одинаковое, то выбираем тот вариант, при котором Маша приедет как можно раньше – 10:05.

Answer 1

from datetime import datetime, timedelta

def time_to_minutes(time_str):
return int(time_str[:2]) * 60 + int(time_str[3:])

def minutes_to_time(minutes):
return f"{minutes // 60:02d}:{minutes % 60:02d}"

def parse_time_range(time_range):
start, end = time_range.split('-')
return time_to_minutes(start), time_to_minutes(end)

def solve_problem(schedules):
all_lectures = []
for teacher_schedule in schedules:
for lecture in teacher_schedule:
start, end = parse_time_range(lecture)
all_lectures.append((start, end, schedules.index(teacher_schedule)))

all_lectures.sort()
n = len(schedules)
target = (n + 1) // 2

best_start = None
best_end = None
best_waiting_time = float('inf')
best_lecture_time = 0

for i in range(len(all_lectures)):
visited = set()
current_start = all_lectures[i][0]
current_end = all_lectures[i][1]
visited.add(all_lectures[i][2])
lecture_time = current_end - current_start
waiting_time = 0

for j in range(i + 1, len(all_lectures)):
if len(visited) >= target:
break
if all_lectures[j][2] not in visited:
if all_lectures[j][0] > current_end + 5:
waiting_time += all_lectures[j][0] - current_end - 5
current_end = max(current_end, all_lectures[j][1])
lecture_time += all_lectures[j][1] - all_lectures[j][0]
visited.add(all_lectures[j][2])

if len(visited) >= target:
if waiting_time < best_waiting_time or (waiting_time == best_waiting_time and current_start < best_start):
best_start = current_start
best_end = current_end
best_waiting_time = waiting_time
best_lecture_time = lecture_time

return best_start, best_lecture_time, best_waiting_time

# Входные данные
schedules = [
["10:05-11:50", "17:00-18:45"],
["11:45-12:30"],
["13:00-14:00", "16:00-17:00"]
]

start, lecture_time, waiting_time = solve_problem(schedules)

print
(minutes_to_time(start))
print(lecture_time)
print(waiting_time)

Answer 2

 import datetime 
 
def parse_time(time_str): 
    return datetime.datetime.strptime(time_str, '%H:%M') 
 
def time_to_minutes(time_obj): 
    return time_obj.hour * 60 + time_obj.minute 
 
def solve(): 
    n = int(input()) 
    lectures = [] 
    for _ in range(n): 
        num_lectures = int(input()) 
        teacher_lectures = [] 
        for _ in range(num_lectures): 
            start_time_str, end_time_str = input().split('-') 
            start_time = parse_time(start_time_str) 
            end_time = parse_time(end_time_str) 
            teacher_lectures.append((start_time, end_time)) 
        lectures.append(teacher_lectures) 
 
    min_lectures_needed = (n + 1) // 2 
    min_start_time = None 
    min_total_lecture_time = 0 
    min_waiting_time = float('inf') 
     
     
     
    import itertools 
     
    for combination in itertools.combinations(lectures, min_lectures_needed): 
        all_possible_lectures = [] 
         
        for teacher_lectures in combination: 
          for lecture in teacher_lectures: 
               all_possible_lectures.append((lecture[0] - datetime.timedelta(minutes=5), lecture[1] + datetime.timedelta(minutes=5))) 
        all_possible_lectures.sort() 
         
        for i in range(1 << len(all_possible_lectures)): 
          chosen_lectures = [] 
           
          for j in range(len(all_possible_lectures)): 
             if (i >> j) & 1: 
                chosen_lectures.append(all_possible_lectures[j]) 
           
          if len(chosen_lectures) != min_lectures_needed: 
             continue 
              
           
           
          chosen_lectures.sort(key = lambda x:x[0]) 
           
           
           
           
           
          current_start_time = chosen_lectures[0][0] 
          current_total_lecture_time = 0 
          current_waiting_time = 0 
           
           
           
           
          for k in range(len(chosen_lectures)): 
               
              current_total_lecture_time += time_to_minutes(chosen_lectures[k][1]) - time_to_minutes(chosen_lectures[k][0]) 
               
              if k > 0: 
                  current_waiting_time += max(0,time_to_minutes(chosen_lectures[k][0]) - time_to_minutes(chosen_lectures[k-1][1]) ) 
                   
           
          if min_start_time is None or current_start_time < min_start_time or (current_start_time == min_start_time and current_waiting_time < min_waiting_time): 
             min_start_time = current_start_time 
             min_total_lecture_time = current_total_lecture_time 
             min_waiting_time = current_waiting_time 
 
    print(min_start_time.strftime('%H:%M')) 
    print(min_total_lecture_time) 
    print(min_waiting_time) 
 
 
solve()