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

Задания

На грузовом судне необходимо перевезти контейнеры, имеющие одинаковый габарит и разные массы (некоторые контейнеры могут иметь одинаковую массу). Общая масса всех контейнеров превышает грузоподъёмность судна. Количество грузовых мест на судне не меньше количества контейнеров, назначенных к перевозке. Какое максимальное количество контейнеров можно перевезти за один рейс и какова масса самого тяжёлого контейнера среди всех контейнеров, которые можно перевезти за один рейс?

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

Задание 26

В первой строке входного файла находятся два числа: S  — грузоподъёмность судна (натуральное число, не превышающее 100 000) и N  — количество контейнеров (натуральное число, не превышающее 20 000). В следующих N строках находятся значения масс контейнеров, требующих транспортировки (все числа натуральные, не превышающие 100), каждое в отдельной строке.

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

Два целых неотрицательных числа: максимальное количество контейнеров, которые можно перевезти за один рейс и масса наиболее тяжёлого из них.

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

100 4

При таких исходных данных можно транспортировать за один раз максимум два контейнера. Возможные массы этих двух контейнеров  — 30 и 40, 30 и 50 или 40 и 50. Поэтому ответ для приведённого примера: 2 50.

Ответ:

Решение. Сначала считаем в массив данные из файла. После этого отсортируем массив в порядке возрастания. Таким образом, последовательно складывая элементы массива с начала и сравнивая сумму с оставшейся грузоподъёмностью, получим максимальное количество контейнеров, которые можно перевезти. Далее, вычитая из найденной суммы наибольшую массу контейнера в текущей последовательности, будем пробовать прибавлять контейнеры с большей массой. Если такой контейнер будет найден, то заменяем значение контейнера с наибольшей массой, который возможно поместить на судно.

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

var 
i, j, t: integer;
a: array [1..10000] of integer;
s: integer;
n: integer;
sum: integer;
maxi: integer;
f: text;
begin
    assign(f,'C:\26.txt');
    reset(f);
    readln(f, s, n);
    for i := 1 to n do readln(f, a[i]);
    for i := 1 to n do
        for j := i + 1 to n do 
            if a[i] > a[j] then begin
                t := a[i];
                a[i] := a[j];
                a[j] := t;
            end;
    sum := 0;
    maxi := 1;
    for i := 1 to n do
        if sum + a[i] <= s then begin
            sum := sum + a[i];
            maxi := i;
        end;
    t := a[maxi];
    for i := maxi to n do
        if ((sum - t) + a[i]) <= s then begin
            sum := sum - t + a[i];
            t := a[i];
        end;
    writeln(maxi, ' ', t);
end.

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

Ответ: 1612 90.

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

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

f = open('26 (5).txt')

data = f.readlines()

s = data[0].split()

s = int(s[0])

del (data[0]) # первая строка больше не нужна, удаляем ее

for i in range(0, len(data)):

data[i] = int(data[i])

data = sorted(data)

summa = 0

for count in range(0, len(data)):

if summa + data[count] > s: break

summa += data[count]

print(count)

zapas = s - summa

for i in range(0, len(data)):

if data[i] - data[count - 1] <= zapas:

itog = data[i]

print(itog)

Приведём решение Максима Митина (Нижний Новгород) на языке Python.

f = open('26.txt')

l = f.readline()

limit = int(l.split()[0])

n = int(l.split()[1])

a = [int(x) for x in f.readlines()]

a.sort()

ns = 0

k = 0

for i in a:

if ns + i <= limit:

ns += i

k += 1

temp = i

else:

ns -= temp

for j in a:

if ns + j <= limit:

temp = j

else:

break

print(k, temp)

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

s = [i for i in open('26.txt').readlines()]

capacity = int(s[0].split()[0])

containers = [int(i) for i in s[1:]]

selectedContainers = []

containers = sorted(containers)

while (capacity - sum(selectedContainers)) >= containers[0]:

selectedContainers.append(containers[0])

containers.pop(0)

# Получили массив с максимальным количеством самых легких контейнеров

# Теперь нужно определить какой максимальный контейнер может поместиться в последний слот

maxLastContainerCapacity = capacity - sum(selectedContainers[:-1])

biggestContainer = max([container for container in containers if container <= maxLastContainerCapacity])

print(len(selectedContainers), biggestContainer)

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

f = open('26.txt')

s,n = list(map(int,f.readline().split()))

a = sorted([int(x) for x in f])

k = 0

for x in a:

if x > s: break

s -= x

last = x

k += 1

s += last

m = max([x for x in a if x <= s])

print(k,m)

№ п/п	№ задания	Ответ
1	36039	1612 90

Ключ