Разбор задач прошлогоднего этапа 1/8 ICPC

Задача A. Лара Крофт и клад

Имя входного файла: стандартный ввод

Имя выходного файла: стандартный вывод

Ограничение по времени: 1 секунда

Ограничение по памяти: 512 мегабайт

Лара Крофт нашла глиняную табличку, на которой было написана следующая инструкция:

  • Пройдите m метров на север от места, где обнаружена табличка.
  • После этого пройдите m метров на восток.
  • После этого пройдите $\sqrt{2} \cdot m$ метров на юго-запад.
  • Здесь и находится клад.

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

Формат входных данных

Входные данные содержат одно целое число m $(1 ⩽ m ⩽ 1000)$ — расстояние с таблички.

Формат выходных данных

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

Анализ

Самая простая задача тура. В ней надо просто вывести 0. Начертив траекторию или сложив соответствующие векторы, несложно убедиться, что Лара Крофт пришла в ту же точку. Пример к задаче мог служить подсказкой.

In [2]:
#include <iostream>
#include <vector>
#include <map>
using namespace std;
typedef long long llong;
typedef unsigned long long ullong;
In [3]:
void LarisaKroftovna(){
    int m=0;
    cin >> m;
    cout << 0;
}
In [4]:
LarisaKroftovna();
65465456
0

Задача B. История ICPC

Имя входного файла: стандартный ввод

Имя выходного файла: стандартный вывод

Ограничение по времени: 1 секунда

Ограничение по памяти: 512 мегабайт

Хотя история финалов чемпионатов по программированию ICPC отсчитывается с 1977 года, современный вид соревнования приобрели только в 1992. Дело в том, что до финала 1991 года включительно в команду на соревнованиях входило не трое, а четверо студентов.

Представьте, что вы — тренер студенческих команд в начале 1991-1992 учебного года. В конце прошлого сезона в тренировках участвовало K полных команд по старым правилам; из участников этих команд L закончили обучение в университете, а с нового набора ваши тренировки посещает M студентов. Какое наименьшее количество студентов вам надо дополнительно привлечь к тренировкам, чтобы к локальному чемпионату, который пройдёт уже по новым правилам, ни один из тренирующихся студентов не остался без полноценной команды?

Формат входных данных

Входной файл содержит три целых числа — K, L и M $(1 ⩽ K ⩽ 100, 0 ⩽ L ⩽ 4 \cdot K, 1 ⩽ M ⩽ 100)$.

Формат выходных данных

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

Анализ

Так как в предыдущем сезоне в команде участвовало 4 участника, то всего на данный момент тренируются $4K - L + M$ участников. Количество участников, остающихся без команды — это остаток от деления $4K - L + M$ на 3. Если остаток равен 0, никого дополнительно привлекать не надо. Если остаток равен 1, надо привлечь двух участников, если остаток равен 2 — одного участника. Также ответ можно записать формулой через операцию взятия остатка, но в этом случае надо учитывать особенности реализации этой операции в используемом языке программирования.

In [5]:
int GoodOldICPC_1(){
    int k, l, m;
    cin >> k >> l >> m;
    int a = (4 * k - l + m) % 3;
    if (a == 0) {
        return 0;
    } else if (a == 1) {
        return 2;
    } else {
        return 1;
    }
}
In [6]:
int GoodOldICPC_2(){
    int k, l, m;
    cin >> k >> l >> m;
    return (3 - ((k * 4 - l + m) % 3)) % 3;
}
In [7]:
cout << "First method: " << GoodOldICPC_1()<<'\n';
cout << "Second method: " << GoodOldICPC_2()<<'\n';
First method: 6 7 8
2
Second method: 7 6 5
0

Задача C. Петя, Маша и верёвочки

Имя входного файла: стандартный ввод

Имя выходного файла: стандартный вывод

Ограничение по времени: 1 секунда

Ограничение по памяти: 512 мегабайт

На столе лежали две одинаковые верёвочки целой положительной длины. Петя разрезал одну из верёвочек на N частей целой положительной длины, так что на столе стало $N + 1$ верёвочек. Затем в комнату зашла Маша и взяла одну из лежащих на столе верёвочек. По длинам оставшихся на столе N верёвочек определите, какую наименьшую длину может иметь верёвочка, взятая Машей.

Формат входных данных

Первая строка входных данных содержит одно целое число N — количество верёвочек, оставшихся на столе $(2 ⩽ N ⩽ 1000)$. Каждая из последующих N строк содержит по одному целому числу $l_i$ — длине очередной верёвочки $(1 ⩽ l_i ⩽ 1000)$.

Формат выходных данных

Выведите одно целое число — наименьшую длину, которую может иметь верёвочка, взятая Машей.

Анализ

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

In [5]:
void PMV(){
    int n, sum, max;
    cin >> n;
    max = 0;
    sum = 0;
    for (int i = 0; i < n; i++){
        int c;
        cin >> c;
        sum += c;
        if (max < c) max = c;
    }
    sum -= max;
    if (max > sum) cout << max - sum<<'\n';
    else cout << max + sum<<'\n';
}
In [8]:
PMV();
PMV();
4
1 5 2 1
1
4
5 12 4 3
24

Задача D. Многозначность

Имя входного файла: стандартный ввод

Имя выходного файла: стандартный вывод

Ограничение по времени: 1 секунда

Ограничение по памяти: 512 мегабайт

Сколько существует таких целых положительных чисел, которые в $B_1$-ичной системе счисления являются $D_1$-значными числами, а в $B_2$-ичной — $D_2$-значными?

Формат входных данных

Первая строка входных данных содержит два целых числа $B_1$ и $D_1$ $(2 ⩽ B1 ⩽ 100, 1 ⩽ D1 ⩽ 20)$. Вторая строка содержит два целых числа $B_2$ и $D_2$ $(2 ⩽ B2 ⩽ 100, 1 ⩽ D2 ⩽ 20)$.

Гарантируется, что наибольшее $D_1$-значное число в $B_1$-ичной системе счисления и наибольшее $D_2$-значное число в $B_2$-ичной системе счисления не превосходят 1018.

Формат выходных данных

Выведите одно число — количество целых положительных чисел, являющихся $D_1$-значными в $B_1$-ичной системе счисления и $D_2$-значными в $B_2$-ичной системе счисления.

Анализ

Наименьшее K-значное число в B-ичной системе счисления имеет вид «единица и $K - 1$ нулей»; соответственно, равно $B^{K-1}$. Аналогично, наименьшее $K + 1$-значное равно $B^K$, следовательно, предшествующее ему число $B^K - 1$ является наибольшим K-значным.

Тем самым задача сводится к следующей: даны два отрезка c концами $B_1^{D_1 - 1}$ и $B_1^{D_1} - 1$ и $B_2{D_2 - 1}$ и $B_2^{D_2} - 1$, найти количество целых точек в их пересечении. Для этого найдём самый правый из левых концов отрезка $L_r$ и самый левый из правых $R_l$. Если первый левее правее второго, ответ 0, иначе ответ $R_l - L_r + 1$.

In [6]:
llong mypow(llong a, llong b){
    if (b == 0)
        return 1;
    if (b == 1)
        return a;
    llong x = mypow(a, b / 2);
    if (b % 2 == 0)
        return x * x;
    else
        return x * x * a;
}
/*long long binpow (long long a, long long n) {
	long long res = 1;
	while (n) {
		if (n & 1)
			res *= a;
		a *= a;
		n >>= 1;
	}
	return res;
}*/
In [7]:
void MultiVal(){
    long long B1, D1, B2, D2;
    cin >> B1 >> D1 >> B2 >> D2;
    long long max1 = 1, max2 = 1, min1 = 1, min2 = 1, res;
    max1 = mypow(B1, D1) - 1;
    min1 = mypow(B1, D1 - 1);
    max2 = mypow(B2, D2) - 1;
    min2 = mypow(B2, D2 - 1);
    res = min(max1, max2) - max(min1, min2) + 1;
    if (res < 1)
        cout << 0;
    else
        cout << res;
    cout << '\n';
}
In [8]:
MultiVal();
MultiVal();
3 1 5 1
2
10 2 2 4
6

Задача E. Неактуальный баннер

Имя входного файла: стандартный ввод

Имя выходного файла: стандартный вывод

Ограничение по времени: 1 секунда

Ограничение по памяти: 512 мегабайт

Как известно, с этого года командный чемпионат мира по программированию называется ICPC; название же “ACM” более не актуально и использоваться не должно.

Однако дизайнер, делавший баннер к очередному сезону ICPC, скопировал старый дизайн и изобразил в углу баннера таблицу $M \times N$, заполненную заглавными латинскими буквами ‘A’, ‘C’ и ‘M’. Заказчик решил снизить вознаграждение дизайнера на сумму, равную количеству способов прочитать слово “ACM” на баннере.

Считается, что в таблице можно прочитать слово “ACM” если в некоторой клетке записана буква “A”, в одной из соседних с ней по стороне — буква “C”, а в одной из соседних уже с ней по стороне — буква “M”. Способы считаются различными, если хотя бы одна из клеток, задействованных при прочтении слова этими способами, различается.

Ваша задача — определить, на какую сумму заказчик снизит вознаграждение дизайнеру.

Формат входных данных

Первая строка входа содержит два целых числа M и N — размерность таблицы $(1 ⩽ M ⩽ 1000, 1 ⩽ N ⩽ 1000)$. Каждая из последующих M строк содержит по N заглавных латинских букв ‘A’, ‘C’ или ‘M’.

Формат выходных данных

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

Анализ

Для каждой буквы C количество способов прочтения слова ACM, в которую она входит, равно количеству соседних с буквой C букв A, умноженному на количество соседних с ней букв M (любые два способа, в которых различается первая буква, различны, равно как и любые два способа, в которых различается последняя буква; так как выбор из возможных соседних A и M независим, то для получения общего количества прочтений для заданной буквы C результаты подсчёта надо перемножить). Если просуммировать получившиеся результаты для всех букв C, то мы получим требуемый ответ.

In [8]:
int cnt(vector <vector<char>> &v, int pos_i, int pos_j){
    int c_m = 0, c_a = 0;
    int i = pos_i, j = pos_j;
    if (v[i - 1][j] == 'M') c_m++;
    if (v[i + 1][j] == 'M') c_m++;
    if (v[i][j - 1] == 'M') c_m++;
    if (v[i][j + 1] == 'M') c_m++;
    if (v[i - 1][j] == 'A') c_a++;
    if (v[i + 1][j] == 'A') c_a++;
    if (v[i][j - 1] == 'A') c_a++;
    if (v[i][j + 1] == 'A') c_a++;
    return c_a * c_m;
}
In [9]:
void CountACM(){
    int n, m;
    cin >> m >> n;
    m += 4;
    n += 4;
    unsigned long long sum = 0;
    vector <vector<char>> v(m);
    for (int i = 0; i < m; i++)
        v[i].resize(n);
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            v[i][j] = '0';
    for (int i = 2; i < m - 2; i++)
        for (int j = 2; j < n - 2; j++)
            cin >> v[i][j];
    for (int i = 2; i < m - 2; i++)
        for (int j = 2; j < n - 2; j++)
    if (v[i][j] == 'C')sum += cnt(v, i, j);
    cout << sum <<'\n';
}
In [11]:
CountACM();
2 4
ACMA
AACA
4

Задача F. Гиперсферы

Имя входного файла: стандартный ввод

Имя выходного файла: стандартный вывод

Ограничение по времени: 1 секунда

Ограничение по памяти: 512 мегабайт

Гиперсферой радиуса R с центром O в N-мерном пространстве называется множество всех точек, находящихся ровно на расстоянии R от точки O. Напоминаем, что расстояние между точкой a с координатами $x_1, x_2, ... , x_N$ и точкой b с координатами $y_1, y_2, ... , y_N$ в N-мерном пространстве равно $$\sqrt{\sum_{i=1}^N{{(x_i-y_i)}^2}}$$

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

Формат входных данных

Первая строка входных данных содержит одно целое число N — размерность пространства $(2 ⩽ N ⩽ 100)$. Вторая строка содержит параметры первой гиперсферы — радиус R и координаты центра $x_1, x_2, ... , x_N$ $(1 ⩽ R ⩽ 10^5, -10^5 ⩽ xi ⩽ 10^5)$. Третья строка содержит параметры второй гиперсферы в аналогичном формате.

Формат выходных данных

Выведите одно целое число — количество общих точек двух гиперсфер или -1, если общих точек бесконечно много.

Анализ

Обозначим расстояние между центрами за D.

Возможны следующие случаи:

  • D = 0. Тогда если радиусы равны, гиперсферы совпадают и ответ равен -1, если радиусы различны, гиперсферы не пересекаются и ответ равен 0.
  • Расстояние между центрами меньше одного из радиусов или равно ему. Тогда центр одной из гиперсфер находится внутри или на границе другой. В этом случае если разность большего и меньшего радиусов равна D, гиперсферы касаются изнутри, и ответ равен 1, если разность больше D, гиперсферы не имеют общих точек, и ответ равен 0, а если разность меньше D, ответ равен 2 в случае двумерного пространства (так как окружности пересекутся в двух точках) и -1 в случае большей размерности (так как пересечение будет по гиперсфере размерности N - 1, содержащей бесконечное количество точек).
  • Расстояние между центрами больше любого из радиусов. Тогда центр каждой гиперсферы находится вне другой. Если сумма радиусов равна D, имеем внешнее касание и ответ 1, если сумма радиусов меньше D, гиперсферы не пересекаются, если сумма радиусов больше D, гиперсферы пересекаются в двух точках в случае двумерного пространства и в бесконечном количестве случае в случае N > 2.

Отметим, что так как в сравнениях всегда в одной из частей находится D, а в другой — сумма или разность целых чисел и обе части сравнения неотрицательны, можно возвести обе стороны в квадрат и работать в 64-битных целых (так как максимальное значение суммы разностей координат равно $100 \cdot (2 \cdot 10^5)^2) = 4 \cdot 10^{12}$, что с гарантией помещается в 64-битный целочисленный тип.

In [10]:
void HyperSpheres(){
    ullong n, r1, r2, l, R, r;
    cin >> n;
    vector <llong> a1(n), a2(n);
    cin >> r1;

    for (int i = 0; i < n; ++i){
        cin >> a1[i];
    }
    cin >> r2;
    for (int i = 0; i < n; ++i){
    cin >> a2[i];
    }

    l = 0ull;

    for (int i = 0; i < n; ++i){
        l = l + ((a1[i] - a2[i])*(a1[i] - a2[i]));
    }

    R = (r1 + r2)*(r1 + r2);
    r = (r1 - r2)*(r1 - r2);

    if (l == 0ull){
        if (r1 != r2)
            cout << 0;
        else 
            cout << -1;
        return;
    }
    else if (l == R)
        cout << 1;

    else if (l <= r1 || l <= r2){
        if (l < r)
            cout << 0;
        else if (l == r)
            cout << 1;
        else if (l > r && n == 2)
            cout << 2;
        else if (l > r && n > 2)
            cout << -1;
        return;
    }
    else if (l < R){
            if (n == 2)
                cout << 2;
            else
                cout << -1;
        }
        else
            cout << 0;
    cout << '\n';
}
In [3]:
HyperSpheres();
HyperSpheres();
HyperSpheres();
3
2 0 0 0
1 3 0 0
1
3
2 0 0 0
1 1 1 1
-1
3
2 0 0 0
2 0 1 8
0

Задача G. Баскетбольная статистика

Имя входного файла: стандартный ввод

Имя выходного файла: стандартный вывод

Ограничение по времени: 1 секунда

Ограничение по памяти: 512 мегабайт

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

Байтландская Баскетбольная Ассоциация также решила ввести такую статистику. Правила баскетбола в Байтландии несколько отличаются от существующих в NBA; важная для статистики часть будет описана далее.

После каждого матча аналитики сдают протокол, который в упрощённом виде можно представить в виде следующего хронологически упорядоченного списка:

  • Владение — игрок X из команды T $(T = 0$ или $T = 1)$ владел мячом в соответствующий момент времени. Обозначается как “BALL X(T)”
  • Фол — на игроке X из команды T были нарушены правила, что привело к назначению Pen штрафных бросков по кольцу соперника, пробиваемых этим игроком. Обозначается как “FOUL ON X(T) Pen”, где Pen — количество бросков.
  • Штрафной бросок — игрок, на котором нарушили правила, пробил штрафной бросок по кольцу соперника. После фола следующие Pen событий — это штрафные броски. Обозначаются как “FREE Res”, где Res — 0, если игрок не попал в кольцо, и 1, если попал. Больше ни в каких ситуациях штрафные броски встретиться не могут.
  • Бросок с игры — владеющий мячом игрок бросил по кольцу соперника с расстояния L сантиметров. Обозначается как “RING L Res”, где Res — 0, если игрок не попал, и 1, если игрок попал.

Верны следующие ограничения:

  • Владение завершается либо сменой игрока, владеющего мячом, либо фолом, либо броском по кольцу, то есть две подряд записи “BALL”, относящиеся к одному и тому же игроку, невозможны.
  • После фола с N штрафными бросками обязательно следуют N бросков подряд (серия штрафных).
  • После попадания в кольцо с игры и после попадания с последнего штрафного в серии мяч обязательно переходит игроку другой команды (то есть следующее событие — “BALL” со сменой номера команды).
  • После неудачного броска или неудачного последнего штрафного в серии следующее событие — обязательно владение (то есть “BALL”).

Статистика определяется следующим образом:

  • Очки: за попадание со штрафного начисляется 1 очко, за попадание с расстояния, меньшего или равного 675 сантиметров — 2 очка, за попадание с расстояния, большего 675 сантиметров — 3 очка.
  • Передачи: если бросок был забит с игры и владение, предшествующее завершившемуся броском владению, было у игрока той же команды, что и бросавший игрок, то соответствующему игроку засчитывается результативная передача. Иначе говоря, для начисления передачи игроку P1 в протоколе должны подряд идти записи “BALL P1(T)”, “BALL P2(T)” и “RING L 1”.
  • Перехваты: если владение переходит к другой команде без броска или фола, игроку команды, получившей мяч, засчитывается перехват. Иначе говоря, для начисления перехвата игроком P1 в протоколе должны подряд идти записи “BALL P0(1-T)” и “BALL P1(T)”.
  • Подборы: первое владение после неудачного броска (с игры или последнего в серии штрафных) засчитывается как подбор. Иначе говоря, для начисления подбора игроком P1 в протоколе должны подряд идти записи “RING L 0” или “FREE 0” и “BALL P1(T)”, причём по какому кольцу был бросок, значения не имеет.

Ваша задача — по протоколу матча определить статистику каждого игрока.

Формат входных данных

Первая строка входных данных содержит целое число $N_1$ — количество задействованных в процессе игры игроков в команде 0 $(5 ⩽ N_1 ⩽ 10)$. В следующих $N_1$ строках задаются имена игроков команды 0. Каждое имя представляет собой непустую строку из заглавных латинских букв длиной не более 20 символов. Далее идёт целое число $N_2$ $(5 ⩽ N_2 ⩽ 10)$ — количество задействованных в процессе игры игроков в команде 1. Последующие $N_2$ строк задают имена игроков команды 1 в аналогичном формате. Гарантируется, что внутри одной команды все имена игроков различны.

Далее следует целое число Q $(1 ⩽ Q ⩽ 104)$ — количество записей в протоколе. Каждая из последующих Q строк содержит одну запись в формате, описанном в условии.

  • BALL pname(team) — игрок с именем pname из команды team владел мячом $(0 ⩽ team ⩽ 1)$.
  • FOUL ON pname(team) Pen — на игроке с именем pname из команды team были нарушены правила, игрок должен пробить Pen штрафных бросков $(0 ⩽ team ⩽ 1, 1 ⩽ Pen ⩽ 3)$.
  • RING L Res — игрок, владевший мячом, бросил по кольцу соперника с L сантиметров с результатом Res $(1 ⩽ L ⩽ 1500, 0 ⩽ Res ⩽ 1)$. Если Res = 1, бросок был успешным, если Res = 0 — неудачным.
  • FREE Res — игрок, на котором были нарушены правила, пробил штрафной бросок по кольцу соперника с результатом Res (Res = 1 — бросок был успешным, Res = 0 — неудачным).

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

Формат выходных данных

Выведите список игроков в следующем формате: TeamID Name S1 S2 S3 S4, где TeamID — номер команды (0 или 1), Name — имя игрока, S1 — количество очков, S2 — количество передач, S3 — количество перехватов и S4 — количество подборов. Список должен быть отсортирован сначала по номеру команды, а затем лексикографически по имени игрока.

Анализ

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

  • если событие — бросок с ненулевым результатом, то сделавшему бросок игроку увеличивается сумма очков, и в случае, если два предыдущих события — владение с одним и тем же номером команды, игроку из самого раннего из этих событий засчитываем передачу;
  • если событие — владение, то если предыдущее событие — бросок с нулевым результатом, то засчитывааем подбор, а если владение с другим номером команды — перехват.
In [11]:
struct player {
    int points = 0;
    int pass = 0;
    int pick = 0;
    int steal = 0;
    player () {};
};

struct command {
    string cmd;
    string name;
    int team;
    int res;
    int dist;
    command () {};
    command (string cmd, string name, int team, int res, int dist) 
        : cmd(cmd)
        , name(name)
        , team(team)
        , res(res)
        , dist(dist) {};
};
In [12]:
void EvalGame(){
    vector<command> query;
    map<string, player> players[2];
    command *tmp, *prev;
    int n1, n2, qq, team;
    string name, c;
    cin >> n1;
    for (int i = 0; i < n1; ++i) {      
        cin >> name;
        players[0][name] = player();
    }
    cin >> n2;
    for (int i = 0; i < n2; ++i) {
        cin >> name;
        players[1][name] = player();
    }
    cin >> qq;
    query.resize(qq);
    for (int i = 0; i < qq; ++i) {
        cin >> c;
        tmp = &query[i];
        tmp -> cmd = c;
        if (c == "BALL") {
            cin >> tmp -> name;
            tmp -> team = tmp -> name[tmp -> name.size() - 2] - '0';
            tmp -> name.erase(tmp -> name.end() - 3, tmp -> name.end());
            if (i != 0) {
                prev = &query[i - 1];
                if (prev -> cmd == "BALL" && prev -> team != tmp -> team) {
                    ++players[tmp -> team][tmp -> name].steal;
                }
                if ((prev -> cmd == "FREE" && prev -> res == 0) ||
                        (prev -> cmd == "RING" && prev -> res == 0)) {
                    ++players[tmp -> team][tmp -> name].pick;
                }
            }
        }
        if (c == "RING") {
            cin >> tmp -> dist >> tmp -> res;
            prev = &query[i - 1];
            if (tmp -> res == 1) {
                players[prev -> team][prev -> name].points += 2;
                if (tmp -> dist > 675) {
                    ++players[prev -> team][prev -> name].points;
                }
                if (i >= 2 && query[i - 2].team == prev -> team && query[i - 2].cmd == "BALL") {
                    ++players[query[i - 2].team][query[i - 2].name].pass;
                }
            }
        }
        if (c == "FOUL") {
            //
            int count;
            cin >> tmp -> name >> tmp -> name >> count;
            tmp -> team = tmp -> name[tmp -> name.size() - 2] - '0';
            tmp -> name.erase(tmp -> name.end() - 3, tmp -> name.end());
            ++i;
            for (int j = 0; j < count; ++j, ++i) {
                cin >> query[i].cmd >> query[i].res;
                if (query[i].res == 1) {
                    ++players[tmp -> team][tmp -> name].points;
                }
            }
            --i;
        }
    }
    for (auto elem : players[0]) {
        cout << "0 " << elem.first << ' ' << elem.second.points
                                   << ' ' << elem.second.pass
                                   << ' ' << elem.second.steal
                                   << ' ' << elem.second.pick
                                   <<'\n';
    }
    for (auto elem : players[1]) {
        cout << "1 " << elem.first << ' ' << elem.second.points
                                   << ' ' << elem.second.pass
                                   << ' ' << elem.second.steal
                                   << ' ' << elem.second.pick
                                   <<'\n';
    }
}
input_line_19:32:43: warning: '&&' within '||' [-Wlogical-op-parentheses]
                if (prev -> cmd == "FREE" && prev -> res == 0 ||
                    ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~ ~~
input_line_19:32:43: note: place parentheses around the '&&' expression to silence this warning
                if (prev -> cmd == "FREE" && prev -> res == 0 ||
                                          ^
                    (                                        )
input_line_19:33:47: warning: '&&' within '||' [-Wlogical-op-parentheses]
                        prev -> cmd == "RING" && prev -> res == 0) {
                        ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
input_line_19:33:47: note: place parentheses around the '&&' expression to silence this warning
                        prev -> cmd == "RING" && prev -> res == 0) {
                                              ^
                        (                                        )
In [5]:
EvalGame();
5
CURRY
DURANT
GREEN
IGOUDALA
PACHULIA
5
LEBRON
IRVING
KORVER
SMITH
LOVE
19
BALL IRVING(1)
BALL LEBRON(1)
RING 200 1
BALL CURRY(0)
RING 1000 1
BALL SMITH(1)
BALL GREEN(0)
BALL DURANT(0)
RING 400 0
BALL IGOUDALA(0)
BALL CURRY(0)
FOUL ON DURANT(0) 2
FREE 1
FREE 0
BALL LOVE(1)
BALL IRVING(1)
BALL LEBRON(1)
BALL KORVER(1)
RING 676 1
0 CURRY 3 0 0 0
0 DURANT 1 0 0 0
0 GREEN 0 0 1 0
0 IGOUDALA 0 0 0 1
0 PACHULIA 0 0 0 0
1 IRVING 0 1 0 0
1 KORVER 3 0 0 0
1 LEBRON 2 1 0 0
1 LOVE 0 0 0 1
1 SMITH 0 0 0 0

Задача H. Игра с матрицей

Имя входного файла: стандартный ввод

Имя выходного файла: стандартный вывод

Ограничение по времени: 1 секунда

Ограничение по памяти: 512 мегабайт

Это интерактивная задача. Алиса учит Боба работать с матрицами. Недавно она рассказала Бобу, что такое определитель.

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

Инверсией в перестановке $\pi$ называется такая пара чисел $i, j$, что $i < j$ и $\pi_i > \pi_j$.

Определителем квадратной матрицы A размера n называется $\sum_{\pi \in P_n}{(-1)^{N(\pi)} A_{1,\pi_1} \cdot A_{2,\pi_2} \cdot ... \cdot A_{n,\pi_n}}$, где $N(\pi)$ — количество инверсий в перестановке $\pi$, $P_n$ — множество всех перестановок размера n.

Боб не до конца усвоил урок, и поэтому Алиса разрешила ему поиграть с квадратной матрицей размера n. Боб может за одно действие прибавить произвольное число к произвольному элементу матрицы. В ответ Алиса называет ему определитель полученной матрицы.

Так как Алиса не умеет перемножать в уме большие числа, она делает все операции по модулю $10^9 + 7$.

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

Протокол взаимодействия

В начале вашего взаимодействия с программой жюри вам следует считать целых два числа — n и a $(1 ⩽ n ⩽ 20; 1 ⩽ a < 10^9 + 7)$ — размер матрицы и ее определитель.

После этого начинается взаимодействие. Каждый ваш запрос описывается тремя числами $x, y, d$ $(1 ⩽ x; y ⩽ n; 1 ⩽ d < 10^9 + 7)$ — номер строки и столбца элемента, который вы хотите изменить, а также число, которое вы хотите к нему прибавить.

На каждый ваш запрос программа жюри в отдельную строку записывает единственное число a $(0 ⩽ a < 10^9 + 7)$ — определитель получившейся матрицы. После того, как вы получили ответ $a = 0$, ваша программа до должна завершить работу.

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

Анализ

Назовем дополнительным минором $M_{i,j}$ матрицы A определитель матрицы, полученной вычеркиванием из матрицы A i-й строки и j-го столбца. Обозначим определитель матрицы A как $det(A)$. Можно доказать, что $det(A) = \sum_{i=1}^n{(-1)^{1+i}A_{1,i} \cdot M_{1,i}}$.

Давайте прибавим единицу к элементу $A_{1,j}$ и посмотрим, как изменится определитель. Из приведённой выше формулы очевидно, что он изменится на $D = (-1)^{1+j} \cdot M^{1,j}$. Мы можем легко найти D как разность нового и старого определителя матрицы.

Пусть $D \neq 0$. Обозначим за B матрицу, полученную после нашей операции. Нам известно, что $det(A) + D = det(B)$. Давайте теперь к элементу $B_{1,j}$ прибавим число $-\frac{det(B)}{D}$. Так как мы меняли только элементы первой строчки, то все используемые нами дополнительные миноры не изменились, а значит определитель полученной матрицы будет равен $det(B) - \frac{det(B)}{D} \cdot (-1)^{1+j} \cdot M_{1,j} = det(B) - \frac{det(B)}{D} \cdot D = det(B) - det(B) = 0$, что и требовалось.

Так как изначально определитель был не равен 0, то существует такое j, что $M_{1,j} \neq 0$, нужно лишь его найти. Для этого достаточно попытаться прибавить единицу к каждому элементу первой строки. Итоговое количество действий не превышает 21, что укладывается в ограничения задачи.

In [2]:
llong mod_pow(llong a, llong b, llong m) {
    if (b == 0) {
        return 1;
    }
    llong tmp = mod_pow(a, b / 2, m);
    tmp = tmp * tmp % m;
    if (b % 2 == 0) {
        return tmp;
    }
    return tmp * a % m;
}
In [3]:
void mxGame() {
    int n;
    llong d, d1 = 0, i = 0;
    const llong M = 1e9 + 7;
    cin >> n >> d;
    d1 = d;
    while (d1 - d == 0) {
        cout << "1 " << ++i << " 1\n";
        cin >> d1;
    }
    cout << "1 " << i << ' ' << (M - d1 * mod_pow((d1 - d + M) % M, M - 2, M) + M * M) % M << '\n';
}
In [10]:
mxGame()
3 2
1 1 1
0
1 1 0

Задача I. Прямые и треугольники

Имя входного файла: стандартный ввод

Имя выходного файла: стандартный вывод

Ограничение по времени: 1 секунда

Ограничение по памяти: 512 мегабайт

Даны целые положительные числа n и k. Необходимо провести n прямых, таких, что:

  • никакие две прямые не являются параллельными или совпадающими;
  • никакие три прямые не пересекаются в одной точке;
  • среди частей, на которые прямые разобьют плоскость, ровно k будут треугольниками.

Формат входных данных

В единственной строке через пробел записаны два целых положительных числа n и k, $3 ⩽ n ⩽ 50$, $n - 2 ⩽ k ⩽ n$.

Формат выходных данных

Выведите n прямых, по одной на каждой строке. Каждая прямая задается четырьмя целыми числами $x_1, y_1, x_2, y_2$, не превосходящими по абсолютной величине 10 000 и записанными через пробел; здесь $(x_1; y_1)$ и $(x_2; y_2)$ - две различные точки, лежащие на задаваемой прямой. Если соответствующие прямые подобрать невозможно, выведите в единственной строке число -123456789. Гарантируется, что если удовлетворяющие условию n прямых существуют, то существуют и удовлетворяющие условию n прямых, которые могут быть заданы вышеописанным способом.

Анализ

Если n = 3, то единственный случай, когда ответ существует, это k = 1. Доказательство этого факта очевидно, поэтому перейдем к следующему случаю.

Если n = 4, то единственный случай, когда ответ существует, это k = 2. Пример:

Если k > 2, то нам необходимо построить хотя бы 3 треугольника, которые суммарно имеют 3 ребра. Значит, всего 9 ребер и, по принципу Дирихле, будет существовать прямая, содержащая в себе 3 ребра. Однако это невозможно, поскольку прямую три другие могут разбить не более чем на два отрезка конечной длины.

Во всех остальных случаях ответ существует.

Пусть $k = n - 2$. Тогда пример строится следующим образом:

Проводятся две прямые, совпадающие с осями координат. Затем проводится n - 2 прямые, i-я из которых проходит через точки с координатами $(0, 100 \cdot i)$ и $(100 \cdot i, 0)$. Нетрудно убедиться, глядя на картинку, что всего будет ровно n - 2 треугольника.

Пусть $k = n - 1$. Тогда пример получается из предыдущего добавлением одной прямой:

Прямая проходит через точки $(0, 100\cdot(n-1))$ и $(100\cdot(n-1), 0)$. Однако следует быть осторожным, поскольку новая прямая может быть параллельна одной из ранее проведённых. Поэтому имеет смысл передвинуть одну из ее точек, например первую: $(0, 100 \cdot (n - 1) - 1)$. Пусть $k = n$. Тогда пример получается из предыдущего добавлением одной прямой:

Прямая проходит через точки $(0, 100 \cdot n)$ и $(100 \cdot (n - 3) - 49, 0)$.

In [15]:
void tringleMeBaby(){
    int n, k;
    const int no = -123456789;
    cin >> n >> k;
    if (n == 3) {
        if (k != 1) {
            cout << no << endl;
            return 0;
        }
        cout << "0 0 0 1\n0 0 1 0\n0 1 1 0\n";
        return 0;
    }
    if (n == 4) {
        if (k != 2) {
            cout << no << endl;
            return 0;
        }
        cout << "0 0 0 1\n0 0 1 0\n2 0 0 1\n 0 2 1 0\n";
        return 0;
    }
    if (k == n - 2) {
        for (int i = 0; i < n; ++i) {
            cout << i * 100 << " 0 0 " << (n - 1) * 100 - i * 100 << '\n';
        }
    }
    if (k == n - 1) {
        for (int i = 0; i < n - 1; ++i) {
            cout << i * 100 << " 0 0 " << (n - 2) * 100 - i * 100 << '\n';
        }
        cout << 100 * (n - 1) << " 0 0 " << 100 * (n - 1) + 1 << '\n';
    }
    if (k == n) {
        for (int i = 0; i < n - 2; ++i) {
            cout << i * 100 << " 0 0 " << 100 * (n - 3) - i * 100 << '\n';
        }
        cout << 100 * (n - 2) << " 0 0 " << 100 * (n - 2) + 1 << '\n';
        cout << 100 * n << " 0 0 " << 100 * (n - 3) - 49 << '\n';
    }
}
In [12]:
tringleMeBaby();
tringleMeBaby();
3 1
0 0 0 1
0 0 1 0
0 1 1 0
3 2
-123456789

Задача J. Камни, компьютер и вечность

Имя входного файла: стандартный ввод

Имя выходного файла: стандартный вывод

Ограничение по времени: 3 секунды

Ограничение по памяти: 512 мегабайт

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

  1. Выбирает кучку, в которой количество камней наибольшее.
  2. Проверяет, верно ли, что количество камней в этой кучке не меньше, чем суммарно в двух других.
  3. Если это так, то он убирает из выбранной кучки количество камней, равное суммарному количеству камней в других кучках, и переходит к шагу 1. Иначе завершает свой ход.

Снежная Королева на каждом своем ходу удваивает количество камней в какой-либо кучке.

Первым ходит компьютер.

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

Снежная Королева застряла на первом же уровне. Известно, что изначально в первой кучке может быть от 1 до a камней, во второй — от 1 до b, а в третьей — от 1 до c камней. Получается, что всего в игре $a \cdot b \cdot c$ уровней. Вам надо определить, в скольких из них выиграет Снежная Королева.

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

Формат входных данных

В единственной строке записаны три целых числа a, b, c $(1 ⩽ a, b, c ⩽ 2000)$ — ограничения на размер первой, второй и третей кучки соответственно.

Формат выходных данных

Выведите единственное целое число — количество позиций, в которых побеждает Снежная Королева.

Анализ

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

Смоделируем первый ход компьютера. Пусть количество оставшихся камней в кучках равно a, b, c, причем, без ограничения общности, $a ⩽ b ⩽ c$. Есть три случая:

  1. $a=0$. В таком случае компьютер сразу выиграл.
  2. $2^t \cdot a = b = c$, для некоторого $t ⩾ 0$. Тогда, если игрок своим ходом выберет кучку b или c, то последовательность ходов компьютера будет следующей: $$(a; 2 \cdot b; b) \rightarrow (a; b - a; b) \rightarrow (a; b - a; 0)$$ То есть, компьютер, в таком случае, выиграет. Если же игрок своим ходом будет все время выбирать первую кучку, то через t шагов он попадет в ситуацию, где количество камней во всех кучках одинаково, и проиграет, так как после любого его хода компьютер будет уменьшать ту кучку, которую удвоил игрок.
  3. В остальных случаях игрок может играть так, чтобы компьютер не сделал ни одного хода. Заметим, что если компьютер больше ходить не будет, то достичь одинакового количества камней во всех кучках не получится, так как для этого их количество должно различаться в $k = 2^t$ раз. Случай, когда $b = c$ рассмотрен во втором пункте, поэтому $b < c$. Но тогда $a, b ⩽ \frac{c}{2}$, то есть компьютер мог сделать еще один ход, противоречие.

Заметим, что компьютер не может ходить тогда и только тогда, когда количество камней в кучках удовлетворяет неравенству треугольника. На каждом ходу игроку следует удваивать кучку, количество камней в которой минимально. Тогда, если $2 \cdot a ⩽ c$, то $2 \cdot a + b > c$ и неравенство треугольника выполнено. Иначе $2 \cdot a < b+c$, так как $a ⩽ b$ и $a ⩽ c$, и хотя бы одно из неравенств строгое.

Получается, что в этом случае игрок побеждает.

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

  1. $(a; a \cdot 2^t; a \cdot 2^t)$
  2. $(0; a; a)$

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

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

In [ ]:
//Author: Artem Romanov
#include <bits/stdc++.h>
//#define TASK "file"

#define F first
#define S second
#define ALL(x) (x).begin(), (x).end()

using namespace std;

typedef double dbl;

namespace task {
int aa, bb, cc;
int a, b, c, t, g;
int d[2000][2000];
vector<bool> s(1335334000);

int f(int x, int y, int z) {
  return d[x - 1][y - 1] + z - y;
}

void r(int x, int y, int z) {
  if (x > 2000 || y > 2000 || z > 2000) return;
  int v = f(x, y, z);
  if (s[v]) return;
  s[v] = true;
  if (x <= a && y <= b && z <= c) {
    if (z <= a) {
        t = 6;
    } else if (y <= a) {
        if (z <= b) {
        t = 4;
        } else {
        t = 2;
        }
    } else {
        if (z <= b) {
        t = 2;
        } else {
        t = 1;
        }
    }
    if (x == y) {
        if (y == z) {
        g += t / 6;
        } else {
        g += t / 2;
        }
    } else if (y == z) {
        g += t / 2;
    } else {
        g += t;
    }
    r(x, y, x + y + z);
    r(x, z, x + y + z);
    r(y, z, x + y + z);
  }
}

int main() {
  for (int i = 0; i < 2000; ++i) {
    for (int j = i; j < 2000; ++j) {
      d[i][j] = t;
      t += 2000 - j;
    }
  }
  cin >> aa >> bb >> cc;
  a = min({aa, bb, cc});
  c = max({aa, bb, cc});
  b = aa + bb + cc - a - c;
  for (int v = 1; v <= 2000; ++v) {
    for (int i = v; i + v <= 2000; ++i) {
      r(v, i, i + v);
    }
    for (int i = 0; (v << i) <= 2000; ++i) {
      r(v, (v << i), (v << i));
    }
  }
  cout << a * 1LL * b * c - g << '\n';
  return 0;
}
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.precision(11);
  cout.setf(ios::fixed);
#ifdef _DEBUG
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
#elif defined(TASK)
  freopen(TASK".in", "r", stdin);
  freopen(TASK".out", "w", stdout);
#endif
  return task::main();
}

Задача K. Игра с массивом

Имя входного файла: стандартный ввод

Имя выходного файла: стандартный вывод

Ограничение по времени: 4 секунды

Ограничение по памяти: 512 мегабайт

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

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

По данным n, k и массиву из n элементов найдите в нем k-ю в лексикографическом порядке подпоследовательность.

Напомним, что подпоследовательность последовательности $x_n$ — это последовательность $x_{n_t}$, где $n_t$ — возрастающая последовательность.

Последовательность x лексикографически меньше последовательности y, если существует такое i, что $x_j = y_j$ для любого $j < i$, а $x_i < y_i$, либо если x является «началом» y.

Формат входных данных

В первой строке входных данных записаны два целых числа — n и k $(1 ⩽ n ⩽ 5 \cdot 10^5; 1 ⩽ k ⩽ 10^{18})$ — количество элементов массива и номер искомой подпоследовательности соответственно.

Во второй строке записаны n целых чисел, по модулю не превосходящих $10^9$ — элементы массива.

Формат выходных данных

Если в массиве меньше чем k подпоследовательностей и ответа не существует, выведите единственное число -1.

Иначе в единственной строке выведите ответ — искомую подпоследовательность.

Анализ

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

Для каждого суффикса и для каждого элемента посчитаем, сколько существует подпоследовательностей на текущем суффиксе и которые начинаются на выбранный элемент. Это можно делать при помощи динамического программирования на суффиксе.

Очевидно, что когда мы к суффиксу добавляем слева элемент a, меняется только количество подпоследовательностей, начинающихся на a. Любую подпоследовательность, начинающуюся с числа a можно перенумеровать так, чтобы она начиналась именно с добавленного элемента. Поэтому новое количество подпоследовательностей, начинающихся на a есть общее количество подпоследовательностей предыдущего суффикса +1 — пустая подпоследовательность. Количество подпоследовательностей предыдущего суффикса можно посчитать как сумму элементов нашей динамики.

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

Однако, такое решение работает за $O(n^2)$.

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

Чтобы ускорить бинарный поиск на префиксных суммах нашего массива, можно использовать структуру данных «дерево отрезков», которая позволяет делать эти операции за $O(log(n))$.

Итоговая асимптотика решения получается $O(n \cdot log(n))$

In [ ]:
//Author: Artem Romanov
#include <bits/stdc++.h>
//#define TASK "file"

#define F first
#define S second
#define ALL(x) (x).begin(), (x).end()

using namespace std;

typedef long double dbl;

namespace task {
const int h = 500000;
const int64_t f = 2000000000000000000LL;
int n, s;
int64_t k;
int a[h];
int b[h];
map<int, vector<int>> c;
int64_t t[2 * h];
int64_t d[h];

int64_t sum(int64_t l, int64_t r) {
  return min(f, l + r);
}

void modify(int p, int64_t v) {
  for (t[p += s] = v; p > 1; p >>= 1) {
    t[p >> 1] = sum(t[p], t[p ^ 1]);
  }
}

int64_t query(int l, int r) {
  int64_t v = 0;
  for (l += s, r += s; l < r; l >>= 1, r >>= 1) {
    if (l & 1) v = sum(v, t[l++]);
    if (r & 1) v = sum(v, t[--r]);
  }
  return v;
}

int main() {
  cin >> n >> k;
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
    c[a[i]].push_back(i);
  }
  for (auto& it : c) {
    b[s] = it.F;
    for (int jt : it.S) {
      a[jt] = s;
    }
    ++s;
  }
  for (int i = n - 1; i >= 0; --i) {
    d[i] = t[s + a[i]];
    modify(a[i], sum(query(0, s), 1LL));
  }
  if (query(0, s) < k) {
    cout << -1 << '\n';
    return 0;
  }
  int i = 0;
  while (k > 0) {
    int l = 0, r = s;
    while (r - l > 1) {
      int m = (l + r) / 2;
      if (query(0, m) < k) {
        l = m;
      } else {
        r = m;
      }
    }
    cout << b[l] << ' ';
    k -= sum(query(0, l), 1LL);
    do {
      modify(a[i], d[i]);
    } while (a[i++] != l);
  }
  cout << '\n';
  return 0;
}
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.precision(11);
  cout.setf(ios::fixed);
#ifdef _DEBUG
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
#elif defined(TASK)
  freopen(TASK".in", "r", stdin);
  freopen(TASK".out", "w", stdout);
#endif
  return task::main();
}

Задача L. Граф. Просто граф...

Имя входного файла: стандартный ввод

Имя выходного файла: стандартный вывод

Ограничение по времени: 4 секунды

Ограничение по памяти: 512 мегабайт

Дан неориентированный связный граф, состоящий из n вершин, пронумерованных от 1 до n, и m ребер, а также q запросов. В каждом из запросов, вам требуется по заданным различным вершинам u и v, найти количество различных простых путей, соединяющих u и v. Напомним, что путь называется простым, если этот путь проходит по каждой из вершин графа не более чем по одному разу.

Формат входных данных

В первой строке записаны целые неотрицательные числа n и m $(1 ⩽ n ⩽ 200000, 0 ⩽ m ⩽ n + 4)$ - количество вершин и рёбер графа.

Далее в следующих m строках записано по паре целых чисел $u, v, 1 ⩽ u, v ⩽ n, u \neq v$.

В следующей строке записано целое число q, $1 ⩽ q ⩽ 2000000$ - количество запросов. В следующих строках записано по паре целых чисел u, v, $1 ⩽ u,v ⩽ n, u \neq v$, описывающих запрос.

Гарантируется, что в графе не существует петель и кратных ребер.

Формат выходных данных

Для каждого запроса выведите в отдельной строке количество различных путей между вершинами u и v.

Анализ

Пусть $G = (V,E)$ - это исходный граф. Запустим в нем поиск в глубину, и пусть $T = (V,E′)$ - корневое дерево, которое обошел поиск. Тогда по свойствам поиска, каждое из ребер $E E′$ соединяет какую-то из вершин с ее предком в T. Назовем такие ребра дополнительными. Также назовем вершину помеченной, если она инцидентна одному из дополнительных ребер и/или является наименьшим общим предком двух инцидентных дополнительным ребрам вершин. Так как $|E′| = n-1$, а $|E| ⩽ n + 4$, то дополнительных ребер не более пяти, а помеченных вершин - не более 14, или $3(m - n + 1) - 1$; назвем это число k.

Помеченные вершины устроены таким образом, что любой путь между двумя помеченными вершинами, не содержащий промежуточных вершин, есть либо дополнительное ребро, либо путь по T, причем такой путь единственнен. Найдем все такие пути и построим граф $H = (V_H,E_H)$, вершинами которого будут помеченные вершины, а ребра будут соответствовать путям без промежуточных вершин. Отметим, что две вершины $G′$ могут быть соединены не более чем двумя кратными ребрами. Таким образом, в $G′$ будет k вершин и не более чем $k - 1 + (m - n + 1) = O(k)$ ребер.

Заметим, что c помощью стандартной динамики по профилю мы за $O(2k \cdot k)$ сможем найти количества простых путей в $G′$ от одной вершины до всех остальных. Насчитаем следующие массивы:

  • $paths[v_1][v_2], v_1; v_2 \in V_H$ - количества простых путей в $G′$ от $v_1$ до $v_2$;
  • $paths2[e][v], e \in E_H, v \in V_H$ - cумма количеств простых путей от $v_1^e$ до v и от $v_2^e$ до v, не проходящих через ребро e, соединяющее вершины $v_1^e$ и $v_2^e$;
  • $paths3[e_1][e_2], e1; e2 \in E_H$ - количества простых путей, соединяющих один из концов ребра $e_1$ с одним из концов ребра $e_2$ и не проходящих через ребра $e_1$ и $e_2$.

Теперь временно удалим помеченные вершины из графа G; тогда граф распадется на компоненты связности, каждая из которых является поддеревом T. Найдем для каждой компоненты $comp$ список $lst = lst(comp)$ помеченных вершин, соединенных ребром c вершинами comp в графе G. Из устройства помеченных вершин очевидно, что $lst(comp)$ содержит не более двух вершин. Также определим $comp$ для помеченной вершины v как $fvg$. Пусть также $v(comp)$ есть вершина списка $lst(comp)$, если она единственна; если же $|lst(comp)| = 2$, то пусть $e(comp)$ есть ребро в графе $G′$, соединяющее вершины $lst(comp)$.

Поймем теперь, как ответить на запрос для вершин $v_1$ и $v_2$. Пусть $comp1$ и $comp_2$ есть компоненты, в которых лежат $v_1$ и $v_2$ соответственно. Тогда ответ может быть получен следующим образом:

  • Если $|lst(comp1)| = |lst(comp2)| = 1$, то ответ есть $paths[v(comp_1)][v(comp_2)]$;
  • Если $|lst(comp1)| = 1$, a $|lst(comp2)| = 2$, то ответ есть $paths2[e(comp_2)][v(comp_1)]$;
  • Если $|lst(comp_1)| = |lst(comp_2)| = 2$, то:
    • если $comp_1 \neq comp_2$, то ответ - это $paths3[e(comp_1)][e(comp_2)]$;
    • если $comp_1 = comp_2$, то пусть $w_1 \in V$ есть минимальный предок $v_1$, лежащий на пути в T, соединяющем вершины $lst(comp_1)$. Аналогично определим w2 для v2. Тогда если $w_1 = w_2$, то тогда любой путь между $v_1$ и $v_2$ будет проходить через наименьшего общего предка $v_1$ и $v_2$, являющегося потомком $w_1$ или самой $v_1$; в силу этого, ответ 1. Если же $w_1 \neq w_2$, то можно единственным способом провести два непересекающиеся вершинно пути из $v_1$ и $v_2$ в вершины $lst(comp_1)$; если это $u_1$ и $u_2$, то ответ есть $1 + (paths2[e(comp_1)][u_2] - 1) = paths2[e(comp_1)][u_2]$ (мы учли путь «напрямую», а также вычли путь, соединяющий $u_2$ с собой же).

Итоговая асимптотика решения $O(n log n + 2^k \cdot k^3)$ (массивы paths, paths2, paths3 ищем за $O(2^k \cdot k^3))$.

In [ ]: