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

Добавлена: 21.07.2026
Обновлена: 21.07.2026
Предмет: Теория вероятностей
Автор: Кэмп

#Теория вероятностей и математическая статистика
#Теория случайных величин

Условие:

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

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

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

Решение:

Дано

$N$ — количество гирек ( $N \le 1000$ ).
$w_1, w_2, \dots, w_N$ — веса гирек ( $w_i \le 10000$ ).

Найти

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

Решение

Шаг 1: Поиск минимальной недостижимой массы $M$

Пусть $S$ — множество всех возможных сумм, которые можно составить из имеющихся гирек. Нам нужно найти наименьшее целое число $M$ , такое что $M \notin S$ .