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

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

Ещё в древности египтяне знали, что треугольник со сторонами $3$ , $4$ и $5$ является прямоугольным, а его прямой угол — наибольшим. Определите, обладают ли тем же свойством и другие треугольники.

Вход. Состоит из нескольких тестов, оканчивающихся строкой $000$ . Каждый тест содержит три натуральных числа — длины сторон очередного треугольника. Все числа не превышают $30000$ .

Выход. Для каждого теста выведите в отдельной строке "right", если треугольник является прямоугольным, или "wrong" в противном случае.

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

В Хогвартсе проходит традиционная ежегодная олимпиада по теории магии среди младшекурсников. Завхозу школы, Аргусу Филчу, поручено распределить студентов по аудиториям.

Каждый факультет выставил на олимпиаду своих лучших учеников: от Гриффиндора участвуют $g$ студентов, от Слизерина — $s$ студентов, Пуффендуй представляет $h$ студентов, а Когтевран — $r$ студентов. В распоряжении Филча имеется $m$ аудиторий.

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

Назовём рассадку оптимальной, если она минимизирует максимальное количество студентов одного факультета в любой аудитории.

Определите, какое минимальное количество студентов одного факультета Филчу всё же придётся посадить в одну аудиторию даже при оптимальной рассадке.

Вход. Первая строка содержит четыре целых числа $g, s, h$ и $r (1 \leq g, s, h, r \leq 1000)$ — количество учеников, представляющих факультеты Гриффиндор, Слизерин, Пуффендуй и Когтевран соответственно.

Во второй строке задано одно целое число $m (1 \leq m \leq 1000)$ — количество доступных аудиторий.

Выход. Выведите одно целое число — минимальное возможное количество студентов одного факультета в одной аудитории при оптимальной рассадке.

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

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

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

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

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

Элементы внутри каждой группы могут быть выведены в любом порядке. Каждое число от $1$ до $n$ должно быть включено ровно в одну из групп.

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

Заметим, что если числа $n$ и $n - 3$ поместить в одну группу, а $n - 1$ и $n - 2$ поместить в другую (сумма чисел в каждой группе будет одинаковой), то задача сведётся к аналогичной задаче меньшей размерности, а именно к разбиению на группы чисел $1, 2, ..., n - 4$ .

Для $n \leq 3$ числа распределим по группам следующим образом:

Если остаются три числа $1, 2, 3$ , то их можно разделить на две группы: ${1, 2}$ и ${3}$ .
Если остаются два числа $1, 2$ , то разделим их на группы: ${1}$ и ${2}$ . Разность сумм чисел в группах составит $1$ .
Если остается одно число $1$ , то его можно поместить в любую группу. Разность сумм чисел в группах составит $1$ .

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

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

Пример

Пусть $n = 10$ . Числа в группы размещаем следующим образом:

Пусть $n = 11$ . Числа в группы размещаем следующим образом:

Читаем входное значение $n$ .

scanf("%d", &n);

Устанавливаем начальные суммы чисел в группах $s_{1}$ и $s_{2}$ равными $0$ .

s1 = s2 = 0;

Перебираем числа от $n$ до $1$ по убыванию.

for (i = n; i > 0; i--)

Если $s_{1} < s_{2}$ , то заносим число $i$ в первую группу. Иначе заносим число $i$ во вторую группу.

  if (s1 < s2)
  {
    s1 += i;
    a.push_back(i);
  }
  else
  {
    s2 += i;
    b.push_back(i);
  }

Выводим размеры групп.

printf("%d %d\n", a.size(), b.size());

Выводим числа первой группы.

for (i = 0; i < a.size(); i++)
  printf("%d ", a[i]);
printf("\n");

Выводим числа второй группы.

for (i = 0; i < b.size(); i++)
  printf("%d ", b[i]);
printf("\n");

Для хранения значений $A_{i} (i < 5000000)$ объявим массив $m$ .

#define MAX 5000000
long long m[MAX];

Функция f вычисляет значение $A_{n}$ .

long long f(long long n, long long p, long long q, 
            long long x, long long y)
{

Если $n \leq 0$ , то $A_{n} = 1$ .

  if (n <= 0) return 1;

Если $n < 5000000$ и значение $m [n]$ уже вычислено (отлично от нуля), то возвращаем его.

  if ((n < MAX) && m[n]) return m[n];

Выполняем рекурсивное вычисление значения $A_{n}$ в соответствии с формулой, приведённой в условии задачи.

  long long temp = f(n/p-x,p,q,x,y) + f(n/q-y,p,q,x,y);

Если $n < 5000000$ , сохраняем результат $A_{n}$ в массиве $m$ , чтобы избежать повторных вычислений в будущем.

  if (n < MAX) m[n] = temp;
  return temp;
}

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

scanf("%lld %lld %lld %lld %lld",&n,&p,&q,&x,&y);

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

res = f(n,p,q,x,y);
printf("%lld\n",res);

По заданным двум целым числам $n$ и $m$ найдите такое действительное число $a$ , что значение $f (1/2 + a)$ является максимальным. Известно, что

f (t) = mi n_{i, j \in Z} ∣ \frac{i}{n} - \frac{j}{m} + t ∣

Можно доказать, что максимальное значение функции $f (t)$ рационально. Выведите его в виде несократимой дроби.

Вход. Содержит не более $1 0^{4}$ тестов. Каждый тест состоит из одной строки, содержащей два целых числа $n$ и $m (1 \leq n, m \leq 1 0^{9})$ .

Выход. Для каждого теста выведите максимальное значение $f (1/2 + a)$ в виде несократимой дроби $p / q$ , где $q > 0$ .

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

Рассмотрим, какие значения принимает выражение $f (i, j) = i / n - j / m$ , где $i, j \in Z$ при фиксированных $n$ и $m$ . Например, $f (n, m) = n / n - m / m = 0$ .

Рассмотрим, например, функцию $f (i, j) = i /3 - j /5$ . Тогда

f (i, j) = \frac{5 i - 3 j}{15}

Согласно расширенному алгоритму Евклида, всегда существуют такие целые $i$ и $j$ , что $i /3 - j /5 = 1$ . Следовательно, наименьшим положительным значением, которое может принимать выражение $i /3 - j /5$ , является $1/15$ . Отсюда следует, что это выражение может принимать все возможные значения вида $k /15$ , где $k \in Z$ .

Теорема. Если $f (i, j) = i / n - j / m$ , то эта функция принимает значения вида $k / НОК (n, m)$ , где $k \in Z$ .

Доказательство. Действительно,

f (i, j) = i / n - j / m = \frac{i \cdot m - j \cdot n}{n \cdot m} = \frac{( i \cdot m ) / НОД ( n , m ) - ( j \cdot n ) / НОД ( n , m )}{( n \cdot m ) / НОД ( n , m )} = \frac{i \cdot ( m / НОД ( n , m )) - j \cdot ( n / НОД ( n , m ))}{НОК ( n , m )}

Поскольку числа $m / НОД (n, m)$ и $n / НОД (n, m)$ являются взаимно простыми, то всегда существуют такие $i$ и $j$ , что числитель дроби равен $1$ . Следовательно, функция $f (i, j)$ может принимать все возможные значения вида $k / НОК (n, m)$ , где $k \in Z$ .

Теперь рассмотрим исходную функцию

f (t) = mi n_{i, j \in Z} ∣ \frac{i}{n} - \frac{j}{m} + t ∣

Ее значения — расстояния от точки $t$ до ближайшей точки вида $k / НОК (n, m), k \in Z$ . Для максимизации функции $f (t)$ значение $t$ следует выбрать таким образом, чтобы оно находилось точно посередине между соседними точками $k / НОК (n, m)$ и $(k + 1) / НОК (n, m)$ , где $k$ — целое число. Значение функции в такой точке равно $1/2 \cdot НОК (n, m)$ , что и будет ответом.

Пример

Пусть $f (t) = mi n_{i, j \in Z} ∣ \frac{i}{3} - \frac{j}{5} + t ∣$ . Очевидно, что $f (0) = 0$ . Равенство $f (1/15) = 0$ справедливо, так как существуют такие $i$ и $j$ , что $i /3 - j /5 = - 1/15$ (например, $i = 1, j = 2$ ). Из этого также следует, что $f (k /15) = 0$ , где $k \in Z$ .

Однако $f (k /15 + 1/30) = 1/30$ , и это будет наибольшим значением функции, так как точка $k /15 + 1/30$ находится на максимальном расстоянии от нулей функции.

Задан массив из $n$ целых чисел. Сколькими способами можно выбрать подмножество его элементов так, чтобы их сумма была равна $s$ ?

Вход. В первой строке заданы два целых числа: $n (1 \leq n \leq 40)$ — размер массива и $s (1 \leq s \leq 1 0^{9})$ — требуемая сумма.

Во второй строке заданы $n$ целых чисел: $t_{1}, t_{2}, \dots, t_{n} (1 \leq t_{i} \leq 1 0^{9})$ — элементы массива.

Выход. Выведите одно число — количество способов выбрать подмножество элементов массива, сумма которых равна $s$ .

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

Разобьем входной массив на две равные части: $t_{1}, t_{2}, ..., t_{n /2}$ и $t_{n /2 + 1}, t_{n /2 + 2}, ..., t_{n}$ . Первую часть сохраним в массив $a$ , вторую — в массив $b$ .

Сначала решим задачу для последовательности $a$ . Переберем все ее возможные подмножества (их будет не более $2^{20}$ ). Для каждого подмножества вычислим сумму его элементов $s$ , и для каждой такой суммы увеличим значение $m [s]$ на $1$ . В качестве структуры данных $m$ можно использовать, например, unordered_map. Таким образом, $m [s]$ будет содержать количество способов выбрать подмножество из массива $a$ с суммой элементов, равной $s$ .

Затем переберём все подмножества массива $b$ . Пусть $s u m$ — сумма элементов одного из таких подмножеств. Если объединить это подмножество со всеми подмножествами массива $a$ , сумма элементов которых равна $s - s u m$ , то в результате получится подмножество исходного массива, сумма элементов которого равна $s$ .

Пример

Рассмотрим второй пример. Разобьем входную последовательность на две части:

$a = (1, 3, 2)$ ,
$b = (2, 1, 4)$

Переберем все подмножества множества $a = {1, 3, 2}$ :

${1} : s u m = 1, m [1] + +$ ;	${1, 2} : s u m = 3, m [3] + +$ ;
${3} : s u m = 3, m [3] + +$ ;	${3, 2} : s u m = 5, m [5] + +$ ;
${2} : s u m = 2, m [2] + +$ ;	${1, 3, 2} : s u m = 6, m [6] + +$ ;
${1, 3} : s u m = 4, m [4] + +$ ;	${} : s u m = 0, m [0] + +$ ;

Структура $m$ после обработки будет содержать следующие значения:

Теперь переберем все подмножества множества $b = {2, 1, 4}$ . В данном примере искомая сумма равна $s = 7$ . Для каждой суммы $s u m$ , соответствующей подмножеству $b$ , будем прибавлять к ответу значение $m [s - s u m]$ .

${2} : s u m = 2, m [7 - 2] = m [5] = 1$ ;
${1} : s u m = 1, m [7 - 1] = m [6] = 1$ ;
${4} : s u m = 4, m [7 - 4] = m [3] = 2$ ;
${2, 1} : s u m = 3, m [7 - 3] = m [4] = 1$ ;
${2, 4} : s u m = 6, m [7 - 6] = m [1] = 1$ ;
${1, 4} : s u m = 5, m [7 - 5] = m [2] = 1$ ;
${2, 1, 4} : s u m = 7, m [7 - 7] = m [0] = 1$ ;
${} : s u m = 0, m [7 - 0] = m [7] = 0$ ;

Искомая сумма равна $1 + 1 + 2 + 1 + 1 + 1 + 1 + 0 = 8$ , что и является ответом.

Объявим рабочие структуры данных.

vector<int> a, b;
unordered_map<long long, long long> m;

Читаем входные данные. Первую половину последовательности заносим в массив $a$ , вторую — в массив $b$ .

scanf("%d %d", &n, &s);
a.resize(n / 2);
for (i = 0; i < n / 2; i++)
  scanf("%d", &a[i]);

b.resize(n - n / 2);
for (i = n / 2; i < n; i++)
  scanf("%d", &b[i - n / 2]);

Перебираем все подмножества последовательности $a$ и вычисляем суммы их элементов. В структуре unordered_map сохраняем, сколько раз каждая сумма встречается среди этих подмножеств. Если $s u m$ — сумма текущего подмножества, то значение $m [s u m]$ увеличиваем на $1$ .

for (i = 0; i < (1 << a.size()); i++)
{
  sum = 0;

Переменная $i$ содержит битовую маску текущего подмножества $а$ . Сумма его элементов вычисляется в переменной $s u m$ .

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

Для каждой найденной суммы sum увеличиваем значение $m [s u m]$ на $1$ .

  m[sum]++;
}

Количество способов получить сумму $s$ из элементов исходного массива подсчитываем в переменной $res$ .

res = 0;

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

for (i = 0; i < (1 << b.size()); i++)
{
  sum = 0;

Переменная $i$ содержит битовую маску текущего подмножества $b$ . Сумма элементов этого подмножества вычисляется в переменной $s u m$ .

  for (j = 0; j < b.size(); j++)
    if (i & (1 << j)) sum += b[j];

Если объединить текущее подмножество множества $b$ , сумма элементов которого равна $s u m$ , со всеми подмножествами множества $a$ , сумма которых равна $s - s u m$ , то в результате получится подмножество исходного массива, сумма элементов которого равна $s$ .

  if (m.count(s - sum) > 0) res += m[s - sum];
}

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

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

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

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

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

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

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

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

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

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

Каждому натуральному числу $a_{i}$ поставим в соответствие отрезок $[s_{i}; e_{i}]$ , где $s_{i}$ — позиция, на которой $a_{i}$ встречается впервые, а $e_{i}$ — позиция, на которой $a_{i}$ встречается в последний раз.

Пусть $res$ — наибольшее возможное количество непересекающихся отрезков. Это значение можно найти с помощью алгоритма "выбора заявок", что означает, что каждый из оставшихся отрезков пересекается хотя бы с одним из выбранных. После этого нужно выполнить описанную процедуру над генами, которым эти отрезки соответствуют.

Если $k$ — общее количество построенных отрезков. Тогда ответом на задачу будет значение $k - res$ .

Пример

Для приведенного примера отрезки будут иметь вид (нумерация позиций начинается с нуля):

для $1 : [0; 4]$ ;
для $2 : [1; 6]$ ;
для $3 : [3; 5]$ ;
для $4 : [7; 7]$ ;
для $5 : [8; 8]$ ;

Отсортируем отрезки по координате конца:

[0; 4], [3; 5], [1; 6], [7; 7], [8; 8]

Максимальное количество непересекающихся отрезков равно $3$ . Например, можно выбрать отрезки $[0; 4], [7; 7], [8; 8]$ . Для генов, соответствующих оставшимся отрезкам, следует выполнить процедуру, описанную в условии задачи. К таким генам относятся $2$ и $3$ . Две перестановки можно выполнить, например, следующим образом:

Пусть $M A X$ — максимальное возможное количество геномов во входной последовательности.

#define MAX 100001

Вектор пар $v$ хранит отрезки $[s_{i}; e_{i}]$ .

vector<pair<int, int> > v;
int s[MAX], e[MAX];

Читаем входные данные. Инициализируем $s_{i} = - 1, e_{i} = - 1$ .

scanf("%d", &n);
memset(s, -1, sizeof(s));
memset(e, -1, sizeof(e));

for (i = 0; i < n; i++)
{
  scanf("%d", &x);

Если число $x$ встречается впервые, то его позицию во входной последовательности записываем в $s_{x}$ .

  if (s[x] == -1) s[x] = i;

Если число $x$ встречается не в первый раз, то его позицию записываем в $e_{x}$ , считая, что $x$ встречается в последний раз.

  if (i > e[x]) e[x] = i;
}

Все построенные отрезки заносим в вектор $v$ .

for (i = 1; i <= n; i++) // numbers 1..n
  if (s[i] != -1) v.push_back(make_pair(e[i], s[i]));

Отрезки заносятся в вектор в обратном порядке (в виде $[e_{i}; s_{i}]$ ), чтобы по умолчанию сортировка отрезков происходила в порядке возрастания их концов.

sort(v.begin(), v.end());

Находим максимальное количество $res$ непересекающихся отрезков.

i = res = 0;
while (i < v.size())
{

Добавляем $i$ -й отрезок во множество непересекающихся отрезков. Переменная $t e m p$ содержит конец этого отрезка (назовём его текущим отрезком).

  res++; temp = v[i++].first; // end

Пока начало следующего отрезка меньше конца текущего, пропускаем такой отрезок, так как он пересекается с текущим.

  while (i < v.size() && v[i].second < temp) i++;
}

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

printf("%d\n", v.size() - res);

Армия Речи Посполитой направляется из города Кострома в деревню Домнино. Во главе армии стоят два гетмана — Стефан и Константин.

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

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

Иван Сусанин, являющийся тайным агентом, старается не вызывать подозрений. Поэтому каждый раз он выбирает такую дорогу (для Стефана) и такую тропу (для Константина), чтобы кратчайшее расстояние до деревни Домнино по соответствующей карте строго уменьшалось.

Помогите Ивану определить, какой максимальной длины может быть маршрут до деревни Домнино.

Вход. Первая строка содержит три целых числа $n, s$ и $t (2 \leq n \leq 1000, 1 \leq s, t \leq n)$ — количество деревень в Костромской области, номер начальной деревни и номер деревни Домнино соответственно. Деревни пронумерованы от $1$ до $n$ . Гарантируется, что $s \neq = t$ .

Затем следуют два блока, каждый из которых описывает карту: первый — карту Стефана, второй — карту Константина.

Первая строка каждого блока содержит целое число $m (n - 1 \leq m \leq 1 0^{5})$ — количество дорог или троп. Каждая из следующих $m$ строк содержит три целых числа $a, b$ и $l (1 \leq a, b \leq n; 1 \leq l \leq 1 0^{6})$ , описывающих соединение между деревнями $a$ и $b$ длиной $l$ .

Передвигаться по дорогам и тропам можно в любом направлении. Гарантируется, что по каждой карте можно добраться из любой деревни в любую другую. Армия начинает движение вечером из деревни $s$ , проходя одну дорогу за ночь и одну тропу за день.

Выход. Выведите одно целое число — максимально возможную длину маршрута до деревни Домнино (учитывая чередование дороги и тропы). Если Иван Сусанин может водить армию бесконечно, не приводя её в Домнино, выведите " $- 1$ ".

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

Построим два графа: граф дорог $g [0]$ и граф троп $g [1]$ . Далее вычислим кратчайшие расстояния от деревни Домнино $t$ до всех деревень:

По карте Стефана: $d [0] [i]$ — минимальное расстояние от $t$ до деревни $i$ ;
По карте Константина: $d [1] [i]$ — минимальное расстояние от $t$ до деревни $i$ ;

Затем рассмотрим граф, вершинами которого являются пары $(v, p a r i t y)$ :

$v$ — номер деревни;
$p a r i t y = 0$ (ночь, передвижение по дорогам), $p a r i t y = 1$ (день, передвижение по тропам).

Армия начинает путь вечером из начальной деревни, двигаясь ночью по дороге $(p a r i t y = 0)$ . Запускаем поиск в глубину из вершины $(s, 0)$ по следующим правилам:

из $(v, 0)$ (ночь) идём по дороге в $(u, 1)$ , если $d [0] [u] < d [0] [v]$ ;
из $(v, 1)$ (день) идём по тропе в $(u, 0)$ , если $d [1] [u] < d [1] [v]$ .

Находясь в состоянии $(v, p a r i t y)$ , перебираем только допустимые переходы, то есть такие, при которых расстояние до Домнино строго уменьшается. Среди них ищем путь максимальной длины.

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

При выполнении поиска в глубину будем поддерживать следующую динамику:

$d p [t y p e] [v]$ — максимальная длина пути от $v$ до $t$ , начиная с типа $t y p e$ .

Для каждого допустимого перехода:

Рекурсивно вызываем $df s (t o, t y p e \oplus 1)$ — переход в противоположную фазу.
Обновляем значение $d p [t y p e] [v]$ :

d p [t y p e] [v] = ma x (d p [t y p e] [v], d p [t y p e \oplus 1] [t o] + w e i g h t);

Таким образом, мы выбираем наилучший следующий ход, который приводит к максимальной суммарной длине пути. Это аналог стандартного поиска самого длинного пути в DAG (ориентированном ациклическом графе), где направление рёбер определяется уменьшением кратчайшего расстояния.

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

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

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

#define INF 2e18
#define MAXN 1005

Объявим используемые структуры данных:

$g [0]$ и $g [1]$ — списки смежности для графов дорог и троп соответственно.
$d [0]$ и $d [1]$ — кратчайшие расстояния от деревни Домнино $t$ до всех остальных деревень.
$d p [0]$ и $d p [1]$ — максимальная длина пути от вершины $v$ до $t$ , если стартовать из $v$ по дороге $(t y p e = 0)$ или по тропе $(t y p e = 1)$ .
$u se d [0]$ и $u se d [1]$ — метки вершин при обходе в глубину для графов дорог и троп соответственно.

vector<pair<int, int>> g[2][MAXN];
long long d[2][MAXN];
long long dp[2][MAXN];
int used[2][MAXN];

Функция dijkstra вычисляет кратчайшие расстояния от деревни Домнино $t$ до всех остальных деревень либо по дорогам $(t y p e = 0)$ , либо по тропам $(t y p e = 1)$ .

void dijkstra(int type)
{
  for (int i = 1; i <= n; i++)
    d[type][i] = INF;

  d[type][t] = 0;

  priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
  pq.push({ 0, t });

  while (!pq.empty())
  {
    pair<long long, int> top = pq.top();
    pq.pop();

    long long dist = top.first;
    int v = top.second;

    if (dist > d[type][v]) continue;

    for (auto edge : g[type][v])
    {
      int to = edge.first;
      int w = edge.second;

      if (d[type][to] > d[type][v] + w)
      {
        d[type][to] = d[type][v] + w;
        pq.push({ d[type][to], to });
      }
    }
  }
}

Функция dfs выполняет поиск в глубину и находит самый длинный путь при движении по чередующимся картам, начиная из деревни $v$ по дороге $(t y p e = 0)$ или по тропе $(t y p e = 0)$ . Если при таком чередующемся движении возникает возможность попасть в цикл, функция возвращает $- 1$ .

void dfs(int v, int type)
{

Вершина $v$ в графе $g [t y p e]$ становится серой.

  used[type][v] = 1;

Инициализируем динамику.

  dp[type][v] = 0;

Перебираем ребра, исходящие из вершины $v$ в графе $g [t y p e]$ .

  for (auto edge : g[type][v])
  {
    int to = edge.first;
    int weight = edge.second;

Переход из вершины $v$ в вершину $t o$ возможен только в том случае, если расстояние от $t o$ до Домнино меньше, чем расстояние от $v$ до Домнино.

    if (d[type][to] < d[type][v])
    {

Если вершина $t o$ в графе $g [t y p e \oplus 1]$ уже находится в процессе обхода (помечена как "серая"), значит, обнаружен цикл — возвращаем $- 1$ .

      if (used[type ^ 1][to] == 1)
      {
        cout << -1 << endl;
        exit(0);
      }

Если вершина $t o$ в графе $g [t y p e \oplus 1]$ еще не посещена, продолжаем из нее поиск в глубину.

      if (used[type ^ 1][to] == 0)
        dfs(to, type ^ 1);

После обработки всех допустимых переходов пересчитываем динамику, выбирая максимальную длину пути от вершины $v$ в графе $g [t y p e]$ до Домнино.

      dp[type][v] = max(dp[type][v], dp[type ^ 1][to] + weight);
    }
  }

Вершина $v$ в графе $g [t y p e]$ помечается черной.

  used[type][v] = 2;
}

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

scanf("%d %d %d", &n, &s, &t);
scanf("%d", &m1);
for (i = 0; i < m1; i++)
{
  scanf("%d %d %d", &a, &b, &len);
  g[0][a].push_back({ b, len });
  g[0][b].push_back({ a, len });
}

scanf("%d", &m2);
for (i = 0; i < m2; i++)
{
  scanf("%d %d %d", &a, &b, &len);
  g[1][a].push_back({ b, len });
  g[1][b].push_back({ a, len });
}

Вычисляем кратчайшие расстояния от деревни Домнино $t$ до всех остальных деревень — отдельно для карты дорог и для карты троп.

dijkstra(0);
dijkstra(1);

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

dfs(s, 0);

Выводим ответ. Стартовая точка — деревня $s$ , движение начинается по дороге.

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

Алиса — фокусница, и она придумала новый трюк. У неё есть $n$ карточек с различными числами от $1$ до $n$ , написанными на них. Сначала она просит одного из зрителей перетасовать колоду и выложить карты в ряд. Допустим, что на $i$ -й карте слева стоит число $a_{i}$ .

Затем Алиса выбирает две перестановки $p$ и $q$ . На $p$ и $q$ есть ограничение — у перестановок не должно быть фиксированных точек. То есть $\forall i : p_{i} \neq = i$ и $q_{i} \neq = i$ .

После выбора перестановок Алиса перемешивает карты в соответствии с ними. Теперь $i$ -ой картой слева является карта $a [p [q [i]]]$ . Трюк считается успешным, если на $i$ -ой карте слева после тасования стоит число $i$ .

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

Вход. Первая строка содержит количество тестов $t (1 \leq t \leq 1 0^{5})$ .

Каждый тест задается двумя строками. Первая строка содержит одно целое число $n (1 \leq n \leq 1 0^{5})$ — количество карточек. Вторая строка содержит $n$ целых чисел $a_{i} (1 \leq a_{i} \leq n, \forall i \neq = j : a_{i} \neq = a_{j})$ — начальную перестановку карточек.

Гарантируется, что сумма $n$ по всем тестам не превышает $1 0^{5}$ .

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

Для каждого теста в отдельной строке выведите "Impossible", если решение не существует.

В противном случае, в первой строке выведите "Possible", а в следующих двух строках выведите перестановки $p$ и $q$ .

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

Рассмотрим три перестановки: $a, p, q$ . Пусть $I$ — тождественная перестановка. Рассмотрим равенство: $a (p (q (I))) = I$ . Отсюда $p (q (I)) = a^{- 1}$ . Используя тот факт, что перестановка применяется справа налево, указанное тождество можно переписать в виде: $p ° q = a^{- 1}$ . Отсюда следует что $q = p^{- 1} ° a^{- 1}$ .

Генерируем случайную перестановку $p$ , у которой нет фиксированных точек. После чего вычисляем перестановку $q = p^{- 1} ° a^{- 1}$ и тоже проверяем, чтобы у нее не было фиксированных точек. Найденные перестановки $p$ и $q$ являются искомыми.

Пример

Рассмотрим перестановку $a = (5, 1, 4, 2, 3)$ .

Обратной к ней будет $a^{- 1} = (2, 4, 5, 3, 1)$ .

Генерируем случайную перестановку $p$ без фиксированных точек. Пусть, например, $p = (4, 1, 2, 5, 3)$ . Вычислим перестановку, ей обратную: $p^{- 1} = (2, 3, 5, 1, 4)$ .

Далее вычисляем $q = p^{- 1} ° a^{- 1} = (2, 3, 5, 1, 4) ° (2, 4, 5, 3, 1) = (3, 1, 4, 5, 2)$ . Перестановка $q$ не содержит фиксированных точек, поэтому она нам подходит.

Функция print выводит элементы массива $a$ , начиная с первого.

void print(vector<int>& a)
{
  for (int i = 1; i < a.size(); i++)
    printf("%d ", a[i]);
  printf("\n");
}

Функция is_valid проверяет, содержит ли перестановка $v$ фиксированные точки.

bool is_valid(vector<int>& v)
{
  for (int i = 1; i < v.size(); i++)
    if (v[i] == i) return false;
  return true;
}

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

vector<int> a, p, p1, q;

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

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

Инициализируем массивы.

  a.resize(n + 1);
  p1.resize(n + 1);
  p.resize(n + 1);
  q.resize(n + 1);

Читаем входную перестановку $a$ и сразу в массив $а$ заносим перестановку, ей обратную. То есть массив $a$ содержит перестановку $a^{- 1}$ , где $a$ — входная перестановка.

  for (i = 1; i <= n; i++)
  {
    scanf("%d", &x);
    a[x] = i;
  }

mt19937 — это один из стандартных генераторов псевдослучайных чисел в C++ (Mersenne Twister с периодом 19937). Он очень быстро работает и обладает хорошими статистическими свойствами, что делает его отличным выбором для большинства задач, требующих генерации случайных чисел.

  mt19937 gen(random_device{}());

В переменной $f o u n d$ будем отмечать, найден ли ответ для текущего теста.

  found = false;

Проводим $1000$ итераций.

  for (it = 0; it < 1000; it++)
  {

Генерируем случайную перестановку. Для этого заносим в массив $p$ числа $0, 1, 2, ...$ и при помощи функции shuffle проводим перемешивание элементов, начиная с первого (не нулевого) элемента. Мы работаем с перестановками от $1$ до $n$ .

    iota(p.begin(), p.end(), 0);
    shuffle(p.begin() + 1, p.end(), gen);

Проверяем, является ли перестановка $p$ допустимой (не содержит фиксированных точек).

    if (!is_valid(p)) continue;

Вычисляем перестановку $p_{1} = p^{- 1}$ .

    for (i = 1; i <= n; i++)
      p1[p[i]] = i;

Вычисляем перестановку $q = p_{1} ° a^{- 1} = p^{- 1} ° a^{- 1}$ .

    for (i = 1; i <= n; i++)
      q[i] = p1[a[i]];

Если перестановка $q$ является допустимой, то выводим ответ.

    if (is_valid(q))
    {
      puts("Possible");
      print(p);
      print(q);
      found = true;
      break;
    }
  }

Если за $1000$ итераций ответ не был найден, то его не существует.

  if (!found) puts("Impossible");
}

Комментарии

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

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

Войти

Загрузка

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