| Условие задачи | | |
ID 33086: 0-1 рюкзак: наибольший вес
Темы:
Задача о рюкзаке
Дано N золотых слитков массой m1, …, mN. Ими наполняют рюкзак, который выдерживает вес не более M. Какую наибольшую массу золота можно унести в таком рюкзаке?
Входные данные:
- в первой строке вводится натуральное число N, не превышающее 100 и натуральное число M, не превышающее 10000;
- во второй строке вводятся N натуральных чисел mi, не превышающих 100.
Выходные данные: выведите одно целое число - наибольшую возможную массу золота, которую можно унести в данном рюкзаке.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
2 3195
38 41
|
79 |
| |
![]()
|
ID 33105: Копилка
Темы:
Задача о рюкзаке
Задан вес E пустой копилки и вес F копилки с монетами. В копилке могут находиться монеты N видов, для каждого вида известна ценность Pi и вес Wi одной монеты. Найти минимальную и максимальную суммы денег, которые могут находиться в копилке.
Входные данные:
- в первой строке находятся числа E и F (\(1<=E<=F<=10000\));
- во второй - число N (\(1<=N<=500\));
- в следующих N строках - по два числа, Pi и Wi (\(1<=Pi<=50000\), \(1<=Wi<=10000\)).
Все числа целые.
Выходные данные: выводятся два числа через пробел - минимальная и максимальная суммы. Если копилка не может иметь точно заданный вес при условии, что она наполнена монетами заданных видов, - вывести "This is impossible.".
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
1000 1100
2
1 1
5 2
|
100 250 |
| 2 |
1000 1010
2
6 3
2 2
|
10 16 |
| 3 |
1000 2000
1
10 3
|
This is impossible. |
| |
![]()
|
ID 33087: 0-1 рюкзак: минимум предметов
Темы:
Задача о рюкзаке
Дано N предметов массой m1, …, mN. Ими наполняют рюкзак, который выдерживает вес не более M. Как набрать вес в точности M, используя как можно меньше предметов?
Входные данные:
- в первой строке вводится натуральное число N, не превышающее 100 и натуральное число M, не превышающее 10000;
- во второе строке вводятся N натуральных чисел mi, не превышающих 100.
Выходные данные: выведите наименьшее необходимое число предметов или 0, если набрать данный вес невозможно.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
1 5968
18
|
0 |
| |
![]()
|
ID 33088: Гирьки
Темы:
Задача о рюкзаке
Дан набор гирь массой m1, …, mN. Можно ли их разложить на две чаши весов, чтобы они оказались в равновесии?
Входные данные:
- в первой строке вводится натуральное число N, не превышающее 100;
- во второе строке вводятся N натуральных чисел mi, не превышающих 100.
Выходные данные: выведите YES или NO.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
1
17 |
NO |
| 2 |
2
19 19 |
YES |
| |
![]()
|
ID 33081: Задача о рюкзаке с восстановлением ответа
Темы:
Задача о рюкзаке
Дано N предметов массой m1, …, mN и стоимостью c1, …, cN соответственно.
Ими наполняют рюкзак, который выдерживает вес не более M. Определите набор предметов, который можно унести в рюкзаке, имеющий наибольшую стоимость.
Входные данные:
- в первой строке вводится натуральное число N, не превышающее 100 и натуральное число M, не превышающее 10000;
- во второй строке вводятся N натуральных чисел mi, не превышающих 100;
- в третьей строке вводятся N натуральных чисел сi, не превышающих 100.
Выходные данные: выведите номера предметов (числа от 1 до N), которые войдут в рюкзак наибольшей стоимости (по одному номеру в строке).
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
4 6
2 4 1 2
7 2 5 1
|
1
3
4 |
| |
![]()
|
ID 33104: Сдача - 1
Темы:
Задача о рюкзаке
Покупатель хочет приобрести товар стоимостью S рублей. У него есть N банкнот номиналом P1, P2, ..., PN рублей. У продавца есть M банкнот номиналом Q1, Q2, ..., QM. рублей. Определите, смогут ли они рассчитаться.
Входные данные:
- в первой строке задается сумма S;
- во второй строке - число N;
- в третьей строке - N чисел P1, P2, ..., PN;
- в четвертой строке - число M;
- в пятой строке - M чисел Q1, Q2, ..., QM.
Количество банкнот у продавца и покупателя и их номиналы не превосходят 100.
Выходные данные: если продавец сможет рассчитаться с покупателем, выведите номиналы банкнот, которые покупатель отдает продавцу и которые он получает в качестве сдачи. Выводите число со знаком “+”, если банкноту соответствующего номинала покупатель отдает продавцу и со знаком “-”, если покупатель получает эту банкноту на сдачу. Номиналы банкнот разделяйте пробелом.
Если они не могут рассчитаться, выведите строку Impossible.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
10
3
3 9 14
2
6 2
|
-2 +9 +3 |
| 2 |
100
3
74 35 8
2
19 6
|
Impossible |
| |
![]()
|
ID 33650: Гомер Симпсон
Темы:
Задача о рюкзаке
Обеденный перерыв Гомера Симпсона составляет T миллисекунд. Один гамбургер Гомер съедает за N миллисекунд, один чизбургер - за M. Какое количество гамбургеров и чизбургеров нужно съесть, чтобы потраченное время было как можно больше, не превышая T. При равенстве потраченного времени необходимо максимизировать суммарное количество съеденных гамбургеров и чизбургеров.
Ограничения: 1 <=M, N, T, <= 1000000 , все числа целые.
Входные данные
В первой строке находятся три числа - M, N и T, разделённые пробелами.
Выходные данные
Вывести максимальное суммарное число гамбургеров и чизбургеров. Если остаётся какое-то время, требуется указать его через пробел. Предпочтителен вариант, когда дополнительного времени остаётся как можно меньше.
| Ввод |
Вывод |
| 1 2 1000 |
1000 |
| 2 1 1000 |
1000 |
| |
![]()
|