•Розбори•2 місяці тому

Освітній раунд №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$ містить бітову маску поточного підмножини $a$ . Сума його елементів обчислюється у змінній $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");
}

Коментарі

Покищо нічого

Будьте першим, хто розпочне обговорення!

Увійти

Завантаження

Секундочку, отримую дані з серверу