Портал обучения информатике. Подготовка к ЕГЭ, ОГЭ, олимпиадам

0-1 Рюкзак#47745

Дано N предметов массой m₁, …, m_N и стоимостью c₁, …, c_N соответственно.

Ими наполняют рюкзак, который выдерживает вес не более M. Какую наибольшую стоимость могут иметь предметы в рюкзаке?

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

Выходные данные
Выведите наибольшую стоимость рюкзака.

Задача о рюкзаке

✓ 34✗ 73400лёгкаяВойти и решать

Айвен собирает кристаллы#47744

Юный волшебник Айвен отправляется в волшебный лес, чтобы набрать волшебных кристаллов. Каждый кристалл, растущий в данном лесу, обладает своей массой. Айвен имеет рюкзак, который может выдержать определенный вес M. Айвен хочет использовать свой рюкзак по максимуму и набрать кристаллов такое количество, чтобы суммарно их вес равнялся в точности весу, который может выдержать его рюкзак.
Вам стали известны массы кристаллов, которые растут в волшебном лесу. Выведите "YES", если Айвен сможет набрать кристаллов суммарным весом ровно M, иначе выведите "NO".

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

Выходные данные
Выведите YES или NO.

Динамическое программирование Задача о рюкзаке

✓ 37✗ 60600лёгкаяВойти и решать

Кристаллы максимуса#47675

Максимус очень любит коллекционировать кристаллы. Среди всех кристаллов у него есть один самый любимый с магической силой равной n. Также у него есть коллекция совершенных кристаллов. Совершенный кристалл - это кристалл, магическая сила которого равна квадрату натурального числа.
У Максимуса выдался свободный вечер, и он задумался: сколько нужно ему совершенных кристаллов, чтобы сумма их магических сил равнялась бы магической силе его любимого кристалла?
Квадратом натурального числа является число, которое получается умножением натурального числа на себя. Например, 1, 4 и 9 - это квадраты натуральных чисел, а 2, 3 и 5 - нет.
Ваша задача - помочь Максимусу найти минимальное количество совершенных кристаллов, сумма магических сил которых равна n.

Входные данные
Программа получает на вход натуральное число n (n < 10⁴).

Выходные данные
Выведите ответ на задачу.

Примеры

№	Входные данные	Выходные данные	Примечание
1	12	3	`12 = 4 + 4 + 4`
2	`13`	`2`	`13 = 4 + 9`

Динамическое программирование Задача о рюкзаке

✓ 40✗ 71500лёгкаяВойти и решать

Сдача (java)#46546

Определите количество различных способов выплаты сдачи в размере n рублей купюрами 10 рублей и монетами 5, 2 и 1 рубль.

Например, 5 рублей можно выплатить четырьмя различными способами: 5 = 2 + 2 + 1 = 2 + 1 + 1 + 1 = 1 + 1 + 1 + 1 + 1.

Входные данные
На вход программе подается натуральное число n <= 100 — размер сдачи, которую необходимо выплатить.

Выходные данные
Выведите искомое количество способов выплаты.

Примеры

№	Входные данные	Выходные данные
1	2	2
2	5	4

Динамическое программирование: один параметр Задача о рюкзаке

✓ 124✗ 12300лёгкаяВойти и решать

Гомер Симпсон#33650

Обеденный перерыв Гомера Симпсона составляет T миллисекунд. Один гамбургер Гомер съедает за N миллисекунд, один чизбургер - за M. Какое количество гамбургеров и чизбургеров нужно съесть, чтобы потраченное время было как можно больше, не превышая T. При равенстве потраченного времени необходимо максимизировать суммарное количество съеденных гамбургеров и чизбургеров.

Ограничения: 1 <=M, N, T, <= 1000000 , все числа целые.

Входные данные
В первой строке находятся три числа - M, N и T, разделённые пробелами.

Выходные данные
Вывести максимальное суммарное число гамбургеров и чизбургеров. Если остаётся какое-то время, требуется указать его через пробел. Предпочтителен вариант, когда дополнительного времени остаётся как можно меньше.

Ввод	Вывод
1 2 1000	1000
2 1 1000	1000
3 6 1000	333 1

Задача о рюкзаке

✓ 40✗ 239600лёгкаяВойти и решать

Гирьки#33088

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

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

- в первой строке вводится натуральное число N, не превышающее 100;

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

Выходные данные: выведите YES или NO.

Примеры

№	Входные данные	Выходные данные
1	1 17	NO
2	2 19 19	YES

Задача о рюкзаке

✓ 238✗ 407600лёгкаяВойти и решать

0-1 рюкзак: минимум предметов#33087

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

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

- в первой строке вводится натуральное число N, не превышающее 100 и натуральное число M, не превышающее 10000;

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

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

Примеры

№	Входные данные	Выходные данные
1	1 5968 18	0

Задача о рюкзаке

✓ 371✗ 1 267600лёгкаяВойти и решать

0-1 рюкзак: наибольший вес#33086

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

Входные данные:
- в первой строке вводится натуральное число N, не превышающее 100 и натуральное число M, не превышающее 10000;

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

Выходные данные: выведите одно целое число - наибольшую возможную массу золота, которую можно унести в данном рюкзаке.

Примеры

№	Входные данные	Выходные данные
1	2 3195 38 41	79

Задача о рюкзаке

✓ 653✗ 996400лёгкаяВойти и решать

Задача о рюкзаке с восстановлением ответа#33081

Дано N предметов массой m₁, …, m_N и стоимостью c₁, …, c_N соответственно.

Ими наполняют рюкзак, который выдерживает вес не более M. Определите набор предметов, который можно унести в рюкзаке, имеющий наибольшую стоимость.

Входные данные:
- в первой строке вводится натуральное число N, не превышающее 100 и натуральное число M, не превышающее 10000;

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

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

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

Примеры

№	Входные данные	Выходные данные
1	4 6 2 4 1 2 7 2 5 1	1 3 4

Задача о рюкзаке

✓ 400✗ 846600лёгкаяВойти и решать

Максимальная прибыль#24755

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

Про каждую задачу известно время t_i, которое нужно затратить, чтобы сделать её, а также прибыль p_i, которую сделанная задача принесёт компании. Вы хотите включить в план некоторые задачи так, чтобы:

Суммарное время, затраченное на выполнение задач, включённых в план, не превышало T.
Суммарная прибыль от выполнения этих задач была максимальна.

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

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

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

В первой строке находятся натуральные числа T (1 ≤ T ≤ 100 000) и n (1 ≤ n ≤ 10) - число единиц времени в месяце и число задач.

Следующие n строк содержат по два натуральных числа t_i и p_i (1 <= t_i, p_i <= 100 000) - время, которое необходимо затратить на выполнение i-й задачи и прибыль, которую можно получить, выполнив её.

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

Выведите единственное число — максимальная прибыль, которую можно получить, составив план, удовлетворяющий написанным выше условиям.

Примеры

№	Входные данные	Выходные данные
1	10 3 8 100 3 10 3 10	100
2	10 4 5 10 5 20 2 5 2 6	31

битмаски Задача о рюкзаке

✓ 56✗ 87700средняяВойти и решать