Тема 26. Обработка целочисленной информации с использованием сортировки

26.09 Прочие прототипы

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела обработка целочисленной информации с использованием сортировки

Решаем задачи

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

Задача 1#23513

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

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

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

В первой строке входного файла 26.txt находятся три числа, записанные через пробел: $N$ — общее количество результатов учащихся (натуральное число, не превышающее $10000$ ), $K$ — количество победителей, $M$ — количество призёров. В следующих $N$ строках находятся значения каждого из результатов (все числа натуральные, не превышающие $10000$ ), каждое в отдельной строке. Запишите в ответе два числа: сначала максимальный балл призёра, а затем минимальный балл победителя данной олимпиады.

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

$6 2 3$

$7589$

$6344$

$8590$

$6231$

$3159$

$5462$

При таких исходных данных ответ должен содержать $2$ числа — $6344$ и $7589$ . Пояснение: победители набрали $7589$ и $8590$ балла, призёры набрали $6344$ , $6231$ , $5462$ баллов. Тогда максимальный балл призёра $6344$ , а минимальный балл победителя — $7589$ .

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

Задание_26__ktct.txt

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

Решение 1 ( Excel / LibreOffice):
Откроем текстовый документ, скопируем значения и перенесем их в Excel или LibreOffice.
Перенесём числовые значения общего количества результатов учащихся, количества победителей и призёров туда, где они нам не помешают. Сортируем по убыванию. Сначала выбираем первые 289 ячеек, соответствующих количеству победителей, выписываем последнее (минимальное) значение балла победителя, затем 691 ячейку, соответствующую количеству призёров, выписываем первое (максимальное) значение балла призёра. Выписанные значения и являются ответом.

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

f = open(’Задание_26__ktct.txt’)
n, k, m = [int(s) for s in f.readline().split()]
a = sorted([int(s) for s in f], reverse=True)
ans1 = 0
ans2 = 10000000000000
for i in range(n):
    if i < k:
        ans2 = min(ans2, a[i])
    else:
        ans1 = max(ans1, a[i])
print(ans1, ans2)

Ответ: 9688 9688

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

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

Задача 2#25624

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

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

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

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

6 2 3

589

344

590

231

159

462

При таких исходных данных ответ должен содержать $2$ числа — $462$ и $589$ . Пояснение: победители набрали $589$ и $590$ балла, призёры набрали $344$ , $231$ , $462$ баллов. Тогда максимальный балл призёра $462$ , а минимальный балл победителя — $589$ .

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

Задание_26__cke1.txt

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

Решение 1 ( Excel / LibreOffice):
Откроем текстовый документ, скопируем значения и перенесем их в Excel или LibreOffice.
Перенесём числовые значения общего количества результатов учащихся, количества победителей и призёров туда, где они нам не помешают. Сортируем по убыванию. Сначала выбираем первые 40 ячеек, соответствующих количеству победителей, выписываем последнее (минимальное) значение балла победителя, затем 140 ячеек, соответствующих количеству призёров, выписываем первое (максимальное) значение балла призёра. Выписанные значения и являются ответом.

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

f = open(’Задание_26__cke1.txt’)
n, m, k = map(int, f.readline().split())
a = []
for i in range(n):
    a.append(int(f.readline()))
a.sort(reverse=True)
x = []
y = []
for i in range(m):
    x.append(a[i])
for i in range(m, m+k):
    y.append(a[i])
print(min(x), max(y))

Ответ: 994 994

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

Задача 3#25999

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

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

Входные и выходные данные. В первой строке входного файла 26.txt находятся три числа, записанные через пробел: $N$ — общее количество результатов учащихся (натуральное число, не превышающее $30000$ ), $K$ — количество победителей, $M$ — количество призёров. В следующих $N$ строках находятся значения каждого из результатов (все числа натуральные, не превышающие $1000$ ), каждое в отдельной строке. Запишите в ответе одно число взятое по модулю: разность суммы баллов победителей и призёров данной олимпиады.

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

$6 1 2$

$853$

$752$

$156$

$652$

$432$

$184$

При таких исходных данных ответ должен содержать $551$ . Пояснение: победитель набрал $853$ балла, призёры набрали $752$ и $652$ баллов. Тогда взятые по модулю разность суммы баллов победителей и призёров равны: $|853− 1404| = 551$ .

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

Задание_26__g57w.txt

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

Решение 1 ( Excel / LibreOffice):
Откроем текстовый документ, скопируем значения и перенесем их в Excel или LibreOffice.
Перенесём числовые значения общего количества результатов учащихся, количества победителей и призёров туда, где они нам не помешают. Сортируем по убыванию. Сначала выбираем первые 150 ячеек, соответствующих количеству победителей, считаем их сумму, затем 765 ячеек, соответствующих количеству призёров, определяем их сумму. Находим модуль разности полученных значений: |149659 - 748812| = 599153

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

f = open(’Задание_26__g57w.txt’)
n, k, m = map(int, f.readline().split())
a = []
for i in range(n):
    a.append(int(f.readline()))
a.sort(reverse=True)
ans1 = 0
for i in range(k):
    ans1 += a[i]
ans2 = 0
for i in range(k, k+m):
    ans2 += a[i]
print(abs(ans1-ans2))

Ответ: 599153

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

Задача 4#26132

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

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

Входные и выходные данные. В первой строке входного файла 26.txt находятся три числа, записанные через пробел: $N$ — общее количество результатов учащихся (натуральное число, не превышающее $30 000$ ), $W$ — количество победителей, $M$ — количество призёров. В следующих $N$ строках находятся значения каждого из результатов (все числа натуральные, не превышающие $1000$ ), каждое в отдельной строке. Запишите в ответе одно число взятое по модулю: разность суммы баллов победителей и призёров данной олимпиады.

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

$6 1 2$

$984$

$631$

$125$

$527$

$251$

$353$

При таких исходных данных ответ должен содержать $174$ . Пояснение: победитель набрал $984$ балла, призёры набрали $631$ и $527$ баллов. Тогда взятые по модулю разность суммы баллов победителей и призёров равны: $|984− 1158| = 174.$

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

Задание_26__hi6x__swy8.txt

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

Решение 1 ( Excel / LibreOffice):
Откроем текстовый документ, скопируем значения и перенесем их в Excel или LibreOffice.
Перенесём числовые значения общего количества результатов учащихся, количества победителей и призёров туда, где они нам не помешают. Сортируем по убыванию. Сначала выбираем первые 743 ячейки, соответствующих количеству победителей, считаем их сумму, затем 1358 ячеек, соответствующих количеству призёров, определяем их сумму. Находим модуль разности полученных значений: |717318 - 1168636| = 451318

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

file = open(’Задание_26__hi6x__swy8.txt’)
n, w, m = [int(i) for i in file.readline().split()]

mass = [int(file.readline()) for i in range(n)]
mass.sort(reverse=True)

sum_w = sum(mass[0:w])
sum_m = sum(mass[w:m + w])

print(abs(sum_w - sum_m))

Ответ: 451318

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

Задача 5#26186

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

По итогам проведения олимпиады по программированию каждый участник получил определённое количество баллов. По регламенту олимпиады победителя присуждают W лучших участников, а призёра присуждают M лучших участников, следующих за ними. По заданной информации о результатах каждого из участников определите значение выражения: (сумма баллов призёров - сумма баллов победителей) - $712$ .

Входные и выходные данные. В первой строке входного файла ’26.txt’ находятся три числа, записанные через пробел: $N$ – общее количество результатов учащихся (натуральное число, не превышающее $30000$ ), $W$ – количество победителей, $M$ – количество призёров. В следующих N строках находятся значения каждого из результатов (все числа натуральные, не превышающие $1000$ ), каждое в отдельной строке. Запишите в ответе одно число: (сумма баллов призёров - сумма баллов победителей) - $712$ .

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

$6 1 2$

$847$

$574$

$63$

$609$

$147$

$498$

При таких исходных данных ответ должен содержать - $376$ . Пояснение: победитель набрал $847$ балла, призёры набрали $574$ и $609$ баллов. Тогда разность сумм баллов призёров и победителей равны: $1183− 847 = 336.$ Уменьшив ответ на $712$ , получаем: $336− 712 = − 376$ .

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

Задание_26__iob8.txt

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

Решение 1 ( Excel / LibreOffice):
Откроем текстовый документ, скопируем значения и перенесем их в Excel или LibreOffice.
Перенесём числовые значения общего количества результатов учащихся, количества победителей и призёров туда, где они нам не помешают. Сортируем по убыванию. Сначала выбираем первые 666 ячеек, соответствующих количеству победителей, считаем их сумму, затем 696 ячеек, соответствующих количеству призёров, определяем их сумму. Находим по формуле из условия значение выражения: 649580 - 650392 - 712 = -1524

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

f = open(’Задание_26__iob8.txt’)
n, w, m = map(int, f.readline().split())
a = []
for i in range(n):
    a.append(int(f.readline()))
a.sort(reverse=True)
sum_priz = 0
sum_pob = 0
for i in range(w):
    sum_pob += a[i]
for i in range(w, w+m):
    sum_priz += a[i]
print(sum_priz - sum_pob - 712)

Ответ: -1524

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

Задача 6#30260

На закупку товаров типов 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.

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

5.txt

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

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

Ответ: 35 44

Курсы

Всё необходимое для достижения цели

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

Задача 7#49309

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

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

Входные данные: файл 2.txt

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

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

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

2.txt

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


f = open(’2.txt’)
n = f.readline()
boxes = sorted([int(i) for i in f], reverse=True)
ans = [boxes[0]]
for box in boxes[1:]:
    if ans[-1] - box >= 4:
        ans.append(box)
print(len(ans), ans[-1])

Ответ: 2172 50

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

Задача 8#49512

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

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

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

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

1.txt

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

f = open("1.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)

Ответ: 299 274.48

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

Задача 9#50439

Спутник «Фотон» проводит измерения солнечной активности, результат каждого измерения представляет собой натуральное число. Перед обработкой серии измерений из неё исключают K наибольших и K наименьших значений (как недостоверные). По заданной информации о значении каждого из измерений, а также количестве исключаемых значений, определите наибольшее достоверное измерение, а также целую часть среднего значения всех достоверных измерений.
Входные и выходные данные. В первой строке входного файла 3.txt находятся два числа, записанные через пробел: N – общее количество измерений (натуральное число, не превышающее 10 000) и K – количество исключаемых минимальных и максимальных значений. В следующих N строках находятся значения каждого из измерений (все числа натуральные, не превышающие 1000), каждое в отдельной строке. Запишите в ответе без пробелов два числа: сначала наибольшее достоверное измерение, а затем целую часть среднего значения всех достоверных измерений.
Пример входного файла:
10 2
34
50
43
44
23
9
39
5
38
36
При таких исходных данных ответ должен содержать 2 числа – 43 и 35. Пояснение: будут отброшены значения 5, 9, 44, 50. Тогда наибольшее оставшееся значение равно 43, а среднее значение из оставшихся равно (23+34+36+38+39+43):6 = 35,5.

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

26_3.txt

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

500 - общее количество измерений, 47 - исключаемые минимальные и максимальные значения. Копируется столбец данных в Excel и сортируется по возрастанию. Так как первые 47 измерений удаляются, то тогда наименьшее достоверное значение будет стоять в ячейке А48, а наибольшее в ячейке А453 (значения отсортированы).

$PIC$

Так как удаляются 47 самых больших и маленьких значения, то найдем среднее значение в диапазоне А48:A453

$PIC$

Таким образом, ответ 899 507.

Ответ: 899507

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

Задача 10#50440

По итогам проведения олимпиады по программированию каждый участник получил определённое количество баллов, различное для каждого ученика. По регламенту олимпиады победителя присуждают K лучшим участникам, а призёра присуждают M лучшим участникам, следующим за последним победителем. По заданной информации о результатах каждого из участников определите минимальный балл победителя и максимальный балл участника, не ставшего призером.
Входные и выходные данные. В первой строке входного файла 4.txt находятся три числа, записанные через пробел: N – общее количество результатов учащихся (натуральное число, не превышающее 10 000), K – количество победителей, M – количество призёров. В следующих N строках находятся значения каждого из результатов (все числа натуральные, не превышающие 1000), каждое в отдельной строке. Запишите в ответе без пробелов два числа: сначала минимальный балл победителя, а затем максимальный балл участника, не ставшего призером.
Пример входного файла:
10 2 4
244
39
213
108
132
18
46
52
242
179
При таких исходных данных ответ должен содержать 2 числа – 242 и 52. Пояснение: победители набрали 244 и 242 балла, призёры набрали 213, 179, 132, 108 баллов. Тогда минимальный балл победителя 242, а максимальный балл участника, не ставшего призером – 52.

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

26_4.txt

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

Количество победителей 10, количество призеров - 35. Копируем столбец с результатами олимпиады в Excel и сортируем по убыванию. Тогда минимальный балл победителя находится в ячейке А10 = 993. А максимальный балл участника в ячейке А46 = 950 (первые 45 человек либо победители, либо призеры).

Таким образом, ответ 993 950

Ответ: 993950

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

Задача 11#50441

В магазине сотовой связи представлены смартфоны различной стоимости. Считается, что K самых дешёвых смартфонов относятся к бюджетному сегменту, а M самых дорогих – к премиум сегменту.
Входные и выходные данные. В первой строке входного файла 5.txt находятся три числа, записанные через пробел: N – общее количество приведённых далее цен на смартфоны (натуральное число, не превышающее 10 000), K – количество смартфонов в бюджетном сегменте, M – количество смартфонов в премиум сегменте. В следующих N строках находятся значения цен на смартфоны (все числа натуральные, не превышающие 30000), каждое в отдельной строке.
Запишите в ответе без пробелов два числа: сначала цену самого дорогого смартфона, не попадающего в премиум сегмент, а затем целую часть средней цены телефона из сегмента, не относящегося ни к премиум, ни к бюджетному.
Пример входного файла:
10 3 2
28500
12000
17500
25000
18000
20000
22500
7500
19000
5500
При таких исходных данных ответ должен содержать 2 числа – 22500 и 19400. Пояснение: стоимость смартфонов из бюджетного сегмента: 5500, 7500, 12000; стоимость смартфонов из премиум сегмента – 25000 и 28500. Максимальная цена смартфона не класса премиум - 22500, а средняя цена смартфонов, не относящихся ни к премиум, ни бюджетным, - (22500 + 20000 + 19000 + 18000 + 17500)/5 = 19400.0.

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

26_5.txt

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

Всего смартфонов - 7777, количество смартфонов в бюджетном сегменте - 190, количество смартфонов в премиум сегменте - 82. Копируем столбец с ценами в Excel и сортируем по убыванию, теперь в начале столбца находятся смартфоны премиум класса, а в конце - бюджетного класса. Так как получается, что теперь в первых 82 ячейках находятся смартфоны в премиум сегменте, то в ячейке А83 будет находится цена на самый дорогой телефон после премиум сегмента. А83 = 29732.

Необходимо найти среднее значение сегмента, который не относится ни к бюджетному, ни к премиум. Весь диапазон столбца с ценами таков А1:А7777. Из начала надо убрать 82 ячейки, а из конца 190 ячеек, тогда диапазон для обычного сегмента будет А83:А7587.

СРЗНАЧ(А83:А7587) = 17865

Таким образом, ответ 29732 17865

Ответ: 2973217865

Интенсивы

Глубокий разбор тем, требующих дополнительного внимания

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

Задача 12#50442

На вход программе поступает набор чисел в диапазоне [10; 5000]. Необходимо узнать, сколько чисел в массиве находятся в диапазоне между минимальным значением и медианой, включая совпадающие с этими показателями значения. Медианой называется такое значение, что ровно половина из оставшихся элементов больше медианы и, соответственно, вторая половина меньше медианы.
Входные данные представлены в файле 6.txt следующим образом. В первой строке записано нечетное число N – количество чисел, в каждой из последующих N строк число из обрабатываемой последовательности.
В качестве ответа дать одно число – количество найденных чисел.
Пример организации исходных данных во входном файле:
7
10
47
60
84
65
47
37
При таких исходных результатом является число 2. Минимальное значение равно 10, медиана – 47. Таким образом, попадают числа 10, 37, 47 и 47.
Ответ: 4.

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

26_6.txt

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

Копируем столбец со значениями в Excel (без первой строки, в которой указано количество строк) и сортируем по возрастанию. Всего чисел 795, тогда получится, что есть 397 чисел, которые больше медианы и 397 чисел, которые меньше медианы. Значит наша медиана находится в 398 ячейке, в самой середине. Минимальное значение равно 18. В ячейке А398 хранится значение медианы, оно равно 2420. Смотрим, что числа 18 и 2420 в единcтвенном экземпляре. Тогда нам подходит диапазон A1:A398. Следовательно, ответ 398 чисел.

Ответ: 398

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

Задача 13#54782

В магазине для упаковки подарков есть $N$ кубических коробок и $M$ декоративных замочков к ним $(M < N ).$ Самой интересной считается упаковка подарка по принципу матрёшки - подарок упаковывается в одну из коробок, та в свою очередь в другую коробку и т. д., при этом к каждой коробке подбирается подходящий замочек. Одну коробку можно поместить в другую, если длина её стороны хотя бы на $6$ единиц меньше длины стороны другой коробки. Замочек подходит к коробке, если маркировка замочка совпадает с длиной стороны коробки. Определите наибольшее количество коробок, которое можно использовать для упаковки одного подарка, и максимально возможную длину стороны самой маленькой коробки, где будет находиться подарок. Размер подарка позволяет поместить его в самую маленькую коробку.

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

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

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

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

$5 4$

$43 40$

$31 30$

$32 43$

$40 31$

$30$

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

При таких исходных данных условию задачи удовлетворяют набор коробок с длинами сторон $30$ , $40$ и $43$ или $31$ , $40$ и $43$ или $32$ , $40$ и $43$ соответственно, т.е. количество коробок равно $3$ , а длина стороны самой маленькой коробки равна $31$ (поскольку замочка для коробки с длиной стороны $32$ в магазине нет).

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.

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

26.txt

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

f = open(’26.txt’)
n, m = map(int, f.readline().split())
length = []
locks = set()
for i in range(m):
    x, y = map(int, f.readline().split())
    length.append(x)
    locks.add(y)
for i in range(n - m):
    x = int(f.readline())
    length.append(x)
length = sorted([i for i in length if i in locks], reverse=True)
ans = 1
x = length[0]
for i in range(1, len(length)):
    if (x - length[i]) >= 6:
        ans += 1
        x = length[i]
print(ans, x)

Ответ: 650 103

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

Задача 14#54939

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

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

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

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

6 2 3

7589

6344

8590

6231

3159

5462

При таких исходных данных ответ должен содержать 2 числа – 5462 и 7589. Пояснение: победители набрали 7589 и 8590 балла, призёры набрали 6344, 6231, 5462 баллов. Тогда минимальный балл призёра 5462, а минимальный балл победителя – 7589.

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

26.txt

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

file = open(’26.txt’)
n, k, m = [int(_) for _ in file.readline().split()]
arr = [int(_) for _ in file]
arr.sort(reverse=True)
min_win = 10 ** 6
min_prize = 10 ** 6
for i in range(len(arr)):
    if k != 0:
        k -= 1
        min_win = arr[i]
    elif m != 0:
        m -= 1
        min_prize = arr[i]
print(min_prize, min_win)

Ответ: 8904 9688

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

Задача 15#55486

Спутник «Фотон» проводит измерения солнечной активности, результат каждого измерения представляет собой натуральное число. Перед обработкой серии измерений из неё исключают K наибольших и K наименьших значений (как недостоверные). По заданной информации о значении каждого из измерений, а также количестве исключаемых значений, определите наименьшее достоверное измерение, а также целую часть среднего значения всех достоверных измерений.
Входные и выходные данные. В первой строке входного файла 4.txt находятся два числа, записанные через пробел: N – общее количество измерений (натуральное число, не превышающее 10 000) и K – количество исключаемых минимальных и максимальных значений. В следующих N строках находятся значения каждого из измерений (все числа натуральные, не превышающие 1000), каждое в отдельной строке. Запишите в ответе без пробелов два числа: сначала наименьшее достоверное измерение, а затем целую часть среднего значения всех достоверных измерений.
Пример входного файла:
10 2
34
50
43
44
23
9
39
5
38
36
При таких исходных данных ответ должен содержать 2 числа – 23 и 35. Пояснение: будут отброшены значения 5, 9, 44, 50. Тогда наименьшее оставшееся значение равно 23, а среднее значение из оставшихся равно (23+34+36+38+39+43):6 = 35,5.

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

4.txt

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

Открываем Excel, заходим в "Открыть"и выбираем текстовый документ из задачи. В вышедшем окне в первом пункте выбираем формат данных с разделителями. Во втором пункте помимо знака табуляции выбираем пробел. Формат данных столбца общий.

Перетаскиваем числа из первой строки в бок, чтобы не мешались. Пустую первую строку убираем(ПКМ на номер строки — удалить). Выделяем столбец с числами, нажимаем на "Сортировка и фильтр"(раздел "Главная справа), выбираем сортировку по возрастанию, удаляем первые 85 чисел. Затем выделяем столбец и применяем сортировку по убыванию, удаляем первые 85 чисел. Снова выделяем столбец и применяем сортировку по возрастанию, видим, что минимальное число — 86.

Находим среднее значение: =СРЗНАЧ(A:A). Берём целое значение — 501.

Ответ: 86501

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

Задача 16#55487

По итогам проведения олимпиады по программированию каждый участник получил определённое количество баллов, различное для каждого ученика. По регламенту олимпиады победителя присуждают K лучших участников, а призёра присуждают M лучших участников, следующих за ними. По заданной информации о результатах каждого из участников определите минимальный балл победителя и максимальный балл участника, не ставшего призером.
Входные и выходные данные. В первой строке входного файла 5.txt находятся три числа, записанные через пробел: N – общее количество результатов учащихся (натуральное число, не превышающее 10 000), K – количество победителей, M – количество призёров. В следующих N строках находятся значения каждого из результатов (все числа натуральные, не превышающие 1000), каждое в отдельной строке. Запишите в ответе без пробелов два числа: сначала минимальный балл победителя, а затем максимальный балл участника, не ставшего призером.
Пример входного файла:
10 2 4
244
39
213
108
132
18
46
52
242
179
При таких исходных данных ответ должен содержать 2 числа – 242 и 52. Пояснение: победители набрали 244 и 242 балла, призёры набрали 213, 179, 132, 108 баллов. Тогда минимальный балл победителя 242, а максимальный балл участника, не ставшего призером – 52.

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

5.txt

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

Минимальный победитель находится в 50-й ячейке, значение 920. Минимальный призёр находится в 250-й ячейке, значит, максимальный балл после призёров находится в 251-й ячейке, значение 613.

Ответ: 920613

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

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

Задача 17#55488

В магазине сотовой связи представлены смартфоны различной стоимости. Считается, что K самых дешёвых смартфонов относятся к бюджетному сегменту, а M самых дорогих – к премиум сегменту.
Входные и выходные данные. В первой строке входного файла 6.txt находятся три числа, записанные через пробел: N – общее количество приведённых далее цен на смартфоны (натуральное число, не превышающее 10 000), K – количество смартфонов в бюджетном сегменте, M – количество смартфонов в премиум сегменте. В следующих N строках находятся значения цен на смартфоны (все числа натуральные, не превышающие 30000), каждое в отдельной строке.
Запишите в ответе без пробелов два числа: сначала цену самого дешевого смартфона в премиум сегменте, а затем целую часть средней цены телефона из сегмента, не относящегося ни к премиум, ни к бюджетному.
Пример входного файла:
10 3 2
28500
12000
17500
25000
18000
20000
22500
7500
19000
5500
При таких исходных данных ответ должен содержать 2 числа – 25000 и 19400. Пояснение: стоимость смартфонов из бюджетного сегмента: 5500, 7500, 12000; стоимость смартфонов из премиум сегмента – 25000 и 28500. Минимальная цена смартфона класса премиум - 25000, а средняя цена смартфонов, не относящихся ни к премиум, ни бюджетным, - (22500 + 20000 + 19000 + 18000 + 17500)/5 = 19400.0.

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

6.txt

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

Самый дешёвый телефон из премиум сегмента находится в 170-й ячейке столбца, значит, берём значение из A170 = 29493.

Далее выделяем первые 170 элементов и удаляем их. Выделяем столбец, выполняем сортировку по возрастанию и удаляем первые 220 элементов. Затем находим среднее значение и берём целое число из него: =СРЗНАЧ(A:A).

Ответ: 2949317774

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

Задача 18#56167

Транспортная компания владеет автомобилями с грузоподъемность $M$ . Для транспортировки $N$ грузов автомобили загружают предметами по убыванию веса, пока общая масса предметов не превышает грузоподъемность $M$ . И далее процедуру повторяют для другого грузовика, до тех пор, пока все предметы не будут погружены.

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

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

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

Пример:

$6 100$

$30$

$10$

$40$

$50$

$10$

$20$

В первый автомобиль будут погружены грузы весом $50$ , $40$ и $10$ , во второй – грузы весом $30,20,10$ . Ответ: $2$ $100.$

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

0.txt

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

n, m  = map(int, input().split())

all = []
for i in range(n):
    num = int(input())
    all.append(num)

all = sorted(all)[::-1]

ans = []

while True:
    if all[0] == 0:
        break

    # [длина, цвет]
    chain = [ all[0] ]
    all.pop(0)
    all.append(0)

    i = 0
    while i < len(all):
        if all[i] == 0:
            break

        if sum(chain) + all[i] <= m:
            chain.append(all[i])
            all.pop(i)
            all.append(0)
            i -= 1
        i += 1

    ans.append(chain)


print(len(ans), sum(ans[-2]) )

Ответ: 38 1481

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

Задача 19#56168

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

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

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

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

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

Пример:

$7 9$

$2$

$18$

$47$

$16$

$38$

$55$

$48$

Для таких контейнеров можно составить три блока, удовлетворяющих условию: $(55,38,18,2)$ , $(48,16)$ и $(47)$ . Наибольшее количество контейнеров – в первом блоке – $4$ . Ответ: $3 4$ .

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

1.txt

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

n, k  = map(int, input().split())

all = []
for i in range(n):
    num = int(input())
    all.append(num)

all = sorted(all)[::-1]

ans = []

while True:
    if all[0] == 0:
        break

    # [длина, цвет]
    chain = [ all[0] ]
    all.pop(0)
    all.append(0)

    i = 0
    while i < len(all):
        if all[i] == 0:
            break

        if chain[-1] - all[i] >= k:
            chain.append(all[i])
            all.pop(i)
            all.append(0)
            i -= 1
        i += 1

    ans.append(chain)


print(len(ans), max( [len(x) for x in ans ] ))

Ответ: 19 1045

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

Задача 20#56169

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

а) размер стороны внешнего контейнера превышает размер стороны внутреннего на $K$ и более условных единиц

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

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

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

В первой строке входного файла записано натуральное число $N$ $(1 ≤ N ≤ 20000)$ – количество контейнеров, натуральное число $K$ $(1 ≤ K ≤ 1000)$ – наименьшая допустимая разница размеров вложенных соседних контейнеров

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

Пример:

$7 5$

$2 A$

$18 B$

$47 A$

$16 B$

$38 A$

$55 A$

$48 B$

Для такого набора контейнеров можно составить два блока, удовлетворяющих условию: $(55,48,38,18,2)$ , $(47,16)$ . Наибольшее количество контейнеров – в первом блоке – $5$ . Ответ: $2$ $5$ .

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

2.txt

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

n, k  = map(int, input().split())

all = []
for i in range(n):
    num, color = input().split()
    all.append([int(num), color])

all = sorted(all)[::-1]

ans = []

while True:
    if all[0][0] == 0:
        break

    # [длина, цвет]
    chain = [ all[0] ]
    all.pop(0)
    all.append([0, 0])

    i = 0
    while i < len(all):
        if all[i][0] == 0:
            break

        if all[i][1] != chain[-1][1]:
            if chain[-1][0] - all[i][0] >= k:
                chain.append(all[i])
                all.pop(i)
                all.append([0, 0])
                i -= 1
        i += 1

    ans.append(chain)


print(len(ans), max( [len(x) for x in ans ] ))

Ответ: 25 2093

Предыдущий раздел

Следующий раздел