Прочие прототипы —Каталог задач по ЕГЭ - Информатика

Ошибка.
Попробуйте повторить позже

Задача 1#61917

В некотором государстве правительство выделяет $K$ специальностей для обучения студентов. На эти места претендуют $N$ абитуриентов. Для каждой специальности задано количество мест. Для каждого абитуриента известны его баллы и одна выбранная им специальность. Зачисление осуществляется в одну волну. На направление зачисляются абитуриенты с максимальными баллами. Определите максимальный балл поступившего абитуриента на специальность с самым высоким средним баллом и этот средний балл с точностью до двух знаков после запятой.

Входные данные представлены в файле следующим образом. В первой строке через пробел записаны два целых числа $K$ и $N$ . В следующих $K$ строках записано по одному числу – количеством мест по каждой специальности. Следующие $N$ строк содержат пары чисел: баллы студента (до 300 включительно) и код выбранной специальности (начиная с 0).

В ответе запишите два числа: максимальный балл поступившего абитуриента на специальность с самым высоким средним баллом и средний балл такой специальности.

Вложения к задаче

26.txt

Показать ответ и решение

f = open("26.txt")
k, n = [int(i) for i in f.readline().split()]
a = [int(f.readline()) for _ in range(k)]
students = []
for _ in range(n):
    x, y = [int(i) for i in f.readline().split()]
    students.append((y, -x))
students.sort()
res = [[] for _ in range(k)]
for student in students:
    if a[student[0]] > 0:
        a[student[0]] -= 1
        res[student[0]].append(-student[1])
average_score = 0
maxk = 0
for i in range(k):
    if len(res[i]) > 0:
        if sum(res[i]) / len(res[i]) > average_score:
            average_score = sum(res[i]) / len(res[i])
            maxk = max(res[i])
print(maxk, average_score)

Ответ: 300 290.52

Ошибка.
Попробуйте повторить позже

Задача 2#61916

Статград 25.04.23

На парковке имеется $80$ мест для легковых автомобилей и $20$ мест для микроавтобусов. Приезжающий на парковку автомобиль занимает любое свободное место соответствующего типа. При этом если свободных мест для легковых автомобилей нет, то легковой автомобиль занимает свободное место, предназначенное для микроавтобуса, но микроавтобус не может занять место, предназначенное для легкового автомобиля. Если подходящего места нет, автомобиль уезжает.

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

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

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

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

Вложения к задаче

26.txt

Показать ответ и решение

f = open(’26.txt’)
n=int(f.readline())
mesta = [-1] * 100 #0-79 легковые, 80-99 микроавтобусы
a=[]
for i in range(n):
    time,period,type = f.readline().split()
    time,period = int(time), int(period)
    a.append((time,period,type))
a.sort()
count_l=0
count_g=0
for i in range(n):
        time,period,type = a[i]
        if type == ’B’:
            start=80
        else:
            start=0

        for j in range(start,100):
            if time>=mesta[j]:
                mesta[j]=time+period
                if type==’A’:
                    count_l+=1
                else:
                    count_g+=1
                break
print(count_l, n-count_l-count_g)

Ответ: 713 23

Ошибка.
Попробуйте повторить позже

Задача 3#61915

Статград 25.04.23

На парковке имеется $80$ мест для легковых автомобилей и $20$ мест для микроавтобусов. Приезжающий на парковку автомобиль занимает любое свободное место соответствующего типа. При этом если свободных мест для легковых автомобилей нет, то легковой автомобиль занимает свободное место, предназначенное для микроавтобуса, но микроавтобус не может занять место, предназначенное для легкового автомобиля. Если подходящего места нет, автомобиль уезжает.

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

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

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

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

Вложения к задаче

26.txt

Показать ответ и решение

f = open(’26.txt’)
n=int(f.readline())
mesta = [-1] * 100 #0-79 легковые, 80-99 микроавтобусы
a=[]
for i in range(n):
    time,period,type = f.readline().split()
    time,period = int(time), int(period)
    a.append((time,period,type))
a.sort()
count_l=0
count_g=0
for i in range(n):
        time,period,type = a[i]
        if type == ’B’:
            start=80
        else:
            start=0

        for j in range(start,100):
            if time>=mesta[j]:
                mesta[j]=time+period
                if type==’A’:
                    count_l+=1
                else:
                    count_g+=1
                break
print(count_l, n-count_l-count_g)

Ответ: 717 19

Ошибка.
Попробуйте повторить позже

Задача 4#61914

Досрочная волна 2023

В аэропорту есть камера хранения из K ячеек, которые пронумерованы с $1$ . Принимаемый багаж кладется в свободную ячейку с минимальным номером. Известно время, когда пассажиры сдают и забирают багаж (в минутах с начала суток). Ячейка доступна для багажа, начиная со следующей минуты, после окончания срока хранения. Если свободных ячеек не находится, то багаж не принимается в камеру хранения.

Найдите количество багажа, которое будет сдано в камеры за $24$ часа и номер ячейки, в которую сдаст багаж последний пассажир.

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

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

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

Программа должна вывести два числа: количество сданных в камеру хранения багажа и номер ячейки, в которую примут багаж у последнего пассажира, который сможет сдать багаж.

Типовой пример организации данных:

$2$

$5$

$30 60$

$40 60$

$50 1110$

$61 1010$

$1100 1440$

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

Вложения к задаче

26.txt

Показать ответ и решение

f = open(’26.txt’)
k = int(f.readline())
n = int(f.readline())
a=[list(map(int, i.split())) for i in f]
a.sort()
cell=[0]*k
count=0
last=0
for i in range(n):
    for j in range(len(cell)):
        if a[i][0]>cell[j]:
            count+=1
            cell[j]=a[i][1]
            last=j+1
            break
print(count, last)

Ответ: 581 2

Ошибка.
Попробуйте повторить позже

Задача 5#61887

Досрочная волна 2023

В аэропорту есть камера хранения из K ячеек, которые пронумерованы с $1$ . Принимаемый багаж кладется в свободную ячейку с минимальным номером. Известно время, когда пассажиры сдают и забирают багаж (в минутах с начала суток). Ячейка доступна для багажа, начиная со следующей минуты, после окончания срока хранения. Если свободных ячеек не находится, то багаж не принимается в камеру хранения.

Найдите количество багажа, которое будет сдано в камеры за $24$ часа и номер ячейки, в которую сдаст багаж последний пассажир.

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

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

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

Программа должна вывести два числа: количество сданных в камеру хранения багажа и номер ячейки, в которую примут багаж у последнего пассажира, который сможет сдать багаж.

Типовой пример организации данных:

$2$

$5$

$30 60$

$40 60$

$50 1110$

$61 1010$

$1100 1440$

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

Вложения к задаче

26.txt

Показать ответ и решение

f = open(’26.txt’)
k = int(f.readline())
n = int(f.readline())
a=[list(map(int, i.split())) for i in f]
a.sort()
cell=[0]*k
count=0
last=0
for i in range(n):
    for j in range(len(cell)):
        if a[i][0]>cell[j]:
            count+=1
            cell[j]=a[i][1]
            last=j+1
            break
print(count, last)

Ответ: 586 3

Ошибка.
Попробуйте повторить позже

Задача 6#61886

В некотором государстве правительство выделяет $K$ специальностей для обучения студентов. На эти места претендуют $N$ абитуриентов. Для каждой специальности задано количество мест. Для каждого абитуриента известны его баллы и одна выбранная им специальность. Зачисление осуществляется в одну волну. На направление зачисляются абитуриенты с максимальными баллами. Определите максимальный балл поступившего абитуриента на специальность с самым высоким средним баллом и этот средний балл с точностью до двух знаков после запятой.

Входные данные представлены в файле следующим образом. В первой строке через пробел записаны два целых числа $K$ и $N$ . В следующих $K$ строках записано по одному числу – количеством мест по каждой специальности. Следующие $N$ строк содержат пары чисел: баллы студента (до 300 включительно) и код выбранной специальности (начиная с 0).

В ответе запишите два числа: максимальный балл поступившего абитуриента на специальность с самым высоким средним баллом и средний балл такой специальности.

Вложения к задаче

cgtw.txt

Показать ответ и решение

f = open("26.txt")
k, n = [int(i) for i in f.readline().split()]
a = [int(f.readline()) for _ in range(k)]
students = []
for _ in range(n):
    x, y = [int(i) for i in f.readline().split()]
    students.append((y, -x))
students.sort()
res = [[] for _ in range(k)]
for student in students:
    if a[student[0]] > 0:
        a[student[0]] -= 1
        res[student[0]].append(-student[1])
average_score = 0
maxk = 0
for i in range(k):
    if len(res[i]) > 0:
        if sum(res[i]) / len(res[i]) > average_score:
            average_score = sum(res[i]) / len(res[i])
            maxk = max(res[i])
print(maxk, average_score)

Ответ: 292 266.8

Ошибка.
Попробуйте повторить позже

Задача 7#61578

Задание выполняется с использованием прилагаемых файлов.

В аэропорту расположены камеры хранения, состоящие из $K$ ячеек. Ячейки камер хранения пронумерованы, начиная с $1$ . Пассажиры сдают багаж в эти ячейки. Багаж кладётся в свободную ячейку с минимальным номером. Известно время размещения багажа в камеру хранения и время освобождения ячейки в камере хранения (в минутах с начала суток). Багаж достаётся из ячейки в течение минуты. Начиная со следующей минуты, в ячейку можно положить другой багаж. Если все ячейки заняты, то багаж сдать нельзя.

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

В первой строке подается $K$ — число ячеек в камере хранения и $N$ — число пассажиров. На каждой из следующих $N$ строк записаны $2$ числа: время размещения багажа в камере хранения и время освобождения ячейки в камере хранения.

Определите, какое количество багажей сдали в течение суток и номер ячейки, в которую положили последний сданный багаж.

Пример входных данных:

$24 4$

$30 60$

$110 120$

$1000 2000$

$115 133$

Для указанных входных данных ответом будет $4 1$

Вложения к задаче

26-2.txt

Показать ответ и решение

f = open("Zadanie_26__1u832.txt")
k, n = map(int, f.readline().split())
a = []
for i in range(n):
    start, finish = map(int, f.readline().split())
    a.append((start, finish))
counter = 0
m = -1
storage = [-1] * k
a.sort()
for i in range(n):
    start = a[i][0]
    finish = a[i][1]
    for j in range(k):
        if start > storage[j]:
            storage[j] = finish
            counter += 1
            m = j + 1
            break
print(counter, m)

Ответ: 5894 119

Ошибка.
Попробуйте повторить позже

Задача 8#60388

Как известно, во время проведения всетибетской олимпиады по морфемике требуются наблюдатели. Известно, что время начала олимпиады — $begin$ и время окончания — $end$ , то есть время проведения олимпиады — это полуинтервал $[begin,end)$ . Среди студентов вуза, принимающего олимпиаду был составлен список из $N$ студентов-волонтеров, которые смогут наблюдать за учениками и времена $a$ и $b$ , с которого и по которое они смогут проводить наблюдение (полуинтервал $[a,b)$ ).

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

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

В первой строке содержится три натуральных числа — количество наблюдателей $N$ , время начала олимпиады — $begin$ и время окончания — $end$ , то есть время проведения олимпиады — это полуинтервал $[begin,end)$ .

В последующих $N$ строках содержится два числа — $a,b$ , где $a$ — время начала, $b$ — время окончания работы наблюдателя, то есть наблюдатель работает в течение полуинтервала $[a,b)$ .

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

Программа должна вывести в ответе два числа — минимальное количество наблюдателей, которое в состоянии проконтролировать олимпиаду, и время работы первого наблюдателя с момента начала олимпиады.

Пример входных данных:

$5$ $2$ $10$

$1$ $4$

$1$ $3$

$3$ $8$

$7$ $10$

$10$ $11$

Наблюдение полностью обеспечивают наблюдатели, работающие в полуинтервалы $[1,4),[3,8),[7,10)$ . Время работы первого наблюдателя с начала экзамена $4 − 2 = 2$ . Ответ: $3$ $2$

Вложения к задаче

24.txt

Показать ответ и решение

f = open(’27b.txt’)
n, begin, end = map(int, f.readline().split())
data = sorted([[int(i) for i in f.readline().split()] for i in range(n)])
diff = 0
maxim = 0
ans = 0
time = 0

# проходим по списку наблюдателей
for i in range(n):
    # если время начала работы наблюдателя меньше или равно времени начала олимпиады
    if data[i][0] <= begin:
        # и если время окончания работы наблюдателя больше времени начала олимпиады
        if data[i][1] > begin:
            # и если разница между временем окончания работы наблюдателя и временем начала олимпиады больше текущей разницы
            if data[i][1] - begin > diff:
                # обновляем разницу и время окончания работы первого наблюдателя
                diff = data[i][1] - begin
                maxim = data[i][1]
    # если время начала работы наблюдателя больше времени начала олимпиады
    else:
        # и если еще не был назначен ни один наблюдатель
        if ans == 0:
            # вычисляем время работы первого наблюдателя
            time = maxim - begin

        # обновляем начало олимпиады, разницу и количество наблюдателей
        begin = maxim
        diff = 0
        ans += 1

        # если олимпиада закончилась, прерываем цикл
        if maxim >= end:
            break

print(ans, time)

Ответ: 59 290

Ошибка.
Попробуйте повторить позже

Задача 9#59194

Каждую дробь можно представить в виде суммы уникальных единичных дробей (т.е. таких дробей, где в числителе стоит $1$ , а в знаменатале уникальное число). Например, $23 = 12 + 16.$ Такое представление называется египетской дробью, поскольку оно использовалось древними египтянами.

Определите, как можно представить дробь $15 23$ в виде суммы уникальных единичных дробей. В качестве ответа запишите дроби через знак "+". Например, для дроби $23$ в качестве ответа нужно указать $1∕2+ 1∕6$ (В формате: Дробь, пробел, плюс, пробел, дробь).

Показать ответ и решение

def egyptianFraction(nr, dr):
    print("The Egyptian Fraction " +
          "Representation of {0}/{1} is".
          format(nr, dr), end="\n")

    ef = []

    while nr != 0:
        x = dr // nr + (dr % nr != 0)
        ef.append(x)
        nr = x * nr - dr
        dr = dr * x

    for i in range(len(ef)):
        if i != len(ef) - 1:
            print("1/{0} +".format(ef[i]), end=" ")
        else:
            print("1/{0}".format(ef[i]), end="")

egyptianFraction(15, 23)

Ответ: 1/2 + 1/7 + 1/108 + 1/17388

Ошибка.
Попробуйте повторить позже

Задача 10#56735

Задание выполняется с использованием прилагаемых файлов Источник: kpolyakov.spb.ru

Компьютер был заражён вирусами. Супервирусами называются самые опасные вирусы, уровень опасности которых превышает средний уровень опасности всех имеющихся. Нужно определить, какое максимальное количество вирусов можно удалить за заданное время по следующим правилам: - необходимо удалить как можно больше супервирусов; - нельзя удалять два и более супервируса подряд; - нельзя удалять супервирус последним.

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

Первая строка входного файла содержит количество записей N и общее время T, отведённое на удаление этих вирусов. Каждая из следующих N строк содержит два целых числа: уровень опасности вируса и время, которое требуется для его удаления.

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

Запишите в ответе два числа: сначала общее количество вирусов, которое удалось удалить, затем суммарное время, которое было затрачено на удаление супервирусов.

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

5 50

7 13

9 20

4 3

8 9

5 5

Средний уровень опасности равен 6.6, значит, суперопасными считаются вирусы с уровнем опасности >= 7. Удаляем сначала супервирус 8-9, далее обычный вирус 4-3, потом снова суперопасный 7-13, затем обычный 5-5. Обычных вирусов не осталось, значит, суперопасные тоже удалять нельзя. Итого удалено 4 вируса. На удаление супервирусов затрачено времени 9 + 13 = 22. Ответ: 4 22.

Вложения к задаче

26.txt

Показать ответ и решение

Решение 1 ( Excel / LibreOffice):
Откроем текстовый документ, скопируем значения и перенесем их в Excel или LibreOffice.
Перенесем числовые значения количества записей и общее время, отведенное на удаление вирусов, куда-нибудь, где они нам не помешают. Найдем средний уровень опасности вирусов - =СРЗНАЧ(A1:A10000). Суперопасными считаются вирусы с уровнем опасности >= 5004. Для удобства все супервирусы, которые мы выбрали, перенесем в отдельный столбик (столбец C). Удалим столбцы, характеризующие уровень опасности вирусов. Сортируем получившиеся столбцы по возрастанию и начинаем набирать сумму, пока она меньше, чем время, отведенное на удаление. Максимальная сумма, которую мы можем собрать, чтобы не превысить отведенное время, - это 9997173. Выходит, что мы можем удалить 4476 вирусов (2238 вирусов и 2238 супервирусов), время затраченное на удаление супервирусов - 5124042.

Ответ: 4476 5124042

Ошибка.
Попробуйте повторить позже

Задача 11#56722

Источник: kpolyakov.spb.ru

Задание выполняется с использованием прилагаемых файлов

Компьютер был заражён вирусами. Супервирусами называются самые опасные вирусы, уровень опасности которых превышает средний уровень опасности всех имеющихся. Нужно определить, какое максимальное количество вирусов можно удалить за заданное время по следующим правилам: - необходимо удалить как можно больше супервирусов; - нельзя удалять два и более супервируса подряд; - нельзя удалять супервирус последним.

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

Первая строка входного файла содержит количество записей $N$ и общее время $T$ , отведённое на удаление этих вирусов. Каждая из следующих $N$ строк содержит два целых числа: уровень опасности вируса и время, которое требуется для его удаления.

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

Запишите в ответе два числа: сначала общее количество вирусов, которое удалось удалить, затем суммарное время, которое было затрачено на удаление супервирусов.

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

$5 50$

$7 13$

$9 20$

$4 3$

$8 9$

$5 5$

Средний уровень опасности равен $6.6$ , значит, суперопасными считаются вирусы с уровнем опасности >= $7$ . Удаляем сначала супервирус $8− 9$ , далее обычный вирус $4 − 3$ , потом снова суперопасный $7− 13$ , затем обычный $5 − 5$ . Обычных вирусов не осталось, значит, суперопасные тоже удалять нельзя. Итого удалено $4$ вируса. На удаление супервирусов затрачено времени $9+ 13 = 22$ . Ответ: $422$ .

Вложения к задаче

26.txt

Показать ответ и решение

Решение 1 ( Excel / LibreOffice):
Откроем текстовый документ, скопируем значения и перенесем их в Excel или LibreOffice.
Перенесем числовые значения количества записей и общее время, отведенное на удаление вирусов, куда-нибудь, где они нам не помешают. Найдем средний уровень опасности вирусов - =СРЗНАЧ(A1:A10000). Суперопасными считаются вирусы с уровнем опасности >= 4983. Для удобства все супервирусы, которые мы выбрали, перенесем в отдельный столбик (столбец C). Удалим столбцы, характеризующие уровень опасности вирусов. Сортируем получившиеся столбцы по возрастанию и начинаем набирать сумму, пока она меньше, чем время, отведенное на удаление. Максимальная сумма, которую мы можем собрать, чтобы не превысить отведенное время, - это 9993559. Однако,осталось 6441, значит мы можем удалить еще один вирус. Выходит, что мы можем удалить 4499 вирусов (2250 вирусов и 2249 супервирусов), время затраченное на удаление супервирусов - 5005489.

Ответ: 4499 5005489

Ошибка.
Попробуйте повторить позже

Задача 12#56689

Задание выполняется с использованием прилагаемых файлов

Компания по разработке игр открыла набор на работу в офис. На просторах сайта (сайт не уточняется) расположены резюме по поиску работы в сфере разработки игр. Среди них HR-менеджер Петров Влад обязан отобрать только высококвалифицированных и продуктивных программистов, которые смогут справиться со всеми задачами в их компании. При отборе Влад смотрит на КПД (сводка по образованию, опыту работы в данной сфере, качество портфолио). КПД должен составлять более 93 %. Известен КПД каждого соискателя.

По заданной информации о КПД соискателя и о количестве вакантных мест в компании определите максимальное количество потенциальных работников, КПД которых выше 93 %, а также максимальное КПД работника, найденного в таблице при условии, что найдено максимальное количество высококвалифицированных программистов.

В первой строке входного файла находятся два числа: S — количество вакантных мест (натуральное число, не превышающее 1000) и N — количество соискателей (натуральное число, не превышающее 10000). В следующих N строках находятся значения о КПД каждого соискателя (все числа натуральные, удовлетворяющие условию: $1 ≤ X ≤ 100$ ), каждое в отдельной строке

Запишите в ответе два числа: сначала максимальное количество потенциальных работников, КПД которых выше 93 %, а также максимальное КПД работника, найденного в таблице при условии, что найдено максимальное количество высококвалифицированных программистов. Пример входного файла:

5 10

30

97

45

65

89

94

93

95

70

78

При таких исходных данных можно заполнить только 3 вакантных места. Эти люди со следующим КПД: 97, 95, 94. А максимальное КПД соискателя равно 97%. Таким образом, ответ для вышеприведенного примера будет: 3 97.

Вложения к задаче

26.txt

Показать ответ и решение

Решение 1 ( Excel / LibreOffice):

Откроем текстовый документ, скопируем значения и перенесем их в Excel или LibreOffice.
Перенесем числовые значения количества вакантных мест и количества соискателей, где они нам не помешают. Сортируем числа по возрастанию. Выделяем 500 элементов, начиная с первого, числовое значение которого больше 93. Мы получили, что количество вакантных мест больше, чем количество подходящих нам соискателей. Запишем полученное количество подходящих соискателей и элемент, имеющий максимальное числовое значение, в ответ.

Решение 2 (Python):

f = open(’26.txt’)
S, N = map(int, f.readline().split())
a = []
for i in range(N):
    a.append(int(f.readline()))
a.sort(reverse=True)
ans = []
for i in range(S):
    if a[i] > 93:
        ans.append(a[i])
print(len(ans), a[0])

Ответ: 328 100

Ошибка.
Попробуйте повторить позже

Задача 13#56688

У Креветкоеда большая коллекция креветок разных размеров. Каждая креветка имеет размер равный целому числу от $1$ до $N$ (не более $2 ⋅106$ ) включительно. У него есть $Ai$ (каждое не более $103$ ) креветок размера $i$ . Две креветки могут образовать пару, если абсолютное значение разности их размеров составляет не более $1$ . Креветкоед хочет создать максимальное количество пар из своих креветок при условии, что ни одна креветка не должна использоваться в нескольких парах. Найдите максимальное количество пар, которые он может создать и съесть.

В первой строке файла $26.txt$ вам дано число $N$ , а в следующих $N$ строках того же файла $N$ целых чисел $Ai.$

Вложения к задаче

26.txt

Показать ответ и решение

Во-первых, предположим, что не существует такого $i$ , чтобы $Ai = 0$ . В этом случае мы можем доказать, что ответ всегда $S∕∕2$ , где $S$ — общее количество креветок.

Доказательство заключается в следующем. Очевидно, что мы не можем сделать больше, чем $S∕∕2$ пары. С другой стороны, мы можем в явном виде построить $S∕∕2$ пары следующим алгоритмом: Пусть $x1,...,xS$ — все креветки, отсортированные в порядке неубывания. Тогда для каждого $i$ : $xi+1 − xi ≤ 1$ (в противном случае нет креветки с целым числом $xi + 1$ , что является противоречием). Таким образом, мы можем построить $S∕∕2$ пары $(x1,x2),(x3,x4),...$ . Таким образом, мы можем сделать $S∕∕2$ пары.

Когда $Ai = 0$ для некоторого $i$ , вы не можете использовать карты с целым числом $i$ , поэтому вы можете разделить последовательность на $i$ , и для каждой части вы можете решить задачу независимо (ответ — сумма этих независимых задач).

На самом деле можно даже не делать сплит по $0$ . Достаточно лишь посмотреть при рассмотрении креветок размера $i$ , не осталась ли у вас ровно $1$ креветка размера $i− 1$ . Следовательно, вы можете разделить последовательность $Ai$ , по $0$ , и для каждой части вычислить половину (с округлением дробной части в меньшую сторону) суммы, и ответом будет сумма этих чисел. Асимптотика решения $O (N )$ .

Решение на C++

void solve(){
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; ++i){
        cin >> a[i];
    }
    long long ans = 0;
    ans += a[0] / 2; a[0] -= 2 * ans;
    for(int i = 1; i < n; ++i){
        if(a[i - 1] > 0){
            if(a[i] > 0){
                --a[i];
                ++ans;
            }
        }
        ans += a[i] / 2;
        a[i] -= a[i] / 2 * 2;
    }
    cout << ans << ’\n’;
}

Решение на Python

f = open("26.txt")
n = int(f.readline())
a = [int(f.readline()) for _ in range(n)]
ans = 0
for i in range(n - 1):
    if a[i] >= a[i + 1]:
        ans += a[i + 1]
        a[i] -= a[i + 1]
        a[i + 1] = 0
        ans += a[i] // 2
        a[i] = a[i] % 2
    else:
        ans += a[i]
        a[i + 1] -= a[i]
        a[i] = 0
        ans += a[i + 1] // 2
        a[i + 1] = a[i + 1] % 2
print(ans)

Ответ: 24995271

Ошибка.
Попробуйте повторить позже

Задача 14#56687

У вас есть кастрюля и $N$ (не более $50$ ) ингредиентов. Каждый ингредиент имеет параметр вещественного числа, называемый значением, а значение $i$ -го ингредиента $(1 ≤ i ≤ N )$ равно $vi$ (каждое не более $1000$ ). Когда вы положите в кастрюлю два ингредиента, они исчезнут и в результате образуется новый ингредиент. Значение нового ингредиента будет равно $(x+ y)∕2$ , где $x$ и $y$ - значения потребленных ингредиентов, и вы можете снова положить этот ингредиент в кастрюлю. После того, как вы составите ингредиенты таким образом $N − 1$ раз, у вас получится один ингредиент. В ответе запишите максимально возможную ценность этого ингредиента с точностью до сотых. В первой строке файла $26.txt$ находится одно число $N$ . В следующих $N$ строках файла находится массив целых чисел $v$ длины $N$ (длина массива это есть количество содержащихся в нем элементов) по одному элементу в строке.

Вложения к задаче

26.txt

Показать ответ и решение

Для получения ответа работает следующий жадный алгоритм: давайте делать каждый следующий новый ингредиент из двух наименьших по значению ингредиентов. Проделаем эту операцию $N − 1$ раз и получим ответ

Почему это работает? Рассмотрим ситуацию, в которой мы кладем два ингредиента, которые образовались из двух различных наборов ингредиентов: $[v1,v2,v3...,vn]$ и $[u1,u2,u3,...,um]$ со значениями $a$ и $b$ соответственно, и для определенности $a >= b$ . Тогда ценность объединения $(a +b)∕2$ . Тогда если $n > 1$ и $m > 1$ , тогда утверждается, что можно поменять последовательность ходов и собрать новый элемент состоящий из объединения наборов, который будет иметь большую (строго говоря конечно неменьшую) ценность. Давайте просто напросто посмотрим на последнюю операцию из которой получился первый набор $[vi]$ и не будем её делать, получим два каких то элемента. Пусть значения этих элементов $x$ и $y$ , и $x >= y$ . Тогда мы знаем, что $x +y = 2∗ a$ . Теперь у нас есть три элемента со значениями $x,y,b$ . Отсортируем их. Так как $x >= y$ , а $x + y >= 2∗ a$ значит $x >= a >= b$ . Теперь соединим элементы с ценностью $y$ и $b$ , а потом получившийся с элементом со значением $x$ . Итого ценность нового элемента составит $y∕4+ (x+ b)∕2$ вместо $(x +y)∕4+ b∕2$ .

Очевидно, что разница в значениях есть $x∕2$ . Руководствуясь такой логикой можем получить, что каждый ход, это соединение унарного(то есть данного изначально по условию) ингредиента и того, который собран из множества ингредиентов. Тогда чем позже изначальный элемент был смешан, тем на меньшую степень $2$ будет поделена его ценность, поэтому чем больше ценность элемента тем позже его следует добавлять

Решение на Python:

f = open(’26.txt’)
n = int(f.readline())
a = [int(x) for x in f]
a.sort()
ans = a[0]
for i in range(1, n):
    ans = (ans + a[i]) / 2
print(ans)

Ответ: 911.28

Ошибка.
Попробуйте повторить позже

Задача 15#56572

Задание выполняется с использованием прилагаемых файлов

Робот складывает монеты в ящики. Задача робота заполнить как можно большее количество ящиков монетами в количестве 100 штук. Роботу по конвейеру поступают корзины с монетами. В каждой корзине может быть от 1 до 99 монет. Известно, что робот может высыпать в ящик содержимое не более двух корзин. Корзина должна быть высыпана в ящик полностью. Необходимо определить, сколько ящиков можно заполнить монетами так, чтобы в каждом из них было ровно по 100 монет.

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

В первой строке записано число N – количество корзин, в каждой из последующих N строк число K – количество монет в каждой корзине.

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

В ответе запишите одно число – количество ящиков, заполненными 100 монетами.

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

7

10

44

66

90

65

47

34

При таких исходных данных можно заполнить только 2 ящика по 100 монет 10 + 90 и 66 + 34. Ответ: 2.

Вложения к задаче

26.txt

Показать ответ и решение

Решение 1 (Excel/LibreOffice)
Откроем текстовый документ, скопируем значения и перенесем их в Excel или LibreOffice.
Посчитаем корзины с определенным количеством монет, для этого заполним ячейки столбца $B$ цифрами от 1 до 99, и воспользуемся функцией СЧЁТЕСЛИ. Запишем в ячейку $C1$ следующую формулу =СЧЁТЕСЛИ(A1:A10000;B1), скопируем её на свободные клеточки столбца. Для удобства перенесем получившуюся таблицу на новый лист. Разделим данные таблицы на два столбца, перенесем значения $A51$ : $B99$ во второй столбец и воспользуемся настраиваемой сортировкой по убыванию. Посчитаем количество ящиков, которое можно сформировать. Для этого выберем минимум из количества корзин, в которых содержится 1 и 99 монет или 2 и 98 монет и тд. Заметим, что корзина с 50 монетами встречается четное количество раз, значит можно сформировать в два раза меньше ящиков, чем общее количество корзин. Общее количество получившихся ящиков равно 3845.

Решение 2 (Python)

f = open("26.txt")
n=int(f.readline())
array=[int(n) for n in f.readlines()]
array.sort()
counter = 0
for i in range(0, n - 1):
    for j in range(n - 1, i, -1):
        if (array[i] + array[j] == 100 and array[i] != 0 and array[j] != 0):
            counter += 1
            array[j] = 0
            break
print(counter)

Ответ: 3845

Ошибка.
Попробуйте повторить позже

Задача 16#56571

Задание выполняется с использованием прилагаемых файлов

Робот складывает монеты в ящики. Задача робота заполнить как можно большее количество ящиков монетами в количестве $100$ штук. Роботу по конвейеру поступают корзины с монетами. В каждой корзине может быть от $1$ до $99$ монет. Известно, что робот может высыпать в ящик содержимое не более двух корзин. Корзина должна быть высыпана в ящик полностью. Необходимо определить, сколько ящиков можно заполнить монетами так, чтобы в каждом из них было ровно по $100$ монет.

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

В первой строке записано число $N$ – количество корзин, в каждой из последующих $N$ строк число $K$ – количество монет в каждой корзине.

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

В ответе запишите одно число – количество ящиков, заполненными $100$ монетами.

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

$7$

$10$

$44$

$66$

$90$

$65$

$47$

$34$

При таких исходных данных можно заполнить только $2$ ящика по $100$ монет $10$ + $90$ и $66$ + $34$ . Ответ: $2$ .

Вложения к задаче

26.txt

Показать ответ и решение

Решение 1 (Excel/LibreOffice)
Откроем текстовый документ, скопируем значения и перенесем их в Excel или LibreOffice.
Посчитаем корзины с определенным количеством монет, для этого заполним ячейки столбца $B$ цифрами от 1 до 99, и воспользуемся функцией СЧЁТЕСЛИ. Запишем в ячейку $C1$ следующую формулу =СЧЁТЕСЛИ(A1:A10000;B1), скопируем её на свободные клеточки столбца. Для удобства перенесем получившуюся таблицу на новый лист. Разделим данные таблицы на два столбца, перенесем значения $A51$ : $B99$ во второй столбец и воспользуемся настраиваемой сортировкой по убыванию. Посчитаем количество ящиков, которое можно сформировать. Для этого выберем минимум из количества корзин, в которых содержится 1 и 99 монет или 2 и 98 монет и тд. Заметим, что корзина с 50 монетами встречается четное количество раз, значит можно сформировать в два раза меньше ящиков, чем общее количество корзин. Общее количество получившихся ящиков равно 4653.

Решение 2 (Python)

f = open("26.txt")
n=int(f.readline())
array=[int(n) for n in f.readlines()]
array.sort()
counter = 0
for i in range(0, n - 1):
    for j in range(n - 1, i, -1):
        if (array[i] + array[j] == 100 and array[i] != 0 and array[j] != 0):
            counter += 1
            array[j] = 0
            break
print(counter)

Ответ: 4653

Ошибка.
Попробуйте повторить позже

Задача 17#56550

На закупку товаров типов A, B, C, D и E выделена определённая сумма денег. Эти товары есть в продаже по различной цене. Необходимо на выделенную сумму закупить как можно больше товаров пяти типов (по общему количеству). Если можно разными способами купить максимальное количество пяти типов товаров, то нужно выбрать способ, при котором будет закуплено как можно больше товаров типа A. Если при этих условиях есть несколько способов закупки, нужно потратить как можно меньше денег. Определите, сколько будет закуплено товаров типа A и сколько денег останется.
Входные данные представлены в файле 5.txt следующим образом. Первая строка входного файла содержит два целых числа: N – общее количество товаров и M – сумма выделенных на закупку денег (в рублях). Каждая из следующих N строк содержит целое число (цена товара в рублях) и символ (латинская буква), определяющий тип товара. Все данные в строках входного файла отделены одним пробелом.
Запишите в ответе два числа: сначала количество закупленных товаров типа A, затем оставшуюся неиспользованной сумму денег. Пример входного файла:
6 110
40 E
50 A
50 D
30 C
20 B
10 A
В данном случае можно купить не более четырёх товаров, из них не более двух товаров типа A. Минимальная цена такой покупки 100 рублей (покупаем товары 10 A, 20 B, 30 C, 50 A). Останется 0 рублей. Ответ: 2 0.

Вложения к задаче

26.txt

Показать ответ и решение

Откроем текстовый документ, скопируем значения и перенесем их в Excel или LibreOffice.
Перенесем числовые значения количества товаров и суммы денег, где они нам не помешают (ячейки $F2$ и $G2$ ). Сортируем числа по первому столбцу по возрастанию. Выбираем 95 элементов (их общая сумма меньше 100000, то есть это максимальное количество товаров, которые мы сможем купить). Для удобства все элементы, которые мы выбрали, перенесем в отдельный столбик (столбец $C$ ). Найдём разницу между суммой денег, выделенной на закупку, и текущей суммы товаров (ячейка $G6$ ). Будем убирать из текущей суммы (столбец $C$ ) товары типов $B,C, D$ с максимальной стоимостью и добавлять ещё не выбранные товары типа А с минимальной стоимостью до тех пор, пока наша сумма не превысит 100000 В ячейке $F 9$ посчитаем общее количество выбранные товаров типа А, в ячейке $G6$ - оставшуюся неиспользованную сумму денег. Запишем ответ.

Ответ: 32 64

Ошибка.
Попробуйте повторить позже

Задача 18#56377

Для уменьшения аварий на центральной дороге в городе X дорожная служба решила выровнять ямы. Размер объем (в литрах) новой ямы вычисляется как наименьшее значение среди объёмов самой этой ямы и двух соседних перед выравниванием. При этом размеры первой и последней ямы решили не менять.

Ночью перед ремонтом дороги в городе X прошел проливной дождь, поэтому все ямы до краев заполнены водой. Сколько литров воды выльется обратно на дорогу после проведения ремонта?

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

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

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

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

$8$

$10$

$12$

$8$

$6$

$20$

$12$

$16$

$10$

При таких исходных данных после ремонта объем ям будет выглядеть следующим образом $10$ , $8$ , $6$ , $6$ , $6$ , $12$ , $10$ , $10$ . В ответе необходимо указать два числа – $3$ и $26$ .

Вложения к задаче

26.txt

Показать ответ и решение

file = open("26.txt")

n = int(file.readline())
a = [int(file.readline()) for _ in range(n)]
a_new = []

for i in range(1, len(a) - 1):
    a_new.append(min(a[i - 1], a[i], a[i + 1]))
a = a[1:len(a) - 1]

print(a_new.count(min(a_new)), sum(a) - sum(a_new))

Ответ: 3 24766730

Ошибка.
Попробуйте повторить позже

Задача 19#56330

На кондитерской фабрике есть n видов пирожных, i-го вида на фабрике $ai$ штук. Было принято решение отвезти пирожные на продажу на ярмарку, но директор фабрики решил, что кондитерские изделия на ярмарочной витрине должны быть выложены одинаковыми рядами, при этом пирожных каждого вида должно быть одинаковое количество. Необязательно отвозить на ярмарку все виды пирожных, можно выбрать некоторые виды и взять одинаковое число пирожных каждого выбранного вида.

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

Формат входных данных

Первая строка входных данных содержит число n — количество видов пирожных на фабрике, $1 ≤ n ≤ 105$ . Следующие n строк содержат по одному числу $ai$ — количество пирожных i-го вида, $5 1 ≤ ai ≤ 10$ . Сумма всех значений $ai$ не превосходит $2⋅109$ .

Формат выходных данных

Программа должна вывести два целых числа. Первое число равно количеству видов пирожных, которые необходимо выбрать для ярмарки. Второе число равно количеству пирожных каждого выбранного вида, которые нужно отвезти на ярмарку.

Если возможных ответов несколько, выведите любой из них.

Пример:

3

4

10

7

Ответом для примера будет: 2 7.

Рассмотрим пример из условия. Имеется 3 вида пирожных количеством 4, 10 и 7 штук. Наилучшим вариантом будет взять по 7 пирожных второго и третьего вида.

Вложения к задаче

26.txt

Показать ответ и решение

n = int(input())
a = [int(input()) for i in range(n)]
count = [0]*100000

for i in a:
    count[i] += 1

ans_s = 0
ans_k = 0
k = 0
for i in range(100000-1, -1, -1):
    k += count[i]
    if k * i > ans_k * ans_s:
        ans_k = k
        ans_s = i
print(ans_k, ans_s)

Ответ: 2461 1279

Ошибка.
Попробуйте повторить позже

Задача 20#55464

Дано число $N$ , затем $N$ строк. В каждой из строк находится одна десятичная цифра. Составьте наибольшее и наименьшее число из всех этих цифр. В ответе укажите остаток разности наибольшего и наименьшего из этих чисел при делении на $10000$ .

Вложения к задаче

26.txt

Показать ответ и решение

f = open(’26.txt’)

n = int(f.readline())

a = []
for i in range(n):
    a.append(int(f.readline()))

a = sorted(a)

maxim = ’’
minim = ’’

for i in range(n):
    minim += str(a[i])
    maxim += str(a[n - 1 - i])

print((int(maxim) - int(minim)) % 10000)

Ответ: 1