Дано \(N\) предметов массой \(m_1, \ldots, m_N\) и стоимостью \(c_1, \ldots, c_N\) соответственно.
Ими наполняют рюкзак, который выдерживает вес не более \(M\). Какую наибольшую стоимость могут иметь предметы в рюкзаке?
В первой строке вводится натуральное число \(N\), не превышающее \(100\) и натуральное число \(M\), не превышающее \(10000\).
Во второй строке вводятся \(N\) натуральных чисел \(m_i\), не превышающих \(100\).
Во третьей строке вводятся \(N\) натуральных чисел \(с_i\), не превышающих \(100\).
Выведите одно целое число: наибольшую возможную стоимость рюкзака.
| Ввод | Вывод |
|---|---|
4 6 2 4 1 2 7 2 5 1 |
13 |
В некотором государстве в обращении находятся банкноты определенных номиналов. Национальный банк хочет, чтобы банкомат выдавал любую запрошенную сумму при помощи минимального числа банкнот, считая, что запас банкнот каж дого номинала неограничен. Помогите Национальному банку решить эту задачу.
Первая строка входных данных содержит натуральное число \(N\) не превосходящее \(100\) — количество номиналов банкнот в обращении. Вторая строка входных данных содержит \(N\) различных натуральных чисел \(x_1, x_2, \ldots, x_N\), не превосходящих \(10^{6}\) — номиналы банкнот. Третья строчка содержит натуральное число \(S\), не превосходящее \(10^6\) —сумму, которую необходимо выдать.
Программа должна найти представление числа \(S\) виде суммы слагаемых из множества \(x_i\), содержащее минимальное число слагаемых и вывести это представление на экран (в виде последовательности чисел, разделенных пробелами). Если таких представлений существует несколько, то программа должна вывести любое (одно) из них. Если такое представление не существует, то программа должна вывести строку No solution.
| Ввод | Вывод |
|---|---|
5 1 3 7 12 32 40 |
32 7 1 |
Дано \(N\) предметов массой \(m_1, \ldots, m_N\) и стоимостью \(c_1, \ldots, c_N\) соответственно.
Ими наполняют рюкзак, который выдерживает вес не более \(M\). Определите набор предметов, который можно унести в рюкзаке, имеющий наибольшую стоимость.
В первой строке вводится натуральное число \(N\), не превышающее \(100\) и натуральное число \(M\), не превышающее \(10000\).
Во второй строке вводятся \(N\) натуральных чисел \(m_i\), не превышающих \(100\).
Во третьей строке вводятся \(N\) натуральных чисел \(с_i\), не превышающих \(100\).
Выведите номера предметов (числа от \(1\) до \(N\)), которые войдут в рюкзак наибольшей стоимости.
| Ввод | Вывод |
|---|---|
4 6 2 4 1 2 7 2 5 1 |
1 3 4 |
Дано \(N\) золотых слитков массой \(m_1, \ldots, m_N\). Ими наполняют рюкзак, который выдерживает вес не более \(M\). Какую наибольшую массу золота можно унести в таком рюкзаке?
В первой строке вводится натуральное число \(N\), не превышающее 100 и натуральное число \(M\), не превышающее 10000.
Во второй строке вводятся \(N\) натуральных чисел \(m_i\), не превышающих 100.
Выведите одно целое число - наибольшую возможную массу золота, которую можно унести в данном рюкзаке.
| Ввод | Вывод |
|---|---|
2 3195 38 41 |
79 |
Дано \(N\) предметов массой \(m_1, \ldots, m_N\). Ими наполняют рюкзак, который выдерживает вес не более \(M\). Как набрать вес в точности \(M\), используя как можно меньше предметов?
Первая строка входных данных содержит натуральное число \(N\), не превышающее 100 и натуральное число \(M\), не превышающее 10000.
Во второй строке находится \(N\) натуральных чисел \(m_i\), не превышающих 100.
Выведите наименьшее необходимое число предметов или 0, если набрать данный вес невозможно.
| Ввод | Вывод |
|---|---|
4 6 4 2 3 1 |
2 |
Дан набор гирек массой \(m_1, \ldots, m_N\). Можно ли их разложить на две чаши весов, чтобы они оказались в равновесии?
Первая строка входных данных содержит натуральное число \(N\), не превышающее 100. Далее идет \(N\) натуральных чисел \(m_i\), не превышающих 100.
Программа должна вывести YES, если гирьки можно разложить на две кучки равной массы или NO в противном случае.
| Ввод | Вывод |
|---|---|
4 4 2 3 1 |
YES |
По случаю введения больших новогодних каникул устраивается великий праздничный бал-маскарад. До праздника остались считанные дни, поэтому срочно нужны костюмы для участников. Для пошивки костюмов требуется \(L\) метров ткани. Ткань продается в \(N\) магазинах, в которых предоставляются скидки оптовым покупателям. В магазинах можно купить только целое число метров ткани. Реклама магазина номер \(i\) гласит "Мы с радостью продадим Вам метр ткани за \(P_i\) бурлей, однако если Вы купите не менее \(R_i\) метров, то получите прекрасную скидку — каждый купленный метр обойдется Вам всего в \(Q_i\) бурлей". Чтобы воплотить в жизнь лозунг "экономика страны должна быть экономной", правительство решило потратить на закупку ткани для костюмов минимальное количество бурлей из государственной казны. При этом ткани можно купить больше, чем нужно, если так окажется дешевле. Ответственный за покупку ткани позвонил в каждый магазин и узнал, что:
1) реклама каждого магазина содержит правдивую информацию о ценах и скидках;
2) магазин номер \(i\) готов продать ему не более \(F_i\) метров ткани.
Ответственный за покупку очень устал от проделанной работы и поэтому поставленную перед ним задачу «закупить ткань за минимальные деньги» переложил на своих помощников. Напишите программу, которая определит, сколько ткани нужно купить в каждом из магазинов так, чтобы суммарные затраты были минимальны.
В первой строке входного файла записаны два целых числа \(N\) и \(L\) \((1 \leq N \leq 100, 0 \leq L \leq 100)\). В каждой из последующих \(N\) строк находится описание магазина номер \(i\) — \(4\) целых числа \(P_i, R_i, Q_i, F_i\) \((1 \leq Q_i \leq P_i \leq 1000, 1 \leq R_i \leq 100, 0 \leq F_i \leq 100)\).
Первая строка выходного файла должна содержать единственное число — минимальное необходимое количество бурлей.
Во второй строке выведите \(N\) чисел, разделенных пробелами, где \(i-ое\) число определяет количество метров ткани, которое нужно купить в \(i-ом\) магазине. Если в \(i-ом\) магазине ткань покупаться не будет, то на \(i-ом\) месте должно стоять число \(0\). Если вариантов покупки несколько, выведите любой из них.
Если ткани в магазинах недостаточно для пошивки костюмов, выходной файл должен содержать единственное число \(-1\).
| Ввод | Вывод |
|---|---|
2 14 7 9 6 10 7 8 6 10 |
88 10 4 |
1 20 1 1 1 1 |
-1 |