#3095

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

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

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

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

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

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

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

Примеры

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

8
10 20 30 40 50 60 70 80

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

#3096

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

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

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

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

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

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

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

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

Примеры

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

6
10 20 30 40 50 60

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

1 6 
2 5 
3 4

#3097

Сдача - 1

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

Покупатель хочет приобрести товар стоимостью S рублей. У него есть N банкнот номиналом P₁, P₂, ..., P_N рублей. У продавца есть M банкнот номиналом Q₁, Q₂, ..., Q_M. рублей. Определите, смогут ли они рассчитаться.

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

Программа получает на вход сумму S. Далее идет число N затем P₁, P₂, ..., P_N. Далее идет число M, затем Q₁, Q₂, ..., Q_M. Количество банкнот у продавца и покупателя и их номиналы не превосходят 100.

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

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

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

Примеры

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

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

-2 +9 +3

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

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

Impossible

#3098

Сдача - 2

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

Покупатель хочет приобрести товар стоимостью S рублей. У него есть N банкнот номиналом P₁, P₂, ..., P_N рублей. У продавца есть M банкнот номиналом Q₁, Q₂, ..., Q_M. рублей. Определите, смогут ли они рассчитаться.

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

Программа получает на вход сумму S. Далее идет число N затем P₁, P₂, ..., P_N. Далее идет число M, затем Q₁, Q₂, ..., Q_M.Количество банкнот у продавца и покупателя и их номиналы не превосходят 100.

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

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

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

Примеры

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

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

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

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

-1

#3130

Длина максимального подпалиндрома

Темы: [Динамическое программирование по подстрокам]

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

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

Во входном файле находится строка длиной не более 100 символов, состоящая из заглавных букв латинского алфавита.

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

Выведите длину максимального подпалиндрома.

Примеры

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

THISISEASI

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