РЕШУ ЕГЭ — информатика

Задания

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

Определите, какое максимальное количество мероприятий можно провести в конференц-зале и каков при этом максимально возможный перерыв между двумя последними мероприятиями.

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

Задание 26

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

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

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

10 150

100 120

131 170

150 180

120 130

При таких исходных данных можно провести максимум три мероприятия, например, мероприятия по заявкам 2, 3 и 5. максимальный перерыв между двумя последними мероприятиями составит 20 мин., если состоятся мероприятия по заявкам 2, 4 и 5.

Ответ:

Решение. Приведём решение на языке Python.

f = open('0.txt')

n = int(f.readline())

a=[]

for s in f:

start,end=map(int, s.split())

a.append([end, start])

a.sort()

count=[]

z=0

for i in range(n):

if z==0:

z=a[i][0]

count.append(a[i])

last=i

elif z<=a[i][1]:

z=a[i][0]

count.append(a[i])

last=i

del count[-1]

z=count[-1][0]

for i in range (last, n):

if z==0:

z=a[i][0]

count.append(a[i])

elif z<=a[i][1]:

count.append(a[i])

print(len(count), count[-1][1] - count[-2][0])

В результате работы данного алгоритма при вводе данных из файла в условии получаем ответ  — 32  15.

Ответ: 32  15.

Примечание. Путь к файлу необходимо указать согласно расположению файла на Вашем компьютере.

Приведём решение Ильи Крылова на языке Python.

data = open('26_2024.txt').readlines()[1:]

times = []

for item in data:

time = [int(i) for i in item.split()]

times.append(time)

times.sort(key=lambda x: x[1])

selectedTimes = [times[0]]

for time in times[1:]:

if selectedTimes[-1][1] <= time[0]:

selectedTimes.append(time)

selectedLastTime = selectedTimes[-1]

for time in times:

if selectedLastTime[1] <= time[0]:

selectedLastTime = time

print(len(selectedTimes), selectedLastTime[0]-selectedTimes[-2][1])

Приведём решение Евгения Соколова на языке Python.

f = open('26_2024.txt')

f.readline()

a = [list(map(int, s.split())) for s in f]

f.close()

b = []

while len(a) > 0:

a.sort(key = lambda e: e[1])

b.append(a[0])

fin = a[0][1]

a = list(filter(lambda e: e[0] >= fin, a))

print(len(b))

print(b[len(b)-1][0] - b[len(b)-2][1])

Приведём решение Юрия Красильникова на языке Python.

a = sorted([list(map(int,s.split())) for s in open('26_2024.txt')][1:],key=lambda x: x[1])

b = [a[0]]

while True:

c = [x for x in a if x[0]>=b[-1][1]]

if len(c)==0: break

else: b.append(c[0])

print(len(b),max(x[0]-b[-2][1] for x in a))

№ п/п	№ задания	Ответ
1	60268	32 15

Ключ