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

Разбор задания типа 26 из 0-го варианта семестровой

Ежегодно библиотека пополняет свой книжный фонд. На закупку новых книг выделяется определённая сумма, которую нельзя превысить.
На эту сумму библиотеке необходимо закупить максимальное количество книг, среди которых должны быть ровно две редкие книги, одна из которых имеет наименьшую стоимость, а другая - наибольшую, также все энциклопедии.
Известно, что стоимость редких книг превышает 3000 рублей. Стоимость энциклопедий находится в диапазоне от 2000 до 3000 рублей включительно. Стоимость любой другой книги меньше 2000 рублей.
По заданной информации о выделенной сумме на покупку книг и стоимости каждого наименования определите максимальное количество книг, которые может приобрести библиотека, и стоимость самой дорогой книги, не относящейся к категории редких и энциклопедий, при условии, что в итоге будут куплено наибольшее количество книг.

Входные данные:
На вход подается имя файла.

В первой строке входного файла находятся два числа: S - выделенная на покупку книг сумма ( натуральное число, не превышающее 500 000)
и N - количество наименований книг (натуральное число, не превышающее 1000).
В следующих N строках находятся значения стоимости книг каждого наименования (все числа натуральные, не превышающие 5000), каждое в отдельной строке.

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

Пример входного файла	Выходные данные	Пояснение
11000 8 200 3800 3500 500 3100 800 4100 2500	5 800	При таких исходных данных можно приобрести максимум 5 книг: две редкие стоимостью 3100 и 4100, одну энциклопедию за 2500 и две обычных стоимостью 200 и 800.

Для решения задания надо разбить все книги на три группы:

Редкие книги (стоимость больше 3000)
Энциклопедии (стоимость не больше 3000 и не меньше 2000)
Остальные (стоимость менее 2000)

Из группы 1 купить max и min, группу 2 купить целиком, а из 3 группы купить ...

fname = '26_2614.txt' # имя файла с данными
X, Y, Z = [], [], []  # инициализация списков для хранения объектов групп
f = open(fname) # открытие файла и чтение данных
Sm, N = map(int, f.readline().split()) # Чтение параметров обработки
for i in range(N) : # чтение объектов и разнесение их на группы
  a = int(f.readline()) # стоимость очередной книги
  if a < 2000 : Z.append(a) # проверка и занесение в "массовку"
  elif a >3000 : X.append(a) # проверка на "редкость"
  else : Y.append(a) # осталось энциклопедия
f.close() # чтение данных и разбиение на группы завершено
ans_k = 2 # обработка "редких" берем две с мин. и макс. стоимостью
Sm = Sm - min(X) - max(X)
ans_k += len(Y) # обработка энциплопедий - берем все
Sm -= sum(Y)
Z.sort() # сортируем "массовку" в порядке возрастания
i = 0  # указатель на книгу, которую пытаемся купить 
while (i<len(Z)) and (Sm >= Z[i]) : 
  a = Z[i] # стоимость последней купленной книги
  ans_k += 1 # увеличение числа купленных книг
  Sm -= a # уменьшение остатка суммы
  i += 1 # увеличение индекса книги 
# Количество книг определено, "улучшаем" последнюю из "массовки"
b = a # инициализация "улучшения" текущим вариантом
print('Без улучшения:',ans_k, b)  
while (i < len(Z))  and (Sm + a >= Z[i]) : # поиск максимального "улучшения", Sm+a - Капитал на покупку
  b = Z[i] # новый вариант
  i += 1 # сдвиг 
print(ans_k, b)

Блок поиска улучшения может быть написан более эффективно (через "обратную" сортировку с использованием pop и даже с использованием бинарного поиска)

Задания из тренировки 3 (#1)

В проекте «СкупойПлатитДважды» 1 января решено тратить на развитие 60% накоплений всех участников. При этом 20% самых богатых участников вносят 80% от своих накоплений, остальные участники вносят равный процент таким образом, чтобы общая сумма взносов всех участников составила 60%, обозначенные выше.
Запишите в ответе два целых числа: сумма взноса от всех «богатых» участников проекта и сумма взноса участника с самым небольшим размером накоплений. Если в результате получаются дробные числа, нужно записать их целые части.
Входные данные
В первой строке входного файла записано натуральное число N – количество участников проекта (20 ≤ N ≤ 1000).
В следующих N строках находятся значения – размер накоплений всех пользователей (все числа натуральные, не превышающие 1000), каждое в отдельной строке.
Выходные данные
Запишите в ответе два целых числа: сумма взноса от всех «богатых» участников проекта и сумма взноса участника с самым небольшим размером накоплений.
Если в результате получаются дробные числа, нужно записать их целые части. Числа записываются в одну строку через пробел.

Алгоритм решения

Ввод данных
Обработка
Вывод результатов

Реализуем 1 этап, считая, что данные в файле '26-tr301.txt'

def fread(fn) : # подпрограмма чтения данных из файла
  f = open(fn) # открытие файла
  n = int(f.readline()) # чтение числа элементов
  a = []
  for i in range(n): # чтение  n записей
    a.append(int(f.readline()))
  f.close() # закрытие файла
  return a # возврат результатов

data = fread('26-tr301.txt') #чтение данных 
N = len(data)
print(N)

2 этап.
После того, как увидели N можно определить

k_rich = 20% самых богатых
snak - сумму всех накоплени и 60% от неё
s_rich - сумму накоплений 20% богатых
найти сумму которую будут вносить остальные

Вначале данные надо отсортировать. Как? Возьмем стандартную

data = fread('26-tr301.txt') #чтение данных 
N = len(data)
data.sort() # сортировка на месте по возрастанию
k_rich = N//5 # знаем, что число целое
k_poor = N - k_rich
s_rich = sum(data[-k_rich:]) # сум. накопления богатых
s_poor = sum(data[:-k_rich]) # сум. накопления остальных
vz_rich = s_rich*0.8 # cумма взноса богатых
vz_poor = (s_rich+s_poor)*0.6 - vz_rich   # сколько должны внести остальные          
print(vz_rich, (vz_poor,s_poor,k_poor))

Осталось вычислить коэфф. взноса для каждого из остальных, при этом никаких требований на округления нет
kf = vz_ / s_
Выводим ответы (целые части) и kf а %

data = fread('26-tr301.txt') #чтение данных 
N = len(data)
data.sort() # сортировка на месте по возрастанию
k_rich = N//5 # знаем, что число целое
k_poor = N - k_rich
s_rich = sum(data[-k_rich:]) # сум. накопления богатых
s_poor = sum(data[:-k_rich]) # сум. накопления остальных
vz_rich = s_rich*0.8 # cумма взноса богатых
vz_poor = (s_rich+s_poor)*0.6 - vz_rich   # сколько должны внести остальные   
kf = vz_poor/s_poor
print(int(vz_rich), int(data[0]*kf),kf*100)

Задание из тренировки 3 (№3)

Для перевозки партии грузов различной массы выделен грузовик, но его грузоподъёмность ограничена, поэтому перевезти сразу все грузы не удастся. Грузы массой от 180 до 200 кг включительно грузят в первую очередь, выбирая грузы по убыванию массы, начиная с самого тяжёлого. На оставшееся после этого место стараются взять как можно большее количество грузов. Если это можно сделать несколькими способами, выбирают тот способ, при котором самый большой из выбранных грузов имеет наибольшую массу. Если и при этом условии возможно несколько вариантов, выбирается тот, при котором наибольшую массу имеет второй по величине груз, и т.д. Известны количество грузов, масса каждого из них и грузоподъёмность грузовика. Необходимо определить количество и общую массу грузов, которые будут вывезены при погрузке по вышеописанным правилам.

Входные и выходные данные.
На вход подается имя файла.
В первой строке входного файла записаны два целых числа: N – общее количество грузов и M – грузоподъёмность грузовика в кг. Каждая из следующих N строк содержит одно целое число – массу груза в кг. .
Запишите в ответе два числа:максимально возможное количество грузов, затем их общую массу. Числа записываются через пробел.

Алгоритм решения

Ввод данных
Обработка
Вывод результатов

Реализуем 1 этап, считая, что данные в файле '26-tr303.txt'
На этапе считывания можно разбить все грузы на две партии (Gr200 - от 180 до 200 и Gr - остальные, списки проще создать в основной программе)
На этепе 2 : сортируем Gr200 по убыванию, Gr по возрастанию
Вначале набираем из 1-го, затем из 2-го

def fread(fn) : # подпрограмма чтения данных из файла
  f = open(fn) # открытие файла
  n,m = map(int,f.readline().split()) # чтение из 1-й строки
  for i in range(n): # чтение  n записей
    x = int(f.readline())
    if (x-180)*(x-200) > 0 : 
      gr.append(x)
    else : gr200.append(x)
  f.close() # закрытие файла
  return n, m
gr200, gr = [], []
N, M = fread('26-tr303.txt') #чтение данных
print(N,M,(len(gr200),sum(gr200)),(len(gr),sum(gr)))

Видим, что gr200 можно поместить весь,, но сделаем всё "честно"

def otbor(A,m,fl):
  A.sort(reverse = fl)
  k, s = 0, 0 
  while (k < len(A)) and (s + A[k] <= m) : # Есть и можно добавлять
    s += A[k]
    k += 1
  return k,s  
    
gr200, gr = [], []
N, MM = fread('26-tr303.txt') #чтение данных
k1,M1  = otbor(gr200, MM, 1)
k2,M2  = otbor(gr, MM -M1, 0)
print('*',k1+k2, M1+M2)
# убираем последний груз и пытаемся его заменить
i = k2-1 # индекс последнего
x = gr[i] # вес последнего
M0 = MM-M1-M2 # остаток веса, на который можно улучшить
k = 0
while gr[i+k+1]-x <=  M0 :
  k +=1
M2 += gr[i+k] - x
print(k1+k2, M1+M2,k)

Предложенные способы НЕЛЬЗЯ считать эффективными, но для экзамена подходять как ЭЛЕМЕНТАРНЫЕ

Прикрепленные файлы
26-tr301.txt
26-tr303.txt
26_2614.txt

Чтобы оставить комментарий нужна авторизация

Печать