Задачи о рюкзаках

A: Разложение в сумму кубов

Дано натуральное число N. Необходимо представить его в виде суммы точных кубов, содержащей наименьшее число слагаемых. Программа должна вывести это число слагаемых.

Программа получает на вход натуральное число N, не превосходящее 10⁶.

Программа должна вывести единственное натуральное число.

Пример

33

5

Примечание. 33=2³+2³+2³+2³+1³.

B: Банкомат

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

Первая строка входных данных содержит натуральное число N не превосходящее 100 — количество номиналов банкнот в обращении. Вторая строка входных данных содержит N различных натуральных чисел x₁, x₂, ..., x_N, не превосходящих 10⁶ — номиналы банкнот. Третья строчка содержит натуральное число S, не превосходящее 10⁶ —сумму, которую необходимо выдать.

Программа должна найти представление числа S виде суммы слагаемых из множества x_i, содержащее минимальное число слагаемых и вывести это представление на экран (в виде последовательности чисел, разделенных пробелами). Если таких представлений существует несколько, то программа должна вывести любое (одно) из них. Если такое представление не существует, то программа должна вывести строку No solution.

Пример

5
1 3 7 12 32
40

1 7 32

5
10 50 100 500 1000
99

No solution

C: Золотые слитки

Даны N золотых слитков известных масс. Определите, какую наибольшую массу золота можно унести, если вместимость рюкзака не превышает S.

Программа получает на вход целое число S — вместимость рюкзака, не превосходящее 10000 и количество слитков N, не превосходящее 300. Далее следует N целых неотрицательных чисел, не превосходящих 100000 — веса слитков.

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

Пример

10 3
5 7 4

9

D: Рюкзак

Дано N предметов массой m₁, …, m_N и стоимостью c₁, …, 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

E: Рюкзак с восстановлением ответа

Решите предыдущую задачу при условии, что необходимо вывести номера предметов (числа от 1 до N), которые войдут в рюкзак наибольшего веса.

Пример

4 6
2 4 1 2
7 2 5 1

1 3 4

F: Минимум предметов

Дано N предметов массой m₁, …, m_N. Ими наполняют рюкзак, который выдерживает вес не более M. Как набрать вес в точности M, используя как можно меньше предметов?

Первая строка входных данных содержит натуральное число N, не превышающее 100 и натуральное число M, не превышающее 10000.

Во второе строке находится N натуральных чисел m_i, не превышающих 100.

Выведите наименьшее необходимое число предметов или 0, если набрать данный вес невозможно.

Пример

4 6
4 2 3 1

2

G: Гирьки

Дан набор гирек массой m₁, …, m_N. Можно ли их разложить на две чаши весов, чтобы они оказались в равновесии?

Первая строка входных данных содержит натуральное число N, не превышающее 100. Далее идет N натуральных чисел m_i, не превышающих 100.

Программа должна вывести YES, если гирьки можно разложить на две кучки равной массы или NO в противном случае.

Пример

4
4 2 3 1

YES

H: Гирьки - кучки одного размера

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

Формат входных данных аналогичен предыдущей задаче.

Необходимо вывести в первой строчке номера гирек (числа от 1 до N), входящие в первую кучку, во второй строчке — номера гирек во второй кучке. Если задача не имеет решения, выведите строку No solution.

Пример

4
4 2 3 1

1 4
2 3

I: Гирьки - три кучки

Дан набор гирек. Разделите его на три кучки равной масссы.

Формат входных данных аналогичен предыдущей задачи. Количество гирек N и массы гирек m_i не превосходят 60.

Программа должна вывести номера гирек для каждого из наборов в три строки или строчку No solution, если решения не существует.

Пример

5
4 2 3 1 5

1 4
5
2 3

J: Гирьки - четыре кучки

Дан набор гирек. Разделите его на четыре кучки равной масссы.

Формат входных данных аналогичен предыдущей задачи. Количество гирек N не превосходит 14, массы гирек m_i не превосходят 100.

Программа должна вывести номера гирек для каждого из наборов в четыре строки или строчку No solution, если решения не существует.

Пример

8
10 20 30 40 50 60 70 80

1 8
2 7
3 6
4 5

K: Гирьки - три кучки одного размера

Дан набор гирек. Разделите его на три кучки равной масссы, содержащие равное число гирек.

Формат входных данных аналогичен предыдущей задачи. Количество гирек N не превосходит 18, массы гирек m_i не превосходят 100.

Программа должна вывести номера гирек для каждого из наборов в три строки или строчку No solution, если решения не существует.

Пример

6
10 20 30 40 50 60

1 6
2 5
3 4

L: Маскарад

По случаю введения больших новогодних каникул устраивается великий праздничный бал-маскарад. До праздника остались считанные дни, поэтому срочно нужны костюмы для участников. Для пошивки костюмов требуется L метров ткани. Ткань продается в N магазинах, в которых предоставляются скидки оптовым покупателям. В магазинах можно купить только целое число метров ткани. Реклама магазина номер i гласит “Мы с радостью продадим Вам метр ткани за P_i бурлей, однако если Вы купите не менее R_i метров, то получите прекрасную скидку — каждый купленный метр обойдется Вам всего в Q_i бурлей”. Чтобы воплотить в жизнь лозунг “экономика страны должна быть экономной”, правительство решило потратить на закупку ткани для костюмов минимальное количество бурлей из государственной казны. При этом ткани можно купить больше, чем нужно, если так окажется дешевле. Ответственный за покупку ткани позвонил в каждый магазин и узнал, что:

1) реклама каждого магазина содержит правдивую информацию о ценах и скидках;

2) магазин номер i готов продать ему не более F_i метров ткани.

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

В первой строке входного файла записаны два целых числа N и L (1≤N≤100, 0≤L≤100). В каждой из последующих N строк находится описание магазина номер i — 4 целых числа P_i, R_i, Q_i, F_i (1≤Q_i≤P_i≤1000, 1≤R_i≤100, 0≤F_i≤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

M: Сдача -1

Покупатель хочет приобрести товар стоимостью \(S\) рублей. У него есть \(N\) банкнот номиналом \(P_1\), \(P_2\), ..., \(P_N\) рублей. У продавца есть \(M\) банкнот номиналом \(Q_1\), \(Q_2\), ..., \(Q_M\) рублей. Определите, смогут ли они рассчитаться.

Программа получает на вход сумму \(S\). Далее идет число \(N\), затем \(P_1\), \(P_2\), ..., \(P_N\). Далее идет число \(M\), затем \(Q_1\), \(Q_2\), ..., \(Q_M\). Количество банкнот у продавца и покупателя и их номиналы не превосходят 100.

Если продавец сможет рассчитаться с покупателем, выведите номиналы банкнот, которые покупатель отдает продавци и которые он получает в качестве сдачи. Выводите число со знаком “+”, если банкноту соответствующего номината покупатель отдает продавцу и со знаком “-”, если покупатель получает эту банкноту на сдаду. Номиналы банкнот разделяйте пробелом.

Если они не могут рассчитаться, выведите строку Impossible.

Пример

10
3
3 9 14
2
6 2

-2 +9 +3

100
3
74 35 8
2
19 6

Impossible

N: Сдача - 2

Покупатель хочет приобрести товар стоимостью \(S\) рублей. У него есть \(N\) банкнот номиналом \(P_1\), \(P_2\), ..., \(P_N\) рублей. У продавца есть \(M\) банкнот номиналом \(Q_1\), \(Q_2\), ..., \(Q_M\) рублей. Определите, какое наименьшее число банкнот придется отдать продавцу на сдачу, чтобы они могли в точности рассчитаться.

Программа получает на вход сумму \(S\). Далее идет число \(N\), затем \(P_1\), \(P_2\), ..., \(P_N\). Далее идет число \(M\), затем \(Q_1\), \(Q_2\), ..., \(Q_M\). Количество банкнот у продавца и покупателя и их номиналы не превосходят 100.

Если продавец сможет рассчитаться с покупателем, выведите наименьшее количество банкнот, которое придется отдать продавцу на сдачу.

Если они не могут рассчитаться, выведите число -1.

Пример

10
4
3 3 9 3
2
6 2

1

100
3
74 35 8
2
19 6

-1