•Разборы•6 дней назад

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

Проект "Средний вес школьника школы" решили выполнить Мамед и Самед.

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

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

Вход. Веса учеников заданы в нескольких строках, разделённых пробелами (одним или несколькими) или символом конца строки. Чтение данных продолжается до конца ввода.

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

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

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

int w[1000];

Читаем входные данные. Количество входных чисел подсчитываем в переменной $n$ .

n = 0;
while (scanf("%d", &w[n]) == 1) n++;

Находим наименьший $min$ и наибольший $ma x$ элемент массива.

min = max = w[0];
for (i = 0; i < n; i++)
{
  if (w[i] > max) max = w[i];
  if (w[i] < min) min = w[i];
}

Вычисляем сумму весов $s$ и количество учеников $c n t$ , исключив учеников с наибольшим и наименьшим весом.

s = cnt = 0;
for (i = 0; i < n; i++)
  if (w[i] != min && w[i] != max)
  {
    s = s + w[i];
    cnt++;
 }

Выводим ответ, округленный до целого числа килограммов.

printf("%.0lf\n", 1.0 * s / cnt);

Реализация алгоритма — min_element, max_element

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

vector<int> w;

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

while (scanf("%d", &x) == 1)
  w.push_back(x);

Находим наименьший $min_e l$ и наибольший $ma x_e l$ элемент массива.

min_el = *min_element(w.begin(), w.end());
max_el = *max_element(w.begin(), w.end());

Вычисляем сумму весов $s$ и количество учеников $c n t$ , исключив учеников с наибольшим и наименьшим весом.

s = cnt = 0;
for (int x : w)
  if (x != min_el && x != max_el) 
  {
    s += x;
    cnt++;
  }

Выводим ответ, округленный до целого числа килограммов.

printf("%.0lf\n", 1.0 * s / cnt);

Python реализация

import sys

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

lst = []
for line in sys.stdin:
  lst.extend(map(int,line.split()))

Находим наименьший $min_e l$ и наибольший $ma x_e l$ элемент списка.

max_el = max(lst)
min_el = min(lst)

Вычисляем сумму весов $s$ и количество учеников $c n t$ , исключив учеников с наибольшим и наименьшим весом.

cnt = sum = 0
for x in lst:
  if x != max_el and x != min_el:
    cnt += 1
    sum += x

Вычисляем и выводим ответ, округленный до целого числа килограммов.

res = round(sum / cnt)
print(res)

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

Ферма Джона построена вдоль одной длинной прямой дороги, поэтому любое место на его ферме можно описать положением на этой дороге (точкой на числовой прямой). Телепорт описывается двумя числами $x$ и $y$ , где навоз, доставленный в точку $x$ , может быть мгновенно доставлен в точку $y$ , и наоборот.

Фермер Джон хочет транспортировать навоз из места $a$ в место $b$ , и он построил телепорт, который может быть полезен во время этого процесса (если телепорт не поможет, то его можно не использовать). Помогите ему определить минимальное общее расстояние, на которое следует перевезти навоз с помощью трактора.

Вход. Одна строка содержит четыре целых числа: $a$ и $b$ , описывающие начальную и конечную точки, за которыми следуют $x$ и $y$ , описывающие телепорт. Все позиции являются целыми числами в диапазоне $0...100$ , и они не обязательно отличаются друг от друга.

Выход. Выведите одно целое число — минимальное расстояние, на которое фермер Джон должен возить навоз на своем тракторе.

Пример. В этом примере лучшая стратегия — перетащить навоз из положения $3$ в положение $2$ , телепортировать его в положение $8$ , а затем перетащить в положение $10$ . Общее расстояние перевозки трактором составит $1 + 2 = 3$ .

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

У фермера Джона имеются следующие варианты передвижения навоза:

Напрямую от $a$ до $b$ , будет пройдено расстояние $∣ a - b ∣$ ;
Везти на тракторе от $a$ до $x$ , телепортировать от $x$ до $y$ , и снова везти на тракторе от $y$ до $b$ . Суммарно трактором будет пройдено расстояние $∣ a - x ∣ + ∣ b - y ∣$ ;
Везти на тракторе от $a$ до $y$ , телепортировать от $y$ до $x$ , и снова везти на тракторе от $x$ до $b$ . Суммарно трактором будет пройдено расстояние $∣ a - y ∣ + ∣ b - x ∣$ ;

Наименьшее из этих трех значений и будет ответом.

Пример

В приведенном примере лучшая стратегия — переместить навоз из позиции $3$ в позицию $2$ , телепортировать его в позицию $8$ , а затем переместить в позицию $10$ . Общее расстояние, которое проедет трактор, составит $1 + 2 = 3$ .

Найдите такое число от $1$ до $n$ включительно, для которого в разложении на простые множители количество множителей максимально. Если таких чисел несколько, выведите наибольшее из них.

Например, для $n = 7$ ответом будет число $6$ , так как оно является наибольшим числом, разложение которого на простые множители включает два множителя: $2$ и $3$ .

Вход. Одно целое число $n (1 \leq n \leq 2^{31} - 1)$ .

Выход. Выведите одно искомое число.

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

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

Например, попробуем искать его в виде $2^{k}$ . Найдем наибольшее $k$ , для которого $2^{k} \leq n$ . Количество делителей числа $2^{k}$ равно $d (2^{k}) = k + 1$ .

Затем рассмотрим число $2^{k - 1} \cdot 3$ . Количество его делителей равно $d (2^{k - 1} \cdot 3) = k \cdot 2$ , что больше, чем $k + 1$ .

Таким образом:

Если $2^{k - 1} \cdot 3 \leq n$ , то искомым числом будет $2^{k - 1} \cdot 3$ ;
В противном случае ответом будет $2^{k}$ .

Отдельно рассмотрим случай $n = 1$ . Для этого значения ответом будет $1$ .

Пример

Пусть $n = 100$ . Наибольшей степенью двойки, не большей $100$ , будет $2^{6} = 64$ . Число $64$ имеет $d (64) = 6 + 1 = 7$ делителей.

Теперь рассмотрим число $2^{5} \cdot 3 = 96$ . Количество его делителей равно:

d (96) = (5 + 1) * (1 + 1) = 6 * 2 = 12

Так как число $96$ не превышает $100$ , оно будет искомым для $n = 100$ .

Объявим двумерный массив для запоминания значений функции: $d p [x] [y] = f (x, y)$ .

long long dp[51][51];

Реализация рекурсивной функции f с запоминанием.

long long f(int x, int y)
{
  if (x <= 0 || y <= 0) return 0;
  if (dp[x][y] != -1) return dp[x][y];
  if (x <= y) return dp[x][y] = f(x - 1, y - 2) + f(x - 2, y - 1) + 2;
  return dp[x][y] = f(x - 2, y - 2) + 1;
}

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

scanf("%d %d",&x,&y);

Инициализируем ячейки массива $d p$ значением $- 1$ .

memset(dp,-1,sizeof(dp));

Вызываем функцию $f (x, y)$ и выводим ее значение.

printf("%lld\n",f(x,y));

Однажды $n$ человек ( $n$ четное) встретились на площади и устроили два хоровода. Найдите количество способов, которыми $n$ человек могут водить два хоровода, если каждый хоровод должен состоять ровно из $n /2$ человек. Каждый человек должен принадлежать ровно к одному из этих двух хороводов.

Хоровод — танцевальный круг, состоящий из $1$ и более человек. Два хоровода называются неразличимыми (равными), если один можно преобразовать в другой выбором первого участника. Например, хороводы $[1, 3, 4, 2], [4, 2, 1, 3]$ и $[2, 1, 3, 4]$ неразличимы.

Вход. Одно четное целое число $n (2 \leq n \leq 20)$ .

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

Пример. Например, при $n = 4$ количество способов равно $3$ :

первый раунд танца — $[1, 2]$ , второй — $[3, 4]$ ;
первый раунд танца — $[2, 4]$ , второй — $[3, 1]$ ;
первый раунд танца — $[4, 1]$ , второй — $[3, 2]$ .

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

Сначала следует выбрать $n /2$ людей для первого хоровода. Это можно сделать $C_{n}^{n /2}$ способами. Подсчитаем количество способов, которыми можно поставить людей внутри одного хоровода. Зафиксируем того кто будет первым, после чего остальных $n /2 - 1$ людей можно расставить произвольным образом, а именно $(n /2 - 1)!$ способами. Количество способов составить два хоровода равно

C_{n}^{n /2} \cdot (n /2 - 1)! \cdot (n /2 - 1)! / 2

Деление на $2$ необходимо чтобы не различать пары хороводов $(x, y)$ и $(y, x)$ . Например, при $n = 4$ разделения на хороводы $([1, 2], [3, 4])$ и $([3, 4], [1, 2])$ будем считать одинаковыми.

Упростим указанную формулу и получим ответ:

\frac{n !}{( n /2 )! \cdot ( n /2 )!} \cdot (n /2 - 1)! \cdot (n /2 - 1)! / 2 = \frac{1}{2} \cdot \frac{n !}{( n /2 ) \cdot ( n /2 )} = \frac{2 \cdot n !}{n \cdot n} = \frac{2 \cdot ( n - 1 )!}{n}

Пример

Например, при $n = 4$ количество способов равно $3$ :

первый раунд танца — $[1, 2]$ , второй — $[3, 4]$ ;
первый раунд танца — $[2, 4]$ , второй — $[3, 1]$ ;
первый раунд танца — $[4, 1]$ , второй — $[3, 2]$ .

По формуле для $n = 4$ ответ равен

\frac{2 \cdot ( 4 - 1 )!}{4} = \frac{12}{4} = 3

Построим все различимые хороводы для $n = 4$ . На первом месте поставим участника $1$ . На остальных трех местах можно поставить любую перестановку из трех остальных участников.

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

[1, 4, 3, 2], [2, 1, 4, 3], [3, 2, 1, 4], [4, 3, 2, 1]

Имеется $4! = 24$ хороводов из $4$ участников. Однако различимых хороводов для $n = 4$ имеется $3! = 6$ .

Вам дана матрица размером $n \times m$ , в которой выделены $k$ специальных ячеек. Необходимо добраться из клетки $(1, 1)$ в клетку $(n, m)$ . Разрешается двигаться только вправо или вниз.

Каждая из $k$ специальных ячеек обладает определённой силой. $i$ -я специальная ячейка имеет силу $p_{i}$ , и при прохождении через неё вы получаете эту силу.

Требуется найти суммарную силу, которую можно набрать, рассматривая все возможные пути от $(1, 1)$ до $(n, m)$ .

Заметим, что:

Сила пути определяется как сумма значений $p_{i}$ всех специальных ячеек, посещённых на этом пути.
Обычные ячейки, не являющиеся специальными, имеют силу, равную нулю.

Вход. Первая строка содержит целое число $t$ — количество тестов.

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

Каждая из следующих $k$ строк содержит три числа $x_{i}, y_{i} (1 \leq x_{i} \leq n, 1 \leq y_{i} \leq m)$ и $p_{i} (1 \leq p_{i} \leq 1 0^{5})$ , где $(x_{i}, y_{i})$ — координаты специальной ячейки, а $p_{i}$ — её сила.

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

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

Пусть $w a ys (x, y)$ обозначает количество путей на матрице из клетки $(1, 1)$ в клетку $(1 + x, 1 + y)$ . Тогда

w a ys (x, y) = C_{x + y}^{x} = C_{x + y}^{y}

Количество путей из клетки $(1, 1)$ в клетку $(n, m)$ , проходящих через специальную ячейку $(x, y)$ , равно $w a ys (x - 1, y - 1) \cdot w a ys (n - x, m - y)$ . Умножив это число на $p$ , получаем суммарную силу всех путей, проходящих через ячейку $(x, y)$ .

Остается просуммировать силы всех путей, проходящих через специальные ячейки. Ответ будет равен сумме:

i = 1 \sum k w a ys (x_{i} - 1, y_{i} - 1) \cdot w a ys (n - x_{i}, m - y_{i}) \cdot p_{i}

Пример

В приведенном примере заданы $k = 2$ специальные ячейки.

Ровно один путь проходит через ячейку с силой $4$ .
Ровно один путь проходит через ячейку с силой $7$ .

Таким образом, общая сила равна $4 + 7 = 11$ .

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

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

f a c t [n] = n! m o d 1000000007 f a c t in v [n] = n!^{- 1} m o d 1000000007

#define MAX 800001
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;
}

Функция ways вычисляет количество путей на решетке размером $n \times m$ из клетки $(0, 0)$ в клетку $(n, m)$ . Так как любой путь между этими точками имеет длину $n + m$ и содержит ровно $m$ горизонтальных сегментов, число путей равно $C_{n + m}^{m}$ .

ll ways(int n, int m)
{
  return Cnk(n + m, m);
}

Основная часть программы. Заполняем массивы факториалов $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);

Последовательно обрабатываем $t es t s$ тестов.

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

Читаем данные текущего теста.

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

Суммарную полученную силу сохраняем в переменной $res$ .

  res = 0;

Обрабатываем $k$ специальных ячеек.

  for (i = 0; i < k; i++)
  {
    scanf("%d %d %d", &x, &y, &p);
    res = (res + (ways(x - 1, y - 1) * 
                  ways(n - x, m - y)) % MOD * p) % MOD;
  }

Выводим ответ для текущего теста.

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

В стране Смешариков — новый сезон! Теперь все герои отправляются в поход. Для этого им необходимо встретиться в одной точке, а уже оттуда двинуться покорять мир. Лосяш, координирующий действия Смешариков, знает координаты всех участников похода. Помогите ему определить, какое минимальное количество секунд потребуется, чтобы все Смешарики собрались вместе.

Изначально каждый Смешарик находится в узле целочисленной сетки. Если Смешарик стоит в точке $(x, y)$ , то за одну секунду он может переместиться в одну из точек $(x, y + 1)$ , $(x + 1, y)$ , $(x - 1, y)$ , $(x, y - 1)$ или остаться на месте.

Вход. В первой строке задано одно целое число $n (1 \leq n \leq 200000)$ — количество Смешариков. В следующих $n$ строках указаны их начальные позиции. Каждая позиция задаётся двумя целыми числами $x_{i}$ и $y_{i} (- 1 0^{18} \leq x_{i}, y_{i} \leq 1 0^{18})$ .

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

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

Пусть Смешарик находится в точке $(x, y)$ . Тогда за $t$ секунд он сможет оказаться в любой целочисленной точке ромба, как показано на рисунке.

Нужно найти наименьшее натуральное $t$ , при котором все ромбы соответствующего размера для каждого Смешарика будут иметь хотя бы одну общую целочисленную точку. Рассмотрим третий тест и изобразим ромбы для трёх Смешариков при $t = 1, 2, 3$ .

При $t = 3$ смешарики, например, могут встретиться в точке $(0, 3)$ или $(1, 2)$ .

Повернем систему координат на $- 45°$ относительно начала координат. При таком преобразовании ромбы перейдут в квадраты. Выведем формулы поворота:

z^{'} = z e^{- i \frac{π}{4}}

Или в декартовых координатах:

x^{'} + i y^{'} = (x + i y) \cdot (cos (\frac{π}{4}) - i sin (\frac{π}{4}))

{x^{'} = x \frac{2}{2} + y \frac{2}{2} y^{'} = - x \frac{2}{2} + y \frac{2}{2}

Избавимся от иррациональности, растянув изображение в $2$ раз. Для этого воспользуемся следующим преобразованием:

{x^{'} = x + y y^{'} = - x + y

Преобразуем наши три точки:

$(0, 0) \to (0, 0)$
$(0, 3) \to (3, 3)$
$(3, 3) \to (6, 0)$

Найдем координаты прямоугольника, содержащего все точки $(x_{i}^{'}, y_{i}^{'})$ — преобразованные начальные координаты смешариков. Обозначим:

$mi n_{x} = min (x_{i}^{'}); ma x_{x} = ma x (x_{i}^{'})$ ;
$mi n_{y} = min (y_{i}^{'}); ma x_{y} = ma x (y_{i}^{'})$ ;

Тогда прямоугольник с противоположными углами $(mi n_{x}, mi n_{y})$ и $(ma x_{x}, ma x_{y})$ содержит все точки $(x_{i}^{'}, y_{i}^{'})$ . При этом он является минимальным по площади прямоугольником, стороны которого параллельны осям координат.

В нашем примере таким прямоугольником будет $(0, 0) - (6, 3)$ .

Точкой сбора смешариков $(re s_{x}, re s_{y})$ будет центр этого прямоугольника, то есть точка с координатами

(re s_{x}, re s_{y}) = (\frac{mi n _{x} + ma x _{x}}{2}, \frac{mi n _{y} + ma x _{y}}{2})

Теперь нужно найти минимальное время, за которое все Смешарики смогут добраться из своих точек $(x_{i}^{'}, y_{i}^{'})$ в точку $(re s_{x}, re s_{y})$ . Для повернутого ромба (квадрата в новой системе координат) расстояние от точки $(x_{i}^{'}, y_{i}^{'})$ до $(re s_{x}, re s_{y})$ вычисляется по формуле:

ma x (∣ x_{i}^{'} - re s_{x} ∣, ∣ y_{i}^{'} - re s_{y} ∣)

Таким образом, все Смешарики смогут собраться в точке $(re s_{x}, re s_{y})$ за время, равное максимальному из этих расстояний:

1 \leq i \leq n max (ma x (∣ x_{i}^{'} - re s_{x} ∣, ∣ y_{i}^{'} - re s_{y} ∣))

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

typedef long long ll;
#define INFL (ll)4e18

Входные точки будем хранить в массиве $in p$ .

vector<pair<ll, ll>> inp;

Функция calc вычисляет расстояние от точки $(x, y)$ до самого удалённого смешарика. Преобразованные координаты смешариков находятся в массиве $in p$ .

ll calc(ll x, ll y)
{
  ll res = 0;
  for (auto p : inp)
    res = max(res, max(abs(p.first - x), abs(p.second - y)));
  return res;
}

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

cin >> n;
minx = INFL; maxx = -INFL; miny = INFL; maxy = -INFL;
for (i = 0; i < n; i++)
{

Читаем исходные координаты смешарика $(x, y)$ . Выполняем поворот координатной плоскости на $- 45°$ и сохраняем полученные координаты в массиве $in p$ .

  cin >> x >> y;
  nx = x + y;
  ny = -x + y;
  inp.push_back({ nx, ny });

После этого находим координаты прямоугольника с противоположными углами $(mi n_{x}, mi n_{y})$ и $(ma x_{x}, ma x_{y})$ , который содержит все точки $(x_{i}^{'}, y_{i}^{'})$ — преобразованные координаты смешариков.

  minx = min(minx, nx);
  maxx = max(maxx, nx);
  miny = min(miny, ny);
  maxy = max(maxy, ny);
}

Определяем точку сбора смешариков $(re s_{x}, re s_{y})$ — центр прямоугольника.

resx = (minx + maxx) / 2;
resy = (miny + maxy) / 2;

Вычисляем и выводим минимальное время, необходимое для того, чтобы все смешарики смогли добраться из своих точек $(x_{i}^{'}, y_{i}^{'})$ до точки $(re s_{x}, re s_{y})$ .

ans = calc(resx, resy);
cout << ans << "\n";

Нурлашко, Нурбакыт и Жора — последние воины древнего клана ниндзя, ведущего борьбу против тирании императора Рэна. После сокрушительного поражения в открытом бою они решили разделить своё войско на три лагеря и перейти к партизанской войне.

Однако нелепые реформы императора Рэна установили строгие правила: по дорогам между городами можно двигаться только в одном направлении. Более того, направления были выбраны так, что невозможно, пройдя по нескольким дорогам, вернуться в исходный город.

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

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

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

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

В графе требуется найти любые три вершины, которые не расположены на одном пути.

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

Если же при выполнении алгоритма Кана очередь на каждом шаге содержит не более одной вершины, это означает, что все вершины графа расположены на одном пути.

Пример

Графы из тестовых примеров имеют следующий вид:

В первом примере все три вершины лежат на одном пути.
Во втором примере существует три вершины, которые не находятся на одном пути.

Объявим структуры данных. Входной граф представлен списком смежности $g$ , а входящие степени вершин сохраняются в массиве $I n De g ree$ .

vector<vector<int> > g;
vector<int> InDegree;
deque<int> q;

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

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

Для каждого ребра $(a, b)$ увеличиваем значение $I n De g ree [b]$ на $1$ .

  InDegree[b]++;
}

Все вершины с нулевой входящей степенью помещаем в очередь $q$ .

for (i = 1; i < InDegree.size(); i++)
  if (InDegree[i] == 0) q.push_back(i);

Искомые три вершины сохраним в переменные $x, y, z$ .

x = y = -1;

Продолжаем выполнение алгоритма до тех пор, пока очередь $q$ не пуста.

while (!q.empty())
{

Если в очереди одновременно находится более одной вершины, это означает, что ответ найден.

  if (q.size() > 1)
  {
    x = q[0];
    y = q[1];
    break;
  }

Извлекаем вершину $v$ из очереди — она станет текущей вершиной в порядке топологической сортировки.

  v = q.front(); q.pop_front();

Удаляем из графа все ребра вида $(v, t o)$ . Для каждого такого ребра уменьшаем входящую степень вершины $t o$ . Если степень вершины $t o$ становится нулевой, помещаем её в очередь.

  for (int to : g[v])
  {
    InDegree[to]--;
    if (InDegree[to] == 0) q.push_back(to);
  }
}

Алгоритм Кана завершён. Если значение $x$ по-прежнему равно $- 1$ , это означает, что решения не существует.

if (x == -1)
  printf("-1\n");
else
{

Если решение существует, в качестве $z$ выбираем минимальную вершину, отличную от $x$ и $y$ .

  z = 1;
  while (z == x || z == y) z++;
    printf("%d %d %d\n", x, y, z);
}

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

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

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

Среди прочих задач Фернандо интересует, какое минимальное количество новых бунгало необходимо построить и покрасить соответствующим образом, чтобы завершить проект в соответствии с задуманной симметрией.

Вход. В первой строке задано целое число $n (1 \leq n \leq 4 \cdot 1 0^{5})$ — количество уже построенных бунгало.

Во второй строке дана последовательность их цветов в порядке от начала улицы у озера. Это строка длиной $n$ , состоящая из строчных латинских букв от ' $a$ ' до ' $z$ ', каждая из которых обозначает определённый цвет.

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

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

К данной строке необходимо добавить минимальное количество символов, чтобы она стала палиндромом. Для этого нужно найти наибольший палиндром среди всех её суффиксов, затем взять префикс до начала этого палиндрома, развернуть его и приписать к исходной строке.

Например, наибольшим палиндромным суффиксом строки $ab c x q x$ является $x q x$ . Префикс до него — $ab c$ , переворачиваем его (получаем $c ba$ ) и приписываем к исходной строке.

Рассмотрим строку $rs = re v erse (s) + s$ . Вычислим для нее $z$ -функцию.

Найдём наименьший индекс $i$ (такой, что $i \geq n$ ), для которого выполняется равенство $i + z_{i} = 2 n$ . При этом значение $z_{i}$ будет максимальным среди таких индексов. Минимальное количество символов, которое необходимо дописать к исходной строке, чтобы получить палиндром, равно $n - z_{i}$ .

Для строки " $ab c x q x$ " (длина $n = 6$ ) нужный индекс $i = 9$ , так как $9 + z_{9} = 9 + 3 = 12 = 2 * 6$ .

Пример

Рассмотрим первый пример. Вычислим $z$ -функцию для строки $re v erse (s) + s = " bba " + " abb " = " bbaabb "$ .

Наименьшим индексом $i (i \geq n)$ , для которого выполняется равенство $i + z_{i} = 2 n$ , является $i = 4$ . Действительно: $4 + z_{4} = 4 + 2 = 6 = 2 * 3$ . Тогда ответ равен $n - z_{i} = 3 - 2 = 1$ . То есть, к строке " $abb$ " достаточно добавить один символ ' $a$ ', чтобы получить палиндром " $abba$ ".

Функция z строит и возвращает $z$ -функцию для строки $s$ .

vector<int> zfun(string s)
{
  int i, l, r, len = s.size();
  vector<int> z(len, 0);
  l = r = 0;
  for (i = 1; i < len; i++)
  {
    if (i <= r) z[i] = min(r - i + 1, z[i - l]);
    while (i + z[i] < len && s[z[i]] == s[i + z[i]]) z[i]++;
    if (i + z[i] - 1 > r)
    {
      l = i;
      r = i + z[i] - 1;
    }
  }
  return z;
}

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

cin >> n;
cin >> s;

Строим строку $rs = re v erse (s) + s$ .

rs = s;
reverse(rs.begin(), rs.end());
rs += s;

Вычисляем $z$ -функцию строки $rs$ .

z = zfun(rs);

Находим наименьший индекс $i (i \geq n)$ , для которого выполняется равенство $i + z_{i} = 2 n$ . Среди всех таких индексов значение $z_{i}$ будет наибольшим.

for (i = n; i < rs.size(); i++)
  if (i + z[i] == 2 * n)
  {

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

    cout << n - z[i] << endl;
    break;
  }

Вдоль трассы Алматы–Тараз расположены nnn населённых пунктов, пронумерованных от $1$ до $n$ . С наступлением зимы $m$ неизвестных торговцев привезли из некого аула вязаные шапки и начали продавать их в этих населённых пунктах.

Торговцы следуют двум принципам:

Они не торгуют в одном месте более одного дня.
Каждый день они увеличивают цену на шапку.

Более формально каждый $i$ -ый торговец:

Начинает торговлю в населенном пункте $l_{i}$ со стартовой ценой $x_{i}$ за одну шапку.
Каждый день переходит в соседний населённый пункт: если накануне он торговал в пункте $j$ , то сегодня торгует в пункте $j + 1$ .
Каждый день увеличивает цену на $1$ : если вчера цена составляла $x$ , то сегодня она равна $x + 1$ .
Завершает торговлю в населённом пункте $r_{i}$ (при этом в $r_{i}$ он ещё продаёт).

Для каждого населённого пункта определите максимальную цену на одну шапку за всю историю торговли.

Вход. В первой строке заданы два целых числа $n (1 \leq n \leq 3 \cdot 1 0^{5})$ и $m (1 \leq m \leq 3 \cdot 1 0^{5})$ — количество населенных пунктов и количество торговцев соответственно.

Далее следуют $m$ строк, каждая из которых содержит три целых числа $l_{i}, r_{i} (1 \leq l_{i} \leq r_{i} \leq n)$ и $x_{i} (1 \leq x_{i} \leq 1 0^{9})$ — начальный и конечный населённые пункты, а также стартовая цена на шапку для $i$ -го торговца.

Выход. Выведите $n$ целых чисел, где $i$ -ое число обозначает максимальную цену на одну шапку за всю историю торговли в $i$ -ом населённом пункте. Если в каком-то пункте торговля не велась, выведите $0$ .

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

Построим дерево отрезков на диапазоне $[1; n]$ и изначально обнулим его. Пусть торговец продавал шапки в населенных пунктах $[l_{i}; r_{i}]$ , начиная с цены $p_{i}$ . Разобьем отрезок $[l_{i}; r_{i}]$ на фундаментальные отрезки $[l x_{1}; r y_{1}], [l x_{2}; r y_{2}], ..., [l x_{k}; r y_{k}]$ . Тогда в вершину, соответствующую отрезку $[l x_{q}; r y_{q}] (1 \leq q \leq k)$ , занесем число

p_{i} + сумма длин отрезков [l x_{t}; r y_{t}], для всех t < q .

Например, пусть $n = 5$ , и первая торговля охватывает города с номерами от $2$ до $5$ , начиная с цены $4$ . Тогда отрезок $[2; 5]$ распадется на фундаментальные: $[2; 2], [3; 3], [4; 5]$ . После обработки первой операции дерево отрезков будет выглядеть следующим образом:

Если фундаментальный отрезок $[a; b]$ содержит значение $p$ , это означает что:

торговец продавал шапки во всех городах от $a$ до $b$ .
в городе $a$ шапка продавалась по цене $p$ , в городе $a + 1$ по цене $p + 1$ , и так далее, вплоть до города $b$ , где её цена составляла $p + b - a$ .

Рассмотрим процедуру обработки запроса $[l e f t; r i g h t]$ (отрезка, на котором торговец ведёт торговлю) на диапазоне $[lp os; r p os]$ , если начальная цена шапки равна $x$ .

В левом подотрезке торговец будет продавать шапки в $l e n = min (mi d, r i g h t) - l e f t + 1$ городах, начиная с цены $x$ . В правом подотрезке первая цена шапки в городе, куда придёт торговец, составит $x + l e n$ . Таким образом, на отрезке с номерами $[ma x (l e f t, mi d + 1), r i g h t]$ торговля начнётся с цены $x + l e n$ . Однако если $l e n < 0$ (что возможно, если весь отрезок запроса находится в правом подотрезке), следует положить $l e n = 0$ .

Рассмотрим отрезок $[a; b]$ , у которого есть два подотрезка: $[a; m]$ и $[m + 1; b]$ . Если в городе $a$ торговец продал шапку по цене $p$ , то в городе $m + 1$ её цена составит $p + m + 1 - a$ .

В процессе обработки запросов реализуем проталкивание значений, поддерживающее максимум.

Для вывода ответа следует пройти по дереву, протолкнуть все значения до листов и вывести их.

Пример

Рассмотрим выполнение двух запросов, приведённых в примере. Разобьём отрезки запросов на фундаментальные:

$[1; 3] = [1; 3]$ ;
$[2; 4] = [2; 2] + [3; 3] + [4; 4]$ .

Объявим массив $S e g T ree$ для хранения дерева отрезков.

#define MAX 300010
long long SegTree[4*MAX];

Функция Push выполняет проталкивание значения из вершины $v$ в ее потомков.

void Push(int v, int lpos, int mid, int rpos)
{
  if (SegTree[v])
  {
    SegTree[2 * v] = max(SegTree[2 * v], SegTree[v]);
    SegTree[2 * v + 1] = max(SegTree[2 * v + 1], 
                             SegTree[v] + mid - lpos + 1);
    SegTree[v] = 0;
  }
}

Функция Update выполняет продажу шапок на промежутке $[l e f t; r i g h t]$ , начиная с цены $x$ .

void Update(int v, int lpos, int rpos, int left, int right, 
            long long x)
{
  if (left > right) return;
  if ((lpos == left) && (rpos == right))
    SegTree[v] = max(SegTree[v], x);
  else
  {
    int mid = (lpos + rpos) / 2;
    Push(v, lpos, mid, rpos);

    int len = min(mid, right) - left + 1;
    if (len < 0) len = 0;
    Update(2 * v, lpos, mid, left, min(mid, right), x);
    Update(2 * v + 1, mid + 1, rpos, max(left, mid + 1), 
                                         right, x + len);
    }
}

Функция PrintResult проталкивает значения из внутренних вершин до листьев и выводит итоговое состояние массива.

void PrintResult(int v, int lpos, int rpos)
{
  if (lpos == rpos)
    printf("%lld ", SegTree[v]);
  else
  {
    int mid = (lpos + rpos) / 2;
    Push(v, lpos, mid, rpos);

    PrintResult(2 * v, lpos, mid);
    PrintResult(2 * v + 1, mid + 1, rpos);
  }
}

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

scanf("%d %d", &n, &m);
memset(SegTree,0,sizeof(SegTree));

Обрабатываем $m$ запросов.

for(i = 0; i < m; i++)
{
  scanf("%d %d %lld", &l, &r, &x);
  Update(1,1,n,l,r,x);
}

Выводим результат.

PrintResult(1,1,n);
printf("\n");

Комментарии

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

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

Войти

Загрузка

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