e-olymp 8963. Наименьшие влево

Условие

Задан массив из [latex]n[/latex] целых чисел. Переместить все минимальные элементы в начало массива, не меняя порядок других.

Входные данные

В первой строке записано натуральное число [latex]n[/latex]. В следующей строке записаны [latex]n[/latex] целых чисел. Все числа по модулю не превышают [latex]100[/latex].

Выходные данные

Выведите элементы обновленного массива.

Тесты

Ввод Вывод
1 7
6 -3 -7 4 -7 -4 5
-7 -7 6 -3 4 -4 5
2 2
100 -100
-100 100
3 6
-2 -2 7 3 99 -2
-2 -2 -2 7 3 99
4 5
1 1 1 1 1
1 1 1 1 1

Решение

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

Код программы

Ссылки

решение на E-olymp
код на ideone

e-olymp 9414. Убить всех термитов

Условие задачи

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

Входные данные

Первая строка содержит одно целое число $n$ $(1 \leqslant n \leqslant 100000)$. Следующая строка содержит $n — 1$ целое число  $p_{i} (2 \leqslant i \leqslant n)$, означающее что ребро соединяет $p_{i}$ и $i$.

Выходные данные

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

Тесты

Входные данные Выходные данные
1 1 1
2 2
1
1
3 8
1 1 2 1 2 3 2
2
4 5
1 2 1 4
1
5 16
1 2 3 4 5 3 7 1 9 9 11 11 13 13 15
3
6 10
1 2 3 3 1 2 3 7 9
2
7 8
1 1 3 3 1 6 6
2

Код

Решение задачи

Поскольку в задаче речь идет о дереве, циклов в нем нет по определению. Значит, единственным способом для термита ходить «вечно» будет путь между двумя листами, в которых он сможет разворачиваться. Фактически, задача сводится к вопросу «Какое минимальное количество вершин в дереве нужно отравить, чтобы нельзя было добраться из любого листа в другой лист не пройдя через отравленные?».

Определим для этого $3$ типа вершин: лист, развилка и обычная вершина. Листом назовем вершину, у которой нет детей (всего $1$ связь с другой вершиной). Обычные вершины — те, у которых ровно $2$ связи (для нашего термита это пути вниз или вверх). Развилкой назовем вершину, у которой $3$ или больше связей с другими. Будем считать корень тоже развилкой, даже если у него всего $2$ связи, или листом, если одна. Через развилки можно ходить из одного листа в другой, либо «вверх» — в сторону корня.

Типы вершин

$1$ — корень; $5,6,3$ — листья; $4$ — развилка; $2$ — обычная;

Первый этап

Очевидно, выгоднее всего «закрывать» развилки. А среди них — те, которые соединяют несколько листов напрямую. Пусть каждый лист отправляет «запрос» вверх по дереву на закрытие ближайшей к нему развилки. Когда «запрос» доходит до развилки, он тут же записывается на её счёт. Таким образом, в дереве выше вершина $4$ будет иметь $2$ запроса — от листов $5$ и $6$, а корень — $1$ запрос от листа $3$.

Теперь, просто считаем количество вершин с количеством запросов $\geqslant2$ и «закрываем» их.

Второй этап

Увы, первый этап не идеален и может «не донести» запросы в нужное место, т.к. некоторые развилки (а именно — соединяющие лист и другую развилку) могут остаться с одним запросом и не быть закрытыми. Если таких много, термит все еще может ходить между листами. Например, в таком дереве:

Дерево 2

Дерево, в котором необходим второй этап

Вершина $2$ и корень получают по $1$ запросу и остаются открытыми, а у термита остается путь между листами $10$ и $6$.

Для предотвращения таких случаев, пробежимся по дереву «снизу вверх» — от самого нижнего уровня до верхнего и для каждой развилки, у которой ровно $1$ запрос, сместим его вверх аналогично первому этапу — до ближайшей развилки. Будем выполнять этот шаг, пока есть такие вершины (с $1$ запросом).

В итоге, все запросы «соединятся» в нужных развилках, значение в них станет $\geqslant2$ и эти развилки нужно будет тоже закрыть. Для дерева выше, будет закрыт корень.

Осталось посчитать кол-во закрытых.

Описание алгоритма

Дерево будем хранить в массиве векторов tree. Количество запросов для вершины $i$ хранится в killed[i]. Стандартный вектор used для поиска в ширину и dist- вектор расстояний от корня до вершин, которые и будут определяться с помощью BFS.

Функция kills предназначена для того, чтобы донести запрос от листа до развилки. Она рассматривает $3$ случая:

  1.   v == p — текущая вершина совпадает с той, из которой пришли. Это крайний случай, говорящий о том, что мы только начали и находимся в листе. Тогда, идем в единственно возможном направлении — tree[v][0].
  2. tree[v].size == 2 — вершина обычного типа, просто идем «вверх», выбирая из двух путей тот, что не совпадает с предыдущей вершиной.
  3. tree[v].size >= 3 — попали в развилку. Увеличиваем ее значение killed[v] и выходим из рекурсии.

Функция goup отличается от kills лишь тем, что при v == p выбирает из всех направлений то, которое ближе к корню, используя dist.

Подготовка

Можно заметить, что для всех деревьев из $5$ или менее вершин ответ будет $1$. Проверим это сразу при вводе n. Далее, осторожно считываем дерево в массив векторов (см. Входные данные). В следующем цикле, определяем листья и запоминаем их в вектор leaves. Нужно учесть то, что корень может быть листом, если у него всего $2$ связи — одна с деревом, а другая — искусственно созданная нами в $0$ вершину.  Последний шаг — запустить поиск в ширину из корня, который заполнит вектор dist расстояниями от корня до вершин.

Первый этап

Просто запускаем kills (l, l) из каждого листа l для «отправки» запросов в ближайшие развилки.

Второй этап

Определяем максимальную «глубину» дерева — максимальное расстояние вершины от корня. Далее, для каждого уровня от самого нижнего до корня, при определении вершины со значением killed[i] == 1 запускаем goup (i, i), а в переменной wentup считаем количество таких случаев. Как только их не останется — while выйдет из цикла.

Наконец, осталось просто посчитать количество вершин, у которых значение killed[i] >= 2.
Задача на e-olymp
Код решения на ideone
Засчитанное решение на e-olymp

e-olymp 4853. Кратчайший путь

Задача

Задан неориентированный граф.
Найдите кратчайший путь от вершины $a$ до вершины $b.$

Входные данные

В первой строке находится два целых числа $n$ и $m$ $(1 \leqslant n \leqslant 50000,$ $1 \leqslant m \leqslant 100000)$ — количества вершин и рёбер соответственно. Во второй строке заданы целые числа $a$ и $b$ — стартовая и конечная вершина соответственно. Далее идут $m$ строк, описывающие рёбра.

Выходные данные

Если пути между $a$ и $b$ нет, то выведите $-1.$ Иначе выведите в первой строке длину $l$ кратчайшего пути между этими двумя вершинами в рёбрах, а во второй строке выведите $l + 1$ число — вершины этого пути.

Тесты

Входные данные Выходные данные
$4\;5$
$1\;4$
$1\;3$
$3\;2$
$2\;4$
$2\;1$
$2\;3$
$2$
$1\;2\;4$
$5\;4$
$2\;4$
$1\;2$
$2\;3$
$2\;5$
$5\;3$
$-1$
$4\;4$
$2\;3$
$2\;1$
$2\;4$
$4\;3$
$1\;3$
$2$
$2\;1\;3$
$6\;4$
$1\;6$
$1\;2$
$2\;4$
$5\;3$
$4\;5$
$-1$

Код программы

Решение задачи

Раз нам надо найти кратчайший путь, то будем использовать BFS — поиск в ширину. Мы будем постепенно просматривать вершины, внося в «план» те вершины с которыми они связанны и которые еще не внесены в «план». Для удобства используем вектора. В начале создаем вектор векторов, как бы это тавтологически не звучало, для этого я использовал вектор ответа, как объект, который добавлялся в вектор graf, выступающий в роли графа, причем мы добавляем сразу к вершинам graf[x].pushback(y);. То есть $x$-ая вершина получает связь с вершиной $y,$ и наоборот, поскольку граф неориентированный. После чего, проверяем связанна ли начальная вершина хоть с кем-нибудь, если да, то работаем циклом while, пока не наткнемся на начальную вершину, или все вершины в «плане» не будут пройдены. Если мы дошли до конечной вершины, то функция bfs вернет $1,$ что запустит тело if и мы начнем восстанавливать путь. Для этого мы заводили дополнительный вектор family в который по мере добавления в «план», также добавлялись и вершины «отцы»(откуда пришла $i$-ая вершина). Восстановленный путь записываем в вектор ans. После чего while прекращает свою работу и мы переходим к выводу результата. Если вектор ответа пуст, то выводим $-1,$ иначе выводим количество вершин, участвующих в построении пути и сам путь. Задача решена.

Ссылки

Условие задачи на e-olymp
Код решения на ideone.com

ML 31. Площадь параллелепипеда

Условие задачи:

Найти площадь полной поверхности параллелепипеда три стороны которого образованы векторами [latex] \overrightarrow{a}=(a_x,a_y,a_z), \overrightarrow{b}=(b_x,b_y,b_z) [/latex] и [latex]\overrightarrow{c}=(c_x,c_y,c_z)[/latex].

Входные данные:

Координаты векторов [latex] \overrightarrow{a}, \overrightarrow{b}[/latex] и [latex] \overrightarrow{c} [/latex].

Выходные данные:

Площадь полной поверхности параллелепипеда.

Тесты

Входные данные Выходные данные
1 -5.6 8.3 -7.1 2 11 -8 2.1 1 3.3 389.28894739406866
2 1 2 3 4 5 6 7 8 9 58.787753826796276
3 -9 2 4 -3 5 1 -6 7 8 305.5334243147188
4 1 1 1 1 1 1 1 1 1 0.0
5 0 0 1 0 1 0 1 0 0 6.0
6 0 0 0 1 0 0 0 0 1 2.0
7 1 0 0 0 0 1 0 0 1 2.0

 

Код на C++

Код на Java

Алгоритм

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

Для решения данной задачи нужно сперва найти площади трёх сторон (параллелограммов) данного параллелепипеда. Воспользуемся геометрическим смыслом векторного произведения:

  • Модуль векторного произведения [latex] [\overrightarrow{a},\overrightarrow{b}] [/latex] равняется площади S параллелограмма, построенного на приведённых к общему началу векторах [latex]\overrightarrow { a }[/latex] и [latex]\overrightarrow { b } [/latex]

Рассчитаем площадь каждого параллелограмма по формуле [latex] \left|\left[ \overrightarrow { a } , \overrightarrow { b } \right]\right| =
\left|(a_{ y }b_{ z }-a_{ z }b_{ y }, a_{ z }b_{ x }-a_{ x }b_{ z }, a_{ x }b_{ y }-a_{ y }b_{ x })\right|[/latex].

Найдя все три стороны, получим площадь полной поверхности параллелепипеда по формуле

[latex] S=2*(S_1+S_2+S_3) [/latex], где [latex] S_n [/latex] — площадь стороны параллелепипеда.

 

Ссылки:

Условие задачи ML31.
Работающая версия программы на языке C++.
Работающая версия программы на языке Java.
Геометрические свойства векторного произведения.

 

М6a

а) Чётные числа из стандартного потока ввода поместить в хранилище с именем [latex]Even[/latex], а нечётные —[latex]Odd[/latex]. Во входном потоке неизвестное количество целых чисел через пробел.

Поток ввода Результат
4 8 15 16 23 42 4 8 16 4215 23
0 1 1 2 3 5 8 13 21 34 55 89 144 0 2 8 34 1441 1 3 5 13 21 55 89

Код программы:

Создаем два вектора [latex] Odd [/latex] и [latex]Even[/latex]. С помощью цикла [latex]while[/latex] вводим неопределенное количество элементов. Внутри цикла с помощью [latex]push[/latex]_[latex]back[/latex] четные числа помещаем в [latex]Even[/latex] , а нечетные в [latex]Odd[/latex].

Код программы можно посмотреть тут