Разборы•21 час назад

Educational Round #3 — Разборы

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

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

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

Открыть задачу

Пусть $a, b, c$ — количество людей в первой, второй и третьей маршрутках. Для того чтобы после пересадки количество людей в маршрутках было одинаковое, необходимо чтобы сумма $a + b + c$ делилась на $3$ .

Пусть $d = (a + b + c) /3$ — количество людей, которое должно находиться в каждой маршрутке после пересадки. Тогда из каждой маршрутки следует пересадить в какую-то другую столько людей, чтобы в ней осталось ровно $d$ . Это возможно только если в маршрутке изначально находится больше $d$ пассажиров. Например, из первой маршрутки следует пересадить $a - d$ людей, если только $a > d$ . Со второй маршрутки следует пересадить $b - d$ людей (если $b > d$ ). Из третьей маршрутки следует пересадить $c - d$ людей (если $c > d$ ).

Огромное бедствие произошло сегодня утром в кафе, в котором Вы привыкли перекусывать во время учебы в университете. Уборщица Лариса Ивановна во время подметания пола уронила один из шкафов, в котором хранились все кухонные принадлежности. Все содержимое шкафа было разбросано по полу. К счастью, он содержал только кастрюли с крышками. Тем не менее, некоторые из них погнулись или сломались, поэтому были выброшены.

Теперь школьный учитель хочет подсчитать потери и выяснить, как много новых кастрюль и крышек следует купить. Но сначала следует выяснить, сколько оставшихся кастрюль можно накрыть оставшимися крышками.

Кастрюли и крышки круглые. Крышка может покрыть кастрюлю, если только радиус крышки не меньше радиуса кастрюли.

Вход. Первая строка содержит числа $n, m (1 \leq n, m \leq 1000)$ — количество оставшихся кастрюль и крышек. Вторая строка содержит $n$ целых чисел $a_{i} (1 \leq a_{i} \leq 1000)$ — радиусы оставшихся кастрюль. Третья строка содержит $m$ целых чисел $b_{i} (1 \leq b_{i} \leq 1000)$ — радиусы оставшихся крышек.

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

Открыть задачу

Попав в пещеру с сокровищами, Алладин не стал брать старую почерневшую лампу. Вместо этого он принялся заполнять свой рюкзак золотыми монетами и драгоценными камнями. Конечно, ему хотелось забрать всё, но чудес не бывает — рюкзак имеет ограниченную грузоподъёмность и может не выдержать слишком большой вес.

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

Требуется определить максимальную стоимость груза, который Алладин сможет унести.

Будем считать, что в пещере есть предметы $n$ различных типов, причём количество предметов каждого типа не ограничено. Рюкзак может выдержать вес не более $s$ . Каждый предмет типа $i$ имеет вес $w_{i}$ и стоимость $v_{i} (i = 1, 2, ..., n)$ .

Вход. В первой строке заданы два натуральных числа $s$ и $n (1 \leq s \leq 250, 1 \leq n \leq 35)$ — максимальный вес предметов в рюкзаке и количество типов предметов.

Далее следуют $n$ строк, каждая из которых содержит два числа $w_{i}$ и $v_{i} (1 \leq w_{i} \leq 250, 1 \leq v_{i} \leq 250)$ — вес и стоимость предмета типа $i$ .

Выход. Выведите максимальную стоимость груза, который можно унести, не превышая предельный вес $s$ .

Открыть задачу

Пусть $d p_{k} [s]$ — максимальная стоимость груза весом не более $s$ , если разрешено использовать только предметы первых $k$ типов.

Рассмотрим два возможных варианта при составлении груза весом $i$ :

Не использовать предмет $k$ -го типа: в этом случае оптимальное значение не изменится, то есть

d p_{k} [i] = d p_{k - 1} [i]

Использовать предмет $k$ -го типа: тогда его вес $w_{k}$ займёт часть вместимости рюкзака, а стоимость увеличится на $v_{k}$ , то есть

d p_{k} [i] = d p_{k} [i - w_{k}] + v_{k} .

Так как требуется максимизировать стоимость груза, получаем рекуррентное соотношение:

d p_{k} [i] = ma x (d p_{k - 1} [i], d p_{k} [i - w_{k}] + v_{k}), w_{k} \leq i \leq s

Базовые случаи:

d p_{0} [i] = 0 и d p_{k} [0] = 0

Пусть функция $f (k, s)$ вычисляет максимальную стоимость груза, который можно собрать в рюкзак весом не более $s$ , используя первые $k$ типов предметов. Тогда имеет место рекуррентное соотношение:

f (k, s) = ma x (f (k - 1, s), f (k, s - w [k]) + v [k])

Осталось вычислить значение функции $f (k, s)$ используя мемоизацию.

Объявим рабочие массивы:

$w [i]$ — вес предмета $i$ -го типа;
$p [i]$ — стоимость предмета $i$ -го типа;
$d p [i]$ — максимальная стоимость груза весом не более $i$ ;

#define MAXW 252
#define MAXN 37
int w[MAXN], p[MAXN];
int dp[MAXW];

Читаем входные данные.

scanf("%d %d", &s, &n);
for (i = 0; i < n; i++)
  scanf("%d %d", &w[i], &p[i]);

Последовательно обрабатываем $n$ типов предметов.

for (k = 0; k < n; k++)
{

Пересчитываем значения массива $d p$ , учитывая возможность использования предметов типа $k$ . Поскольку количество предметов каждого типа не ограничено, каждый предмет можно выбирать несколько раз.

  for (i = w[k]; i <= s; i++)
    dp[i] = max(dp[i], dp[i - w[k]] + p[k]);
}

Выводим ответ.

printf("%d\n", dp[s]);

Реализация алгоритма — рекурсия

Объявим рабочие массивы:

$w [i]$ — вес предмета $i$ -го типа;
$p [i]$ — стоимость предмета $i$ -го типа;
$d p [i]$ — максимальная стоимость груза весом не более $i$ ;

#define MAXW 252
#define MAXN 37
#define INF 2000000000
int w[MAXN], v[MAXN];
int dp[MAXN][MAXW];

Функция $f (k, s)$ вычисляет максимальную стоимость груза, который можно собрать в рюкзак весом не более $s$ , используя первые $k$ типов предметов.

int f(int k, int s)
{

Если $k = 0$ или $s = 0$ , то рюкзак пуст, и его стоимость равна $0$ .

  if (k == 0 || s == 0) return 0;

Если $s < 0$ , то мы превысили допустимый вес, и этот вариант не имеет смысла. Поэтому возвращаем $- I NF$ ( $I NF$ — это некоторое большое число).

  if (s < 0) return -INF;

Если значение $f (k, s)$ уже вычислено, то возвращаем его.

  if (dp[k][s] != -1) return dp[k][s];

Вычисляем значение $f (k, s)$ и запоминаем его в $d p [k] [s]$ .

  return dp[k][s] = max(f(k - 1, s), f(k, s - w[k]) + v[k]);
}

Основная часть программы. Читаем входные данные.

scanf("%d %d", &s, &n);
for (i = 1; i <= n; i++)
  scanf("%d %d", &w[i], &v[i]);

Вычисляем и выводим ответ.

memset(dp, -1, sizeof(dp));
printf("%d\n", f(n, s));

В подчинении у короля лемуров Джулиана находится ровно $2 \cdot k$ лемуров — по два лемура каждого из $k$ видов. Джулиан обожает вечеринки, поэтому каждый вечер устраивает тусовку. Однако в VIP-зоне, к сожалению, хватает мест только для него самого и ещё $n$ лемуров.

Поскольку Джулиан не любит повторяться, он старается каждый раз приглашать в VIP-зону такой набор лемуров, который ранее ещё не встречался. Два лемура одного вида считаются неразличимыми. Два набора лемуров считаются одинаковыми, если они совпадают как мультимножества видов лемуров.

Помогите Джулиану определить, сколько различных вечеринок он сможет провести. Так как ответ может быть очень большим, выведите его по модулю $1 0^{9} + 7$ .

Вход. В одной строке заданы два целых числа $k$ и $n (1 \leq k \leq 500000, 0 \leq n \leq 2 \cdot k)$ — количество видов лемуров и число мест в VIP-зоне (не считая самого Джулиана).

Выход. Выведите одно число — количество различных вечеринок по модулю $1 0^{9} + 7$ .

Открыть задачу

На $n$ мест некоторые виды будут представлены двумя лемурами, а некоторые одним. Пусть выбрано $i$ пар лемуров (то есть $i$ видов представлены двумя особями). Сделать такой выбор можно $C_{k}^{i}$ способами. После этого в VIP зоне останется $n - 2 i$ свободных мест. Эти места можно занять лемурами из $k - i$ оставшихся видов, выбирая по одному лемуру из каждого. Количество способов выбрать таких лемуров вычисляется по формуле $C_{k - i}^{n - 2 i}$ .

Так как значение $i$ может принимать любое целое значение от $0$ до $k$ , получаем итоговый ответ как сумму по всем возможным $i$ :

i = 0 \sum k C_{k}^{i} \cdot C_{k - i}^{n - 2 i}

Пример

Рассмотрим второй пример, в котором есть $k = 4$ пары лемуров и $n = 3$ места в VIP-зоне. По формуле получаем:

i = 0 \sum k C_{4}^{i} \cdot C_{4 - i}^{3 - 2 i} = C_{4}^{0} \cdot C_{4}^{3} + C_{4}^{1} \cdot C_{3}^{1} = 4 + 12 = 16

Выпишем только ненулевые слагаемые. Значение $C_{n}^{k}$ будем считать равным нулю, если выполняется одно из трех неравенств: $k < 0$ , $n < 0$ или $k > n$ .

Обозначим лемуров буквами ${a, a, b, b, c, c, d, d}$ , где одинаковые буквы соответствуют лемурам одного вида.

Слагаемому $C_{4}^{0} \cdot C_{4}^{3} = 4$ соответствует ситуация, когда ни одна пара лемуров одного вида не выбрана, то есть каждый из трёх выбранных лемуров принадлежит разным видам. Возможные четыре выборки следующие:

Рассмотрим слагаемое $C_{4}^{1} \cdot C_{3}^{1} = 12$ . В этом случае из одного вида выбираются два лемура (существует $4$ варианта такого выбора). На оставшееся одно место выбирается один лемур из трёх оставшихся видов. Таким образом, всего возможно $12$ различных вариантов:

Очевидно, что разместить на $3$ местах по два лемура из двух разных видов невозможно. Поэтому все остальные слагаемые суммы равны нулю.

Объявим константы.

#define MAX 1000001
#define MOD 1000000007

Объявим массивы:

$f a c t$ содержит факториалы чисел по модулю $MO D$ ;
$f a c t in v$ содержит значения, обратные факториалам чисел по модулю $MO D$ :

fact[n] = n! mod 1000000007
factinv[n] = n! -1 mod 1000000007

typedef long long ll;
ll fact[MAX], factinv[MAX];

Функция pow вычисляет степень числа по модулю: $x^{n} m o d p$ .

ll pow(ll x, ll n, ll p)
{
  if (n == 0) return 1;
  if (n % 2 == 0) return pow((x * x) % p, n / 2, p);
  return (x * pow(x, n - 1, p)) % p;
}

Функция inverse находит число, обратное $x$ по простому модулю $p$ . Поскольку $p$ — простое число, по малой теореме Ферма выполняется равенство:

x^{p - 1} m o d p = 1 для всякого 1 \leq x < p

Это равенство можно переписать в виде:

(x \cdot x^{p - 2}) m o d p = 1,

откуда следует, что обратным к $x$ является число $x^{p - 2} m o d p$ .

ll inverse(ll x, ll p)
{
  return pow(x, p - 2, p);
}

Функция Cnk вычисляет значение биномиального коэффициента по следующей формуле:

C_{n}^{k} = \frac{n !}{k ! ( n - k )!}

ll Cnk(int n, int k)
{
  return ((fact[n] * factinv[k]) % MOD * factinv[n - k]) % MOD;
}

Основная часть программы. Читаем входные данные.

scanf("%d %d", &k, &n);

Заполняем массивы факториалов $f a c t$ и $f a c t in v$ .

fact[0] = 1;
for (i = 1; i < MAX; i++)
  fact[i] = (fact[i - 1] * i) % MOD;

factinv[0] = 1;
for (i = 1; i < MAX; i++)
   factinv[i] = inverse(fact[i], MOD);

Вычисляем ответ по формуле $\sum_{i = 0}^{k} C_{k}^{i} \cdot C_{k - i}^{n - 2 i}$ . Значение биномиального коэффициента $C_{n}^{k}$ считаем равным нулю, если выполняется одно из трех условий: $k < 0$ , $n < 0$ или $k > n$ .

res = 0;
for (i = 0; i <= k; i++)
{
  if (n - 2 * i < 0 || k - i < 0 || n - 2 * i > k - i) continue;
  res = (res + Cnk(k, i) * Cnk(k - i, n - 2 * i)) % MOD;
}

Выводим ответ.

printf("%lld\n", res);

Дано дерево с $n$ вершинами, где вершина с номером $i (1 \leq i \leq n)$ содержит $c_{i}$ монет. Выберите такое подмножество вершин, чтобы никакие две из них не были смежными (то есть не соединены ребром), а сумма монет в выбранных вершинах была максимальной.

Вход. Первая строка содержит количество вершин $n (1 \leq n \leq 1 0^{5})$ в дереве. Каждая из следующих $n - 1$ строк содержит два целых числа $u$ и $v (1 \leq u, v \leq n)$ , задающих ребро в дереве. Последняя строка содержит $n$ неотрицательных целых чисел $c_{1}, ... c_{n}$ — количество монет в каждой вершине дерева.

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

Открыть задачу

Пусть $v$ — вершина дерева. Обозначим через:

$d p_{1} (v)$ наибольшую сумму монет, которую можно собрать из поддерева с корнем $v$ , если монеты в вершине $v$ мы берем.
$d p_{2} (v)$ наибольшую сумму монет, которую можно собрать из поддерева с корнем $v$ , если монеты в вершине $v$ мы не берем.

Тогда ответом на задачу будет $ma x (d p_{1} (1), d p_{2} (1))$ , если взять первую вершину за корень дерева.

Определим рекурсивно приведенные функции:

Если монеты в вершине $v$ мы берем, то брать монеты из ее сыновей нельзя:

d p_{1} (v) = c_{v} + i = 1 \sum k d p_{2} (t o_{i}), где t o_{1}, ..., t o_{k} - сыновья вершины v .

Если монеты в вершине $v$ мы не берем, то из её сыновей можно или брать, или не брать монеты. Из этих двух вариантов следует выбрать тот, в котором сумма монет максимальна:

d p_{2} (v) = i = 1 \sum k ma x (d p_{1} (t o_{i}), d p_{2} (t o_{i})), где t o_{1}, ..., t o_{k} - сыновья вершины v .

Если $v$ — лист дерева с $c_{v}$ монетами, то функции в нем примут следующие значения: $d p_{1} (v) = c_{v}$ и $d p_{2} (v) = 0$ .

Пример

Расставим метки $d p_{1} (v) / d p_{2} (v)$ на вершинах деревьев из примеров.

Для первого примера имеем:

$d p_{1} (1) = c_{1} + d p_{2} (2) + d p_{2} (3) = 1 + 3 + 0 = 4$ ;
$d p_{2} (1) = ma x (d p_{1} (2), d p_{2} (2)) + ma x (d p_{1} (3), d p_{2} (3)) = 5 + 7 = 12$ ;
$d p_{1} (2) = c_{2} + d p_{2} (4) + d p_{2} (5) = 5 + 0 + 0 = 5$ ;
$d p_{2} (2) = ma x (d p_{1} (4), d p_{2} (4)) + ma x (d p_{1} (5), d p_{2} (5)) = 1 + 2 = 3$ ;

Для второго примера имеем:

$d p 1 (1) = c_{1} + d p_{2} (2) + d p_{2} (3) = 3 + 11 + 0 = 14$ ;
$d p_{2} (1) = ma x (d p_{1} (2), d p_{2} (2)) + ma x (d p_{1} (3), d p_{2} (3)) = 11 + 5 = 16$ ;
$d p_{1} (2) = c_{2} + d p_{2} (4) + d p_{2} (5) = 7 + 0 + 0 = 7$ ;
$d p_{2} (2) = ma x (d p_{1} (4), d p_{2} (4)) + ma x (d p_{1} (5), d p_{2} (5)) = 10 + 1 = 11$ ;

Упражнение

Расставьте метки $d p_{1} (v) / d p_{2} (v)$ на вершинах дерева:

Объявим рабочие массивы.

vector<vector<int> > g;
vector<int> dp1, dp2, cost;

Функция dfs реализует поиск в глубину. Вычисляем значения $d p_{1}$ и $d p_{2}$ во всех вершинах дерева.

void dfs(int v, int p = -1)
{
  dp1[v] = cost[v];
  dp2[v] = 0;

  for (int to : g[v])
  {
    if (to == p) continue;

    dfs(to, v);

    dp1[v] += dp2[to];
    dp2[v] += max(dp1[to], dp2[to]);
  }
}

Основная часть программы. Читаем дерево и массив монет.

scanf("%d",&n);
g.resize(n+1);
for(i = 1; i < n; i++)
{
  scanf("%d %d",&u,&v);
  g[u].push_back(v);
  g[v].push_back(u);
}

dp1.resize(n+1); dp2.resize(n+1);
cost.resize(n+1);
for(i = 1; i <= n; i++)
  scanf("%d",&cost[i]);

Пусть корень дерева находится в вершине $1$ . Запускаем из нее поиск в глубину.

dfs(1);

Вычисляем и выводим ответ.

ans = max(dp1[1], dp2[1]);
printf("%d\n",ans);

Дан прямоугольник размером $a \times b$ . Ваша задача — разрезать его на квадраты. За один ход можно выбрать один из прямоугольников и разрезать его на два новых прямоугольника так, чтобы все длины сторон оставались целыми числами. Определите наименьшее количество ходов, которое потребуется для этого.

Вход. Два целых числа $a$ и $b (1 \leq a, b \leq 500)$ .

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

Открыть задачу

Пусть $f (a, b)$ — наименьшее количество ходов, за которое прямоугольник размером $a \times b$ можно разрезать на квадраты. Будем хранить это значение в ячейке $d p [a] [b]$ .

Если прямоугольник уже является квадратом $(a = b)$ , разрезы не требуются, поэтому $f (a, a) = 0$ .

Прямоугольник $a \times b$ можно разрезать либо вертикальным, либо горизонтальным разрезом. Рассмотрим сначала вертикальный разрез.

При вертикальном разрезе прямоугольник $a \times b$ делится на два прямоугольника: $a \times k$ и $a \times (b - k)$ . Чтобы полученные прямоугольники были невырожденными, должно выполняться условие $1 \leq k < b$ . Затем рекурсивно решаем задачу для каждого из этих двух прямоугольников и добавляем $1$ к результату, так как мы сделали один вертикальный разрез. При этом выбираем такое $k$ , для которого сумма $f (a, k) + f (a, b - k) + 1$ наименьшая:

f (a, b) = 1 \leq k < b min (f (a, k) + f (a, b - k)) + 1

Для случая горизонтального разреза получаем аналогичную формулу:

f (a, b) = 1 \leq k < a min (f (k, b) + f (a - k, b) + 1

Остаётся выбрать минимальное значение среди этих двух вариантов.

Пример

В первом тесте требуется выполнить $3$ разреза:

Первым разрезом прямоугольник $3 \times 5$ разделяется на $3 \times 3$ и $2 \times 3$ ;
Вторым разрезом прямоугольник $2 \times 3$ разделяется на $2 \times 2$ и $2 \times 1$ ;
Третьим разрезом прямоугольник $2 \times 1$ разделяется на $1 \times 1$ и $1 \times 1$ ;

Объявим константы и рабочий массив.

#define MAX 501
#define INF 0x3F3F3F3F

int dp[MAX][MAX];

Функция $f (a, b)$ возвращает наименьшее количество ходов, за которое прямоугольник размером $a \times b$ можно разрезать на квадраты.

int f(int a, int b)
{

Если прямоугольник уже является квадратом $(a = b)$ , разрезы не требуются.

  if (a == b) return 0;

Если значение $f (a, b)$ еще не вычислено $(d p [a] [b] = \infty)$ , то вычисляем его.

  if (dp[a][b] == INF)
  {

Выполняем все возможные вертикальные разрезы.

    for (int k = 1; k < b; k++)
      dp[a][b] = min(dp[a][b], f(a, k) + f(a, b - k) + 1);

Выполняем все возможные горизонтальные разрезы.

    for (int k = 1; k < a; k++)
      dp[a][b] = min(dp[a][b], f(k, b) + f(a - k, b) + 1);
  }

Возвращаем результат $f (a, b) = d p [a] [b]$ .

  return dp[a][b];
}

Основная часть программы. Читаем размеры прямоугольника $a$ и $b$ .

scanf("%d %d", &a, &b);

Вычисляем и выводим ответ.

memset(dp, 0x3F, sizeof(dp));
printf("%d\n", f(a, b));

Закон Джунглей гласит совершенно ясно: каждый волк, заведя семью, может покинуть свою Стаю. Но как только его волчата подрастут и окрепнут, он обязан привести их на Совет Стаи, который обычно собирается раз в месяц, в полнолуние, и представить всем остальным волкам.

Отец Волк дождался, пока его волчата немного подросли и начали понемногу бегать, и в одну из тех ночей, когда собиралась Стая, повёл их — вместе с Маугли и Матерью Волчицей — на Скалу Совета. Это была вершина холма, усеянная крупными валунами, за которыми могла укрыться целая сотня волков. Акела, большой серый волк-одиночка, избранный вожаком всей Стаи за силу и ловкость, взывал со своей скалы:

— Закон вам известен, закон вам известен! Смотрите же, волки!

Отец Волк вытолкнул на середину круга Лягушонка Маугли. Тот сел на землю, засмеялся и стал играть палочками.

Задачу он придумал себе простую: нужно было из этих палочек сложить прямоугольник максимальной площади — при этом использовать все палочки было не обязательно.

Вход. Первая строка содержит количество палочек $n (1 \leq n \leq 16)$ . Во второй строке заданы их длины — натуральные числа в диапазоне от $1$ до $1 0^{8}$ .

Выход. Выведите максимальную площадь прямоугольника, который можно сложить из данного набора палочек, или число $0$ , если сложить прямоугольник невозможно.

Открыть задачу

Пусть $S$ — данное множество палочек. Необходимо найти два непересекающихся подмножества $A$ и $B$ из $S$ , такие, что палочки каждого из них можно разбить на два подмножества с равной суммой длин.

Для каждого подмножества $ma s k \subseteq S$ вычислим сумму длин его палочек и запишем в $s u m [ma s k]$ .

Переберём все подмножества $I \subset S$ . Для каждого подмножества $I$ переберём все его подмножества $J \subset I$ . Если существует такое $J$ , что $2 \cdot s u m [J] = s u m [I]$ (то есть суммарная длина палочек в $J$ вдвое меньше суммы длин всех палочек из $I$ ), то подмножество $I$ можно использовать в качестве противоположных сторон прямоугольника. В этом случае установим $c an [I] = t r u e$ .

Вся описанная процедура выполняется за $O (3^{n})$ .

Переберём все подмножества множества палочек. Если для некоторого множества $I$ существует подмножество $J \subset I$ такое, что $c an [J] = t r u e$ и $c an [I x or J] = t r u e$ (то есть множества $J$ и $I x or J$ не пересекаются), то тем самым получаем одно из возможных распределений палочек между горизонтальными и вертикальными сторонами прямоугольника.

Длины сторон такого прямоугольника равны $s u m [J] /2$ и $s u m [I x or J] /2$ . Среди всех найденных вариантов выбираем прямоугольник с максимальной площадью.

Длины палочек хранятся в массиве $a$ . Для каждого подмножества палочек $ma s k$ сохраняем их суммарную длину в массиве $s u m [ma s k]$ . Значение $c an [ma s k]$ устанавливаем в $t r u e$ , если множество $ma s k$ можно разделить на два подмножества с равной суммой длин — им будут соответствовать противоположные стороны прямоугольника.

#define MAX 16
int a[MAX];
int sum[1 << MAX];
bool can[1 << MAX];

Основная часть программы. Читаем входные данные.

scanf("%d",&n);
for (i = 0; i < n; i++)
  scanf("%d", &a[i]);

Переберём все подмножества палочек и вычислим суммарную длину каждого из них.

for (i = 0; i < 1 << n; i++)
  for (j = 0; j < n; j++)
    if (i & (1 << j)) sum[i] += a[j];

Затем переберём все возможные подмножества множества палочек. Если для некоторого множества $I$ существует подмножество $J \subset I$ такое, что суммарная длина палочек в $J$ вдвое меньше суммарной длины палочек в $I$ , то установим $c an [I] = t r u e$ . В этом случае палочки из множества $I$ можно использовать как противоположные стороны прямоугольника.

for (i = 1; i < 1 << n; i++) 
{
  int s = sum[i];
  for (j = i; j > 0; j = (j - 1) & i)
    if (sum[j] * 2 == s) 
    {
      can[i] = true;
      break;
    }
}

Переберём все подмножества множества палочек. Если для некоторого множества $I$ существует подмножество $J \subset I$ такое, что $c an [J] = t r u e$ и $c an [I x or J] = t r u e$ , то получаем одно из возможных распределений палочек между горизонтальными и вертикальными сторонами прямоугольника. Длины сторон такого прямоугольника равны $s u m [J] /2$ и $s u m [I x or J] /2$ .

res = 0;
for (i = 1; i < 1 << n; i++)
  for (j = i; j > 0; j = (j - 1) & i)
    if (can[j] && can[i ^ j])
      res = max(res, sum[j] / 2 * 1LL * sum[i ^ j] / 2);

Выводим площадь найденного прямоугольника максимального размера.

printf("%lld\n",res);

Однажды детектив Сайкат расследовал дело об убийстве. На месте преступления он обнаружил лестницу, на каждой ступеньке которой было написано число. Детектив счел это подозрительным и решил запомнить все числа, встреченные на пути. Вскоре он заметил закономерность: для каждого числа на лестнице он записывал сумму всех ранее встреченных чисел, которые были меньше текущего.

Вам необходимо найти сумму всех чисел, записанных детективом в его дневнике.

Вход. Первая строка содержит число $t (t \leq 10)$ — количество тестов. Далее следуют $2 t$ строк. В первой из них указано число $n (1 \leq n \leq 1 0^{5})$ — количество ступенек. В следующей строке записаны $n$ чисел — значения, нанесенные на ступеньки. Все числа находятся в диапазоне от $0$ до $1 0^{6}$ .

Выход. Для каждого теста выведите в отдельной строке итоговую сумму.

Открыть задачу

Числа, записанные на ступеньках, являются целыми и находятся в диапазоне от $0$ до $1 0^{6}$ включительно. Построим дерево Фенвика на массиве $a$ длины $1 0^{6} + 1$ (индексы массива изменяются от $0$ до $1 0^{6}$ включительно), изначально заполненном нулями.

Каждый раз, когда детектив проходит ступеньку со значением $v a l u e$ , увеличим $a_{v a l u e}$ на $v a l u e$ . При этом в дневнике он запишет сумму:

a_{0} + a_{1} + a_{2} + ... + a_{v a l u e - 1}

С учетом ограничений на входные данные, все вычисления следует выполнять в $64$ -битовом целочисленном типе.

Пример

Смоделируем записи детектива на приведённом примере. Индексация массива начинается с $0$ . Числа, записанные детективом, указаны под стрелками.

Сумма чисел, записанных в дневнике детектива, равна

0 + 1 + 1 + 9 + 4 = 15

Пусть максимальный размер массива равен $M A X$ . Создадим дерево Фенвика $F e n w i c k$ .

#define MAX 1000001
vector<long long> Fenwick;

Функция Summa0_i вычисляет значение суммы $a_{0} + a_{1} + ... + a_{i}$ .

long long Summma0_i(int i)
{
  long long result = 0;
  for (; i >= 0; i = (i & (i + 1)) - 1)
    result += Fenwick[i];
  return result;
}

Функция IncElement увеличивает значение элемента: $a_{i} = a_{i} + d e lt a$ .

void IncElement(int i, int delta)
{
  for (; i < MAX; i = (i | (i+1)))
    Fenwick[i] += delta;
}

Основная часть программы. Читаем входные данные.

scanf("%d",&tests);
while (tests--)
{
  scanf("%d",&n);

Заполняем массив $F e n w i c k$ нулями.

  Fenwick.assign(MAX,0);

Искомую сумму, записанную в дневнике детектива, будем подсчитывать в переменной $s u m$ .

  sum = 0;

Последовательно обрабатываем числа, записанные на ступеньках.

  for (i = 0; i < n; i++)
  {

Для каждого значения $v a l u e$ , записанного на ступеньке, увеличиваем $a_{v a l u e}$ на $v a l u e$ , а также вычисляем сумму всех ранее встреченных чисел, меньших $v a l u e$ . Эта сумма равна $a_{0} + a_{1} + a_{2} + ... + a_{v a l u e - 1}$ .

    scanf("%d",&value);
    IncElement(value, value);
    sum += Summma0_i(value - 1);
  }

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

  printf("%lld\n",sum);
}

Амин и Мурад решили создать игровой сервер "Майнкрафт".

На торжественное открытие сервера они пригласили $k$ гостей. Гости живут в разных городах, и при подключении к серверу (в зависимости от их местоположения) будут испытывать определённую задержку (ping). Осознав возможные трудности, Амин и Мурад решили выбрать самое оптимальное место для размещения сервера.

Имеется $n$ городов, пронумерованных от $1$ до $n$ , и $m$ двусторонних каналов связи между ними. Подключение к серверу возможно только по этим каналам. С их помощью можно установить соединение между любыми двумя городами. При этом между двумя городами может быть не более одного прямого канала связи, а ни один город не соединён каналом сам с собой. Для каждого канала указана задержка передачи $w_{i}$ .

Задержкой соединения между каким-либо городом и сервером считается минимально возможная сумма задержек по каналам на пути из этого города до сервера.

Амин и Мурад хотят выбрать такой город для размещения сервера, чтобы суммарная задержка соединений всех гостей была минимальной. Если сервер размещён в том же городе, где живёт гость, то для него задержка считается равной нулю.

Если существует несколько городов с одинаковой минимальной суммарной задержкой, то Амин и Мурад выберут город с наименьшим номером.

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

Вход. В первой строке заданы три целых числа $n (1 \leq n \leq 1 0^{4}), m (1 \leq m \leq 4 * 1 0^{4}), k (1 \leq k \leq 100)$ — количество городов, количество каналов связи и количество гостей соответственно. Во второй строке записаны $k$ различных чисел $c_{i} (1 \leq c_{i} \leq n)$ — номера городов, в которых живут гости.

В каждой из следующих $m$ строк даны три целых числа $u_{i}, v_{i}, w_{i} (1 \leq u_{i}, v_{i} \leq n)$ — описание двустороннего канала связи между городами $u_{i}$ и $v_{i}$ с задержкой $w_{i} (1 \leq w_{i} \leq 1 0^{4})$ .

Выход. Выведите два целых числа — номер города, в котором будет размещён сервер, и суммарную задержку соединений всех гостей к этому серверу.

Открыть задачу

Поскольку $n \leq 1 0^{4}$ , для представления графа воспользуемся списком смежности.

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

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

Пример

Граф, приведенный в примере, имеет следующий вид:

Запустим алгоритм Дейкстры из вершин, в которых проживают гости: $1, 2$ и $5$ . Для каждой из этих вершин определим кратчайшие расстояния до всех остальных городов.

Затем для каждой вершины графа найдём сумму расстояний до всех городов с гостями. Минимальная сумма расстояний равна $13$ , и она достигается в вершине с наименьшим номером $2$ .

Таким образом, сервер следует разместить в городе $2$ . Суммарное расстояние от него до городов, где проживают гости, составляет $5 + 0 + 8 = 13$ .

Объявим константу бесконечность.

#define INF 0x3F3F3F3F

Структура $e d g e$ будет хранить информацию о ребре: вершину $n o d e$ , в которую ведёт ребро, и вес $d i s t$ этого ребра.

struct edge
{
  int node, dist;
  edge(int node, int dist) : node(node), dist(dist) {}
};

Объявим компаратор для сортировки пар $(n o d e, d i s t)$ по убыванию значения $d i s t$ .

bool operator< (edge a, edge b)
{
  return a.dist > b.dist;
}

Объявим список смежности для представления графа.

vector<vector<edge> > g;

Функция Dijkstra реализует алгоритм Дейкстры. На вход она принимает граф $g$ и начальную вершину $s t a r t$ . Возвращаемым значением является массив $d$ , где $d [i]$ содержит кратчайшее расстояние от вершины $s t a r t$ до вершины $i$ .

void Dijkstra(vector<vector<edge> >& g, vector<int>& d, int start)
{
  priority_queue<edge> pq;
  pq.push(edge(start, 0));

  d = vector<int>(n + 1, INF);
  d[start] = 0;

  while (!pq.empty())
  {
    edge e = pq.top(); pq.pop();
    int v = e.node;

    if (e.dist > d[v]) continue;

    for (auto e : g[v])
    {
      int to = e.node;
      int cost = e.dist;
      if (d[v] + cost < d[to])
      {
        d[to] = d[v] + cost;
        pq.push(edge(to, d[to]));
      }
    }
  }
}

Основная часть программы. Читаем входные данные.

scanf("%d %d %d", &n, &m, &k);
c.resize(k);
for (i = 0; i < k; i++)
  scanf("%d", &c[i]);

Читаем входной взвешенный граф.

g.resize(n + 1);
for (i = 0; i < m; i++)
{
  scanf("%d %d %d", &a, &b, &w);
  g[a].push_back(edge(b, w));
  g[b].push_back(edge(a, w));
}

Запускаем алгоритм Дейкстры из городов, в которых проживают гости.

dp.resize(n + 1);
for (i = 0; i < k; i++)
{
  Dijkstra(g, dist, c[i]);

  for (j = 1; j <= n; j++)
   dp[j] += dist[j];
}

На данный момент $d p [i]$ содержит сумму кратчайших расстояний от вершины $i$ до всех городов, в которых находятся гости. Остаётся найти минимальное значение среди элементов массива $d p$ и вывести соответствующий ответ. Переменная $pt r$ хранит наименьший номер вершины, в которой следует разместить сервер.

res = INF;
for (i = 1; i <= n; i++)
{
  if (dp[i] < res)
  {
    res = dp[i];
    ptr = i;
  }
}

Выводим ответ.

printf("%d %d\n", ptr, dp[ptr]);

Комментарии

Пока что ничего

Будьте первым, кто начнет обсуждение!

Войти

Загрузка

Момент, получаем данные с сервера