#3091

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

Темы: [Задача о рюкзаке]

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

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

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

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

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

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

Примеры

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

4 6
4 2 3 1

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

#3092

Гирьки

Темы: [Задача о рюкзаке]

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

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

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

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

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

Примеры

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

4
4 2 3 1

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

YES

#3093

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

Темы: [Задача о рюкзаке]

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

Формат входных данных

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

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

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

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

Примеры

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

4
4 2 3 1

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

2 3 
1 4

#3094

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

Темы: [Задача о рюкзаке]

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

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

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

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

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

Примеры

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

5
4 2 3 1 5

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

5 
1 4 
2 3

#3095

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

Темы: [Перебор] [Задача о рюкзаке]

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

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

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

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

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

Примеры

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

8
10 20 30 40 50 60 70 80

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