Статья Автор: Лебедев Дмитрий Алексеевич

Задание 26_Знакомство

Формулировка задачи 95577

Входной файл содержит информацию о заявках граждан в многофункциональный центр (МФЦ) в течение календарных суток. В заявке указаны время начала и время окончания приёма (в минутах от начала суток). Окна специалистов пронумерованы натуральными числами начиная с 1. Приём ведёт свободный специалист в окне с минимальным номером. Новый посетитель может обратиться к освободившемуся специалисту, начиная со следующей минуты после завершения предыдущего приёма. Если в момент обращения свободных специалистов нет, гражданин уходит.

Формат входных данных. В первой строке — число K (K ≤ 1000) окон. Во второй строке — число N (N ≤ 10 000) граждан. Каждая из следующих N строк содержит два натуральных числа (≤ 1440): время начала и время окончания приёма.

Определите, сколько граждан смогут попасть на приём за сутки и каков номер окна специалиста, который начнёт принимать посетителя последним (если таких окон несколько — наименьший номер). В ответе запишите два числа: количество принятых граждан и номер окна.

# Чтение данных
fin = open("26_95577.txt")
K = int(fin.readline())
N = int(fin.readline())
df = [tuple(map(int,fin.readline().split())) for _ in range(N)]
df.sort()
df.append(df[-1])
print(f'{K=} {N=} {len(df)}', df[-5:])
kl_ans = 0
sk = [(0,0)]*(K+1)
for xy in df :
  for i in range(1, K + 1) :
    if sk[i][1] < xy[0] :
      sk[i] = xy
      kl_ans += 1
      break
tm = max([xy for xy in sk])
ans2 = min([i for i in range(1, K+1) if sk[i][0] == tm[0]])
print(kl_ans,ans2)

f = open('26_95577.txt')

K = int(f.readline())
N = int(f.readline()) + 1

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

#print(a[:5])
a.sort()
a.append(a[-1])
w = [0] * (K + 1)

cnt = 0
num = 0
for el in a:

    for i in range(1, K+1):
        if w[i] < el[0]:
            w[i] = el[1]
            cnt += 1
            num = i
            break

print(cnt, num)

Производитель детского питания производит оптовую закупку винограда у фермерских хозяйств региона. Используется виноград двух типов — A и B (светлый и тёмный). На закупку выделена определённая сумма денег.

У фермерских хозяйств каждая партия винограда имеет свою стоимость в рублях. На выделенные деньги необходимо приобрести как можно больше винограда типа A (независимо от партии) и не менее одной партии винограда B. Если виноград A закончится, то на оставшиеся деньги нужно приобрести как можно больше винограда B. Если существует несколько способов закупить максимальное количество винограда, следует выбрать такой, при котором будет приобретено как можно больше винограда A и при этом потрачено наименьшее количество денег.

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

Входные данные. Первая строка входного файла содержит два целых числа: N — общее количество партий винограда и M — сумму денег, выделенную на закупку (в рублях). Каждая из следующих N строк описывает одну партию и содержит целое число (стоимость партии в рублях) и один символ (латинская буква A или B), определяющий тип винограда. Все данные в строках отделены одним пробелом.

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

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

В данном случае можно купить не более четырёх партий винограда, из них не более двух партий типа A. Минимальная цена такой покупки — 110 рублей (партии 10 B, 20 A, 30 B, 50 A). Останется 0 рублей. Ответ: 2 0.

fin = open("26_95467.txt")
N, M = map(int, fin.readline().split())
df = {1 :[] , 2:[]}
for _ in range(N) :
  x, y = fin.readline().split()
  if y == 'A' : df[1].append(int(x))
  else : df[2].append(int(x))
df[1].sort()
df[2].sort()
print(f'{N=} {M=}\n{len(df[1])} {sum(df[1])}\n{len(df[2])} {sum(df[2])}') 
i, j, y = 0, 1, M - df[2][0]
while i < len(df[1]) and y >= df[1][i] :
  y -= df[1][i]
  i +=1 
while j < len(df[2]) and y >= df[2][j] :
  y -= df[2][j]
  j +=1
print(i, y, j)  
#print(sum(df[1][:1539]),sum(df[2][:25]),df[1][1539])

def solve(filename):
    with open(filename, 'r') as f:
        lines = f.readlines()
    
    # Читаем N и M
    n, m = map(int, lines[0].split())
    
    arr_a = []
    arr_b = []
    
    # Распределяем по типам
    for line in lines[1:]:
        if not line.strip():
            continue
        cost, v_type = line.split()
        cost = int(cost)
        if v_type == 'A':
            arr_a.append(cost)
        else:
            arr_b.append(cost)
            
    # Сортируем по возрастанию цены
    arr_a.sort()
    arr_b.sort()
    
    # Шаг 1: Обязательно берем самую дешевую B
    min_b = arr_b[0]
    remaining_b = arr_b[1:]
    
    # Шаг 2: Находим максимальное число партий (жадно)
    # Объединяем всё остальное
    all_others = sorted(arr_a + remaining_b)
    
    current_money = m - min_b
    if current_money < 0:
        return "Денег не хватает даже на одну партию B"
        
    # Списки для отслеживания того, что МЫ КУПИЛИ в жадном решении
    bought_a = []
    bought_b = [min_b]
    
    # Индекс для прохода по остальным элементам
    for cost in all_others:
        if current_money >= cost:
            current_money -= cost
            if cost in arr_a:
                # Чтобы не запутаться с дубликатами цен, проверяем и удаляем аккуратно
                # Но проще распределять по типу. Из all_others мы знаем, откуда пришел элемент.
                # Для точного трекинга сделаем явный перебор:
                pass
                
    # Перепишем жадный набор более строго для учета типов:
    # Создадим пары (цена, тип) для всех остальных
    remaining_elements = sorted([(x, 'A') for x in arr_a] + [(x, 'B') for x in remaining_b], key=lambda item: item[0])
    
    money = m - min_b
    chosen = [ (min_b, 'B') ]
    
    for cost, t in remaining_elements:
        if money >= cost:
            money -= cost
            chosen.append((cost, t))
        else:
            # Нам еще понадобятся НЕ купленные элементы для замен
            break
            
    max_total_packages = len(chosen)
    
    # Шаг 3: Делаем замены, чтобы максимизировать 'A'
    # Разделим купленные на A и B
    bought_A = [x[0] for x in chosen if x[1] == 'A']
    bought_B = [x[0] for x in chosen if x[1] == 'B'] # включая min_b
    
    # Некупленные элементы
    # Чтобы не усложнять, найдем разность мультимножеств
    from collections import Counter
    all_A_counter = Counter(arr_a)
    for x in bought_A:
        all_A_counter[x] -= 1
    not_bought_A = sorted([k for k, v in all_A_counter.items() for _ in range(v)])
    
    # Пытаемся заменить купленные B на некупленные A.
    # Мы не можем трогать последнюю оставшуюся B, если она всего одна!
    # Но у нас в bought_B гарантированно есть как минимум min_b. 
    # Заменять элементы выгодно так: убирать самую дорогую купленную B и брать самую дешевую некупленную A.
    
    bought_B.sort() # от дешевых к дорогим
    
    # Пока у нас есть более чем 1 партия B И есть доступные партии A для покупки
    while len(bought_B) > 1 and len(not_bought_A) > 0:
        # Берем самую дорогую купленную B (в конце списка)
        expensive_b = bought_B[-1]
        # Берем самую дешевую некупленную A
        cheap_a = not_bought_A[0]
        
        # Считаем, сколько у нас будет денег, если мы вернем B и возьмем A
        if money + expensive_b >= cheap_a:
            money = money + expensive_b - cheap_a
            bought_B.pop() # убираем B
            bought_A.append(cheap_a) # добавляем A
            not_bought_A.pop(0) # она больше не доступна
        else:
            # Если даже самую дорогую B нельзя заменить на самую дешевую A, 
            # то дальнейшие замены этой B или на другие A невозможны
            break
            
    # Шаг 4: У нас максимизировано количество A. 
    # Теперь проверим, можно ли сделать "ротацию" купленных A на более дешевые некупленные A, 
    # или купленных B на более дешевые некупленные B, чтобы просто сэкономить деньги (увеличить сдачу)
    # (Обычно жадный алгоритм в начале и так берет самые дешевые, но после замен стоит проверить)
    
    # По условию: "выбрать такой, при котором будет приобретено как можно больше винограда A и при этом потрачено наименьшее количество денег"
    # Наш цикл замен прекратился, когда денег не хватило. Но возможно, было бы выгоднее вернуть чуть менее дорогую B, 
    # если бы на нее хватило? Нет, жадный выбор по разности (expensive_b - cheap_a) оптимален.
    
    # Выводим ответ: количество купленных А и остаток денег
    print(len(bought_A), money)

# Для запуска раскомментируйте строчку ниже, указав имя вашего файла
solve('26_95467.txt')

fin = open("26_95467.txt")
N, M = map(int, fin.readline().split())
df = {1 :[] , 2:[]}
for _ in range(N) :
  x, y = fin.readline().split()
  if y == 'A' : df[1].append(int(x))
  else : df[2].append(int(x))
df[1].sort()
df[2].sort()
print(f'{N=} {M=}\n{len(df[1])} {sum(df[1])}\n{len(df[2])} {sum(df[2])}') 
i, j, y = 0, 1, M - df[2][0]
go = True
while go :
  a, b = df[1][i], df[2][j]
  if y < min(a,b) :
    go = False
  elif a <= b :
    y -= df[1][i]
    i +=1
  else :
    y -= df[2][j]
    j +=1
while y + df[2][j-1] >= df[1][i] :
  j -= 1
  y+= df[2][j]
  y -= df[1][i]
  i+= 1
print(i, y, j)  
#print(sum(df[1][:1539]),sum(df[2][:25]),df[1][1539])

Фермерское хозяйство занимается закупкой винограда у местных поставщиков для производства соков. Используется виноград двух типов: А и В. В процессе закупки работают K сборщиков, которые принимают партии. Сборщики с нечётными номерами принимают толь- ко виноград типа А, сборщики с чётными номерами – только виноград типа В. Нумерация сборщиков начинается с 1.

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

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

Известны общее количество поставщиков N и количество сборщиков K, а также для каждого поставщика: время начала доступности партии, время окончания возможности сдачи, и тип винограда (A или B).

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

fin = open('26_95468.txt')
N, K = map(int, fin.readline().split())
df= [] 
for _ in range(N) : 
  x, y, z = fin.readline().split()
  df.append((int(x), int(y), z))
print(f'{K=} {N=} {len(df)}')
df.sort()
print(df[-5:])
sb = [(0,0)] * (K+1)
rez = []
for ii in range(N):
  x, y, z = df[ii]
  if z == 'A' : j = 1
  else: j = 2
  fl = False
  for i in range(j,K+1,2) :
    if sb[i][1] <= x :
      sb[i] = (x, y + 5)
      fl, s = True, i
      break
  if fl : 
    rez.append((ii+1, s, df[ii]))
print(len(rez))
print( *rez[-12:], sep ='\n')

with open('26_95468.txt') as f:
    n, k = map(int, f.readline().split())
    postavki = []
    for _ in range(n):
        start, end, tip = f.readline().split()
        postavki.append((int(start), int(end), tip))

# обрабатываем в порядке прибытия
postavki.sort(key=lambda x: (x[0],-x[1]))
#postavki.sort()


# svoboden[c] — момент, когда сборщик c снова свободен
svoboden = [0] * (k + 1)     # нумерация с 1

prinyato = 0                 # сколько партий приняли
posledniy = 0                # номер последнего сборщика, принявшего партию

for start, end, tip in postavki:
    # нечётные сборщики -> A, чётные -> B
    nomera = range(1, k + 1, 2) if tip == 'A' else range(2, k + 1, 2)
    for c in nomera:
        if svoboden[c] <= start:        # сборщик свободен к приходу поставщика
            svoboden[c] = end + 5       # занят до конца разгрузки + 5 сек паузы
            prinyato += 1
            posledniy = c
            break                       # партию забрал один сборщик

print(prinyato, posledniy)

Формулировка задачи (КЕГЭ 26 (2026, резерв, ID 95901)
Сервер выполняет запросы на передачу данных, при этом сведения о каждом выполненном запросе (время регистрации, идентификатор клиента, объём переданных данных) сохраняются в журнале работы, а переданные данные - в специальном разделе памяти сервера, имеющем ограниченный объём. Каждый раз, когда остаётся недостаточно свободной памяти, сервер создаёт резервную копию всех накопленных там данных, после чего освобождает раздел и продолжает выполнение запросов. Напишите программу для обработки журнала работы сервера и с её помощью определите наибольший суммарный объём, переданных на сервер с одного клиентского устройства данных, не превышающий 150 000 Кбайт, а также сумму объёмов (в Кбайт) двух последних по времени резервных копий специального раздела, выполненных не позднее 11:59:59.

Входные данные
Первая строка входного файла (журнала работы сервера) содержит два натуральных числа: N(N< 1 000 000) - количество строк в журнале и К (К < 1 000 000) - вместимость специального раздела памяти сервера в Кбайт. Каждая из следующих N строк содержит информацию об одном выполненном запросе: время регистрации запроса в формате ЧЧ:ММ:СС (часы, минуты, секунды), а также два натуральных числа: С (С < 1 000 000) - идентификатор клиентского устройства и S (S < K) - объём данных запроса в Кбайт.

Выходные данные
В ответе запишите два числа: сначала наибольший суммарный объём данных с одного клиентского устройства, не превышающий 150 000 Кбайт, а затем сумму объёмов (в Кбайт) двух последних по времени резервных копий специального раздела, выполненных не позднее 11:59:59.

Типовой пример организации данных во входном файле
8 140000
01:01:01 101 20000
03:03:03 202 110000
05:05:05 101 90000
07:07:07 303 62000
10:10:10 101 48000
15:15:15 202 12000
21:21:21 303 120000
23:23:23 404 134000
При таких исходных данных резервное копирование специального раздела выполняется четыре раза: в5:05:05 (в объёме 130 000 Кбайт), в 07:07:07 (в объёме 90 000 Кбайт), в 21:21:21 (в объёме 122 000 Кбайт) и в 23:23:23 (в объёме 120 000 Кбайт).
Всего на сервер должно быть передано 596 000 Кбайт данных: 158 000, 122 000, 182 000 и 134000 Кбайт от клиента идентификатором 101, 202, 303 404 соответственно. Ответ для приведённого примера: 134 000 220 000.

fin = open('26_22062026.txt')
N, K = map(int, fin.readline().split())
print(f'{N=} {K=}')
df = []
for _ in range(N) :
  t, x, y = fin.readline().split()
  df.append((t, int(x),int(y)))
rez = []
dk = {}
v = 0
for s in df :
  t, x, y = s
  if x in dk : dk[x] += y
  else :  dk[x] = y
  if v + y > K :
    if t < '12:00:00' : rez.append(v)
    v = 0
  v += y
ans1 = max([dk[i] for i in dk if dk[i]<=150000])
ans2 = rez[-2]+rez[-1]
print(ans1,ans2, rez[-3:])

Attached files
26_22062026.txt
26_95467.txt
26_95467_t.txt
26_95468.txt
26_95577.txt

Печать