Олимпиадный тренинг

Задача . Balanced Cow Subsets


Задача

Темы: meet-in-the-middle

У Фермера Джона есть N cows (2 <= N <= 20), и корова I производит M(i) единиц молока ежедневно (1 <= M(i) <= 100,000,000). ФД хочет рационализировать процесс ежедневной дойки коров, поэтому он установил новый доильный аппарат в амбаре. Есть одно НО – аппарат работает, только если коровы на левой стороне амбара имеют такое же общее количество молока, как и коровы на правой стороне амбара.
Назовем подмножество коров «сбалансированным», если оно может быть разбито на две группы, имеющие равные суммарные надои молока.
ФД хочет, чтобы Вы посчитали, сколько подмножеств из его N коров сбалансированы.
PROBLEM NAME: subsets
Формат входных данных
* Строка 1: Целое N.
* Строки 2..1+N: Строка i+1 содержит M(i).
Формат выходных данных
* Строка 1: Количество сбалансированных подмножеств коров.
Примечание
Подмножество {1,2,3} может быть разбито на {1,2} и {3}. Подмножество {1,3,4} может быть разбито на {1,3} и {4}. Подмножество {1,2,3,4} может быть разбито на {1,4} и {2,3}.
Примеры
№Входные данныеВыходные данные
1 
4
1
2
3
4
 
3
Статистика успешных решений по компиляторам
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет