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

Беси учится управлять роботом, который она недавно получила в подарок.

Робот начинает в точке \((0, 0)\) координатной плоскости и Беси хочет привести робота в точку \((x_g, y_g)\). Изначально у Беси есть список из \(N\) (\(1\le N\le 40\)) инструкций для робота, \(i\)-ая из которых перемещает робота на \(x_i\) единиц вправо и на \(y_i\) единиц вверх (или влево и вниз, если \(x_i\) и \(y_i\) отрицательные, соответственно).

Для каждого \(K\) от \(1\) to \(N\), вычислите количество способов, которыми Беси может выбрать \(K\) инструкций из исходного списка так, что после применения этих \(K\) инструкций, робот окажется в точке \((x_g, y_g)\).

**Замечание: лимиты на время и память в этой задаче увеличены вдвое до 4s и 512MB, относительно значений по умолчанию.**

ФОРМАТ ВВОДА (с клавиатуры / stdin):

Первая строка содержит \(N\). Следующая строка содержит \(x_g\) и \(y_g\), каждое в интервале \(-10^9 \ldots 10^9\). Последующие \(N\) описывают инструкции. Каждая строка содержит два целых числа \(x_i\) и \(y_i\), также в интервале \(-10^9 \ldots 10^9\).

Гарантируется, что \((x_g,y_g)\neq (0,0)\) и \((x_i,y_i)\neq (0,0)\) для всех \(i\).

ФОРМАТ ВЫВОДА (на экран / stdout):

Выведите \(N\) строк, количество способов, которыми Беси может выбрать \(K\) инструкций из списка оригинальных \(N\), для каждого \(K\) от \(1\) до \(N\).

meet-in-the-middle

—Войти и решать

Balanced Cow Subsets#89855

У Фермера Джона есть 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}.

meet-in-the-middle

—Войти и решать

Красивые разбиения#59853

Напомним, что простое число — это целое число, которое делится ровно на два целых числа: на единицу и на себя. Последовательность простых чисел начинается с \(2, 3, 5, \ldots\).

Рассмотрим первые \(n\) простых чисел. Давайте разделим их на две части \(A\) и \(B\) так, чтобы каждое простое число принадлежало ровно одной из этих двух частей. Обозначим произведение всех простых чисел в \(A\) как \(a\), а произведение всех простых чисел в \(B\) как \(b\). Произведение чисел в пустом множестве будем считать равным \(1\). Будем называть разбиение красивым, если \(a < b\) и \(b-a\) минимальное возможное.

Дано \(n\), найдите красивое разбиение множества первых \(n\) простых чисел и выведите соответствующее значение \(a\).

Формат входных данных
Входные данные содержит целое число \(n\) на отдельной строке (\(1 \le n \le 30\)).

Формат выходных данных
Выведите значение \(a\) в красивом разбиении множества первых \(n\) простых чисел.

meet-in-the-middle битмаски

✓ 2✗ 141 100средняяВойти и решать