Портал обучения информатике. Подготовка к ЕГЭ, ОГЭ, олимпиадам

Dueling GPSs#89949

Фермер Джон недавно купил новую машину с двумя навигационными
системами GPS. Что ещё хуже, они часто конфликтуют при выборе
Маршрута.

Карта региона, в котором живёт ФД представляет собой N перекрёстков
(2 <= N <= 10,000) и M двунаправленных дорог (1 <= M <= 50,000).
Дорога I соединяет перекрёстки A_i (1 <= A_i <= N) и B_i (1 <= B_i <= N).

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

Дом ФД находится в перекрёстке 1, а его ферма распложена в перекрёстке
N. Существует путь из дома на ферму, по серии однонаправленных дорог.

Обе GPS-системы используют карту описанную выше, однако они дают
различные значения времени проезда по каждой дороге. Дорога I
требует P_i единиц времени по первой GPS-системе и Q_i единиц времени
по второй (каждая из величин – целое число в интервале 1..100,000).

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

Пожалуйста, помогите ФД определить минимальное количество предупреждений,
которое он может получить соответствующим выбором маршрута.
Если две SPS-системы предупреждают одновременно, к ответу в этом случае
нужно прибавлять число 2.

PROBLEM NAME: gpsduel

Формат ввода:

* Строка 1: целые числа N и M.
* Строка 2-N+1: Строка i описывает дорогу i четырьмя
целыми числами: A_i B_i P_i Q_i.

Примечание

Всего имеется 5 перекрёстков и 7 однонаправленных дорог. Первая
дорога идёт от перекрёстка 3 к перекрёстку 4, первая GPS считает,
что нужно 7 единиц времени для проезда по этой дороге, а вторая GPS
- полагает, что требуется одна единица времени.

Формат вывода:

* Строка 1: Минимальное количество предупреждений, которое
может получить ФД при оптимальном проезде от дома до фермы.

Примечание

Если ФД выберет путь 1 -> 2 -> 4 -> 5, тогда первая GPS пожалуется на
дороге 1->2 (она предпочитает путь 1>3). Однако в остальной части маршрута
2 -> 4 -> 5, обе GPS промолчат, поскольку обе считают такой маршрут
кратчайшим от 2 до 5.

—Войти и решать

Code Breaking#89946

Фермер Джон спрятал ключи от трактора в сейфе. Коровы пытаются взломать этот сейф. Сейф защищён сложной парольной системой. Она организована как корневое дерево из N (1 <= N <= 20,000) вершин, каждая из которых требует цифру от 0 до 9. Вершины пронумерованы от 0 до N-1.
Единственная информация, которой владеют коровы – что определённая последовательность длины 5 не случается на путях в этом дереве.
Например, предположим, то дерево выглядит так (с корнем в A):
A <- B <- C <- D <- E ^ | F
Коровы могут знать, что последовательность 01234 не случится начиная от F, И что последовательность 91234 не случится, начиная от E. Эта информация приводит к тому, что возможными остаются 19 паролей, все такого вида:
The cows might know that the sequence 01234 does not occur starting at F, and that the sequence 91234 does not occur starting at E. This information rules out 19 possible passcodes: all those of the form
4 <- 3 <- 2 <- 1 <- * ^ | 0
или
4 <- 3 <- 2 <- 1 <- 9 ^ | *
Что даёт 19 паролей, поскольку такой
4 <- 3 <- 2 <- 1 <- 9 ^ | 0
появится дважды
По заданным M (1 <= M <= 50,000) последовательностям длины 5, вместе с их стартовой позицией в дереве помогите коровам вычислить сколько паролей будет подходить. Вы должны выводить свой ответ по модулю 1234567.

PROBLEM NAME: code
Формат ввода:
* Строка 1: Два разделённых пробелом целых числа, N и M.
* Строки 2..N: Строка i+1 содержит одно целое число p(i), означающее родителя вершин I в дереве (0 <= p(i) < i).
* Строки N+1..N+M: Строка N+i описывает i-ую последовательность про которую известно, что она не произойдёт в коде. Строка содержит v(i) и s(i), разделённые пробелом. Здесь v(i) - стартовая вершина последовательности, s(i) – строка из 5 цифр, которая не встретится в шифре начиная с вершины v(i) если двигаться вверх по дереву. Гарантируется, что корень дерева находится не менее чем в 4 шагах от v(i).

Вывод формулы графы Деревья

—Войти и решать

Decorating the Pastures#89943

У Фермера Джона имеется N (1 <= N <= 50,000) пастбищ, последовательно пронумерованных от 1 до N, соединённых M (1 <= M <= 100,000) двунаправленными дорогами. Дорога I соединяет пастбища A_i (1 <= A_i <= N) и B_i (1 <= B_i <= N), A_i != B_i. Возможны две дороги соединяющие одну и ту же пару пастбищ.
Беси хочет украсить пастбища к дню рождения ФД. Она хочет разместить на каждом пастбище огромный знак содержащий либо букву ‘F’ либо букву ‘J’, но чтобы не огорчать ФД, должно быть выполнено правило, Пастбища декорируются разными знаками, если они соединены дорогой.
Компания, изготавливающая знаки, требует больше денег за знак ‘F’ и меньше денег за знак ‘J’, поэтому Беси хочет максимизировать количество знаков ‘J’, которые она использует. Пожалуйста, определите это число или выведите -1, если невозможно расставить знаки по описанным правилам.
uses. Please determine this number, or output -1 if there is no valid way to arrange the signs.
PROBLEM NAME: decorate
Формат ввода:
* Строка 1: Два целых числа N и M.
* Строки 2..M+1: Два целых числа, A_i и B_i указывающих наличие двунаправленной дороги между пастбищами A_i и B_i.
Примечание
Пастбища и дороги представляют собой вершины и стороны квадрата.
Формат вывода:
* Строка 1: Одно целое число, указывающее максимальное количество знаков ‘J’ которые сможет использовать Беси. Если нет решения, то выводить -1.
Примечание
Беси может пометить пастбища 1 и 3 знаком ‘J’ (или альтернативно - пастбища 2 и 4).

графы поиск в глубину и подобное Поиск компонент связности

—Войти и решать

Watering the Fields#89942

В связи с недостатком дождей Фермер Джон хочет построить ирригационную систему для доставки воды на N его полей (1 <= N <= 2000).
Все поля описываются различными точками (xi,yi) на плоскости, где 0<=xi,yi<=1000. Цена постройки трубы для доставки воды из точки i в точку j равна квадрату евклидового расстояния между ними:
(xi - xj)^2 + (yi - yj)^2
ФД хочет проложить минимальную по стоимости систему труб так, чтобы все его поля были соединены таким образом, чтобы водя из любого поля могла достичь любого другого поля по некоторой последовательности из проложенных труб.
К несчастью, подрядчик, у которого ФД заказал эту систему, отказывается прокладывать трубы стоимостью меньше чем C (1 <= C <= 1,000,000).
Пожалуйста, помогите ФД определить минимальное количество денег, которые ФД должен заплатить, чтобы проложить задуманную систему труб.
PROBLEM NAME: irrigation
Формат входных данных
* Строка 1: Целые числа N и C.
* Строки 2..1+N: Строка i+1 содержит целые числа xi и yi.
Формат выходных данных
* Строка 1: Минимальная стоимость задуманной сети труб , или -1 если такая сеть не может быть построена.
Примечание
ФД не может построить трубу между полями в точках (4,3) и (5,0), поскольку её стоимость не более 10. Поэтому он построит трубы между (0,2) и (5,0) со стоимостью 29 и трубу между (0,2) и (4,3) со стоимостью 17.

Минимальный каркас

—Войти и решать

Cow Art#89934

Известно, что коровы не различают красный и зелёный цвета. Это затрудняет создание картин, которые бы одинаково воспринимались коровами и людьми.
Например, рассмотрим квадрат, описанный N*N решёткой символов (1 <= N <= 100), каждый из которых либо R (красный), G(зелёный) или B(синий). Рисунок интересен, если в нём много цветовых «регионов» которые могут отличаться друг от друга. Два символа считаются принадлежащими одному и тому же региону, если они являются непосредственно соседними (на восток, запад, север или юг) и если они неразличимы по цвету. Например, рисунок
RRRBB GGBBB BBBRR BBRRR RRRRR
для человека имеет 4 региона (2 красных, 1 синий, 1 зелёный), а для коровы только 3 (2 красно-зелёных и 1 синий) .
Для заданного на вводе рисунка определите количество регионов в нём для человека и коровы.
PROBLEM NAME: cowart
Формат входных данных
* Строка 1: Целое число N.
* Строки 2..1+N: Каждая строка содержит строку из N символов, описывающих одну строку рисунка.
Формат выходных данных
* Строка 1: Два разделённых пробелом целых числа, описывающих количество регионов в этом рисунке для человека и коровы.

Поиск компонент связности

—Войти и решать

Cross Country Skiing#89932

Лыжная трасса описана решёткой из M x N высот (1 <= M,N <= 500), каждая из высот в диапазоне 0 .. 1,000,000,000.
Некоторые из этих ячеек обозначены как точки маршрута гонки. Организаторы хотят назначить маршруту рейтинг трудности D так, чтобы корова могла попасть в любую точки маршрута из любой другой точки маршрута, последовательно перемещаясь между соседними ячейками, абсолютная разность высот которых не превышает D. Две ячейки считаются соседними, если они граничат по стороне (в направлении на север, юг, запад или восток одна от другой). Рейтинг трудности маршрута это минимальное значение D такое, что все точки маршрута взаимно достижимы при выполнении вышеописанного требования.
PROBLEM NAME: ccski
Формат входных данных
* Строка 1: Целые числа M и N.
* Строки 2..1+M: Каждая из этих M строк содержит N целых высот.
* Строки 2+M..1+2M: Каждая из этих M строк содержит N величин 0 или 1, 1 указывает, что данная высота – точка маршрута гонки.

Формат выходных данных
* Строка 1: Рейтинг трудности маршрута (минимальное значение D такое, что все точки маршрута взаимно достижимы)
Примечание
Если D = 21, то все 3 точки маршрута взаимно достижимы. Если D<21 верхняя правая точка не достижимы из других двух.

Бинарный поиск по ответу графы Обход в ширину

—Войти и решать

What's Up With Gravity#89915

Капитан (C) должен спасти доктора (D). Все происходит на двумернйо решетке NxM (1<=N,M<=500). Некоторые из ячеек пусты (и по ним можно двигаться), а некоторые блокированы (и по ним нельзя двигаться).
Движение подчиняется следующим законам:
1) Если под Капитаном нет ячейки (он находится на краю решетки), то он падает в бездну и миссия спасения не выполнена 2) если под Капитаном есть пустая ячейка, но падает в нее. 3) Иначе a) Капитан может двигаться влево или вправо, если соответствующая ячейка существует и пуста. б) Капитан может переключить направление гравитации.
Когда капитан переключает направление гравитации, ячейка которая "под ним" (в смысле правил 1 и 2) переключается между ячейками с большим индексом и ячейками с меньшим индексом. Первая строка имеет индекс 1, последняя строка имеет индекс N.
Помогите Капитану найти Доктора используя минимальное количество переключений гравитации. Если Капитан не может добраться до клетки с Доктором - выведите -1.
PROBLEM NAME: gravity
Формат входных данных
* Строка 1: Два разделенных пробелом целых числа N и M.
* Строки 2..1+N: Строка i+1 описывает i-ую строку решетки: '.' обозначает пустую клетку, '#' обозначает блокированную клетку, 'C' обозначает стартовую позицию Капитана, 'D' обозначает позицию Доктора.
Формат выходных данных
* Строка 1: Одно целое число - минимальное количество раз, когда Капитан переключал гравитацию, или -1, если Капитану не возможно добраться до Доктора.
Примечание
Капитан начинает в позиции (4,2). Он переключает гравитацию и падает в позицию (2,2) затем двигается вправо дважды и попадает в точку (2,4). Переключает гравитацию снова и падает в позицию (4,4), затем двигается вправо в позицию (4,5). Переключает гравитацию опять и падает в позицию Доктора в клетке (3,5).

Обход в ширину

—Войти и решать

Milk Scheduling#89876

N (1 <= N <= 10,000) коров Фермера Джона пронумерованы последовательно от 1 до N. Для доения коровы i требуется T(i) единиц времени. Однако некоторые коровы необходимо подоить ранее других (из-за их положения на ферме). Если корову A требуется подоить перед коровой B, ФД должен полностью закончить дойку коровы A, прежде чем начать дойку коровы B.
Для того, чтобы подоить всех своих коров как можно быстрее, ФД нанял большое количество доярок - достаточно для того чтобы доить любое количество коров одновременно.
Определите минимальное количеатво времени, требуемое для дойки всех коров.

PROBLEM NAME: msched
Формат входных данных
* Строка 1: Два разделенных пробелом целых числа: N (количество коров) и M (количество ограничений).
* Строки 2..1+N: Строка i содержит значение T(i).
* Строки 2+N..1+N+M: Каждая строка содержит два разделенных пробелом целых числа A и B, означающих, что корова A должна быть полностью подоена, прежде чем приступать к дойке коровы B.

Формат выходных данных
* Строка 1: Минимальное количество времени, требуемое чтобы подоить всех коров.
Примечание
Коров 1 и 3 можно начинать доить сразу и делать это одновременно. Когда закончится дойка коровы 3, можно начинать дойку коровы 2. Через 11 единиц времени закончится дойка всех коров.

Топологическая сортировка

—Войти и решать

Perimeter#89872

Фермер Джон выстроил N (1 <= N <= 10,000) стогов сена в одном из своих полей. Мы рассмотрим это поле как решетку 100 х 100 из квадратных ячеек 1 х 1, где каждый стог сена занимает ровно одну ячейку. Никакие два стога не находятся в одной и той же ячейке.

ФД заметил, что его стоги всегда образуют один большой связный регион, что означает, что начиная с любого стога сена можно достичь любого другого стога сена с помощью серии шагов в строго соседнюю клетку в одном из четырех направлений: север, юг, запад, восток.
Однако этот связный регион может содержать "дыры" - пустые регионы, которые полностью окружены стогами.
Помогите ФД определить периметр региона, сформированный его стогами. Учитывайте, что дыры не вносят вклад в периметр.
PROBLEM NAME: perimeter
Формат входных данных
* Строка 1: Количество стогов, N.
* Строки 2..1+N: Каждая строка содержит(x,y) - положение одного стога где x и y целые числа в диапазоне 1..100. Позиция (1,1) это левый нижний угол поля ФД, а позиция (100,100) это правый верхний угол поля.
Формат выходных данных
* Строка 1: периметр связного региона стогов.
Примечание
Длина периметра равна 14, например левая сторона имеет длину 3. Заметьте, что дыра в середине не вносит значение в периметр.

Поиск компонент связности

—Войти и решать

Unlocking Blocks (Silver)#89860

Коровы любят головоломки. Фермер Джон подарил Беси на день рождения новую головоломку. Она состоит из трех твердых объектов, каждый из которых состоит из склеенных вместе квадратиков размера 1 х 1. Каждый из этих объектов имеет «связную» форму в том смысле, что Вы можете перейти из одного квадратика в любой другой, двигаясь по квадратикам этого объекта в одном из четырех направлений: север, юг, запад, восток.
Объект может перемещаться последовательно скольжением на одну единицу в одном из четырех направлений: север, юг, запад, восток. Цель головоломки - переместить объекты так, чтобы они разделились – то есть, чтобы граничные квадратики отошли друг от друга. Ваша задача – по заданным трем объектам определить, можно их разделить, или нет. Конфигурация, которую разделить нельзя, называется заблокированной.

Замечание: программы, которые не делают ничего, кроме угадывания ответа, могут быть дисквалифицированы.
PROBLEM NAME: unlock
Формат входных данных
* Строка 1: Три разделенных одиночными пробелами целых числа: N1, N2, and N3, описывающих количество квадратов соответственно в фигурах 1, 2, и 3.
* Строки 2..1+N1: Каждая из этих строк описывает (x,y) координату юго-западного угла одного квадрата объекта 1. Все координаты в интервале 0..9.
* Строки 2+N1..1+N1+N2: Каждая из этих строк описывает (x,y) координату юго-западного угла одного квадрата объекта 2. Все координаты в интервале 0..9.
* Lines 2+N1+N2..1+N1+N2+N3: Каждая из этих строк описывает (x,y) координату юго-западного угла одного квадрата объекта 1. Все координаты в интервале 0..9.
Формат выходных данных
* Строка 1: Минимальное количество шагов, которое необходимо выполнить, чтобы разделить три объекта или -1, если объекты не могут быть разделены.
Примечание
Если мы сдвинем объект 3 на 4 позиции на восток, а затем объект 2 на одну позицию на север и затем на 3 позиции на восток, то границы трех фигур разъединятся.

графы Задачи на моделирование Обход в ширину

—Войти и решать

Balanced Trees#89846

Ферма Джона - гигантское дерево из N пастбищ (1 <= N <= 40,000), каждое из которых помечено символом ( или символом ).
Например:
'('--'('--')'--'('--')' | | ')' ')'--'('--'(' | | ')' '('--')'--')'--')'--'('
Поскольку ферма дерево - то некоторые пары пастбищ соединены дорожками, так что существует уникальный путь между любыми двумя парами пастбищ. Некоторые из этих путей представляют сбалансированные строки скобок. Теперь ФД хочет узнать какова максимальная глубина вложенности среди всех сбалансированных строк представляющих эти пути.
Максимальной глубиной вложенности сбалансированной строки скобок называется максимальное превышение количества левых скобок над правыми среди всех префиксов этой строки. Например, для строки ()()() максимальная глубина вложенности - 1, а для строки ((()))() максимальная глубина вложенности - 3:
((()))() 12321010
Для примера фермы, представленного выше "наиглубокая" строка есть ((())), ее глубина равна 3, а строка получается по пути из A в B:
'('--'('--')'--'('--')' | | ')' ')'--'('--'(' < A | | ')' '('--')'--')'--')'--'(' ^C ^B
Заметим, что она отличается от самой длинной сбалансированной строки (())(()), которая начинается в A, заканчивается в C и имеет длину 8.
Ваша задача - вывести максимальную глубину вложенности среди путей на данном дереве.
PROBLEM NAME: btree
Формат входных данных
* Строка 1: Одно целое число N, количество вершин в дереве.
* Строки 2..N: Строка i+1: Одно целое число p_(i+1) (1 <= p_(i+1) <= i), означающее, что существует ребро между вершинами I+1 и P_(I+1) в этом дереве.
* Строки N+1..2N: Строка N+i: Или ( или ), метка вершины i.
Формат выходных данных
* Строка 1: Одно целое число - максимальная глубина вложенности среди всех сбалансированных путей

Деревья

—Войти и решать

Tractor#89841

Фермер Джон оставил свой трактор в середине поля. Коровы решили подшутить над ФД. Они разместили N стогов сена (1 <= N <=50,000) в различных участках поля, так что ФД не может забрать трактор не удалив некоторые из них.
Местоположение трактора и стогов сена - это точки на декартовой плоскости с целочисленными координатами от 1 до 1000. Нет стогов сена в позиции трактора. Трактор ФД может двигаться только параллельно осям координат (на север, юг, запад и восток) на целое количество единиц. Трактор не может проходить через точку, в которой имеется стог сена.
Пожалуйста, помогите ФД определить минимальное количество стогов сена, которые придется убрать, чтобы он мог привести трактор в начало координат.
PROBLEM NAME: tractor
Формат входных данных
* Строка 1: Три разделенных пробелом целых числа N x y (x,y) - начальные координаты трактора
* Строки 2..1+N: Каждая строка содержит (x,y)-координаты стога сена

Формат выходных данных
* Строка 1: Минимальное количество стогов сена, которое ФД должен удалить для того, чтобы обеспечить путь своему трактору к началу координат.
Примечание
Достаточно удалить только 1 стог.

Обход в ширину

✓ 1✗ 12—Войти и решать

Running Away From the Barn#89811

Время дойки на ферме Джона, но коровы сбежали. Ферма Джона - это множество из N (1 <= N <= 200,000) пастбищ, пронумерованных от 1 до N, и связанных N - 1 двунаправленными дорожками. Амбар расположен в пастбище 1 и любое пастбище достижимо от амбара.
Коровы бегут в сторону "от амбара" и они пробегают расстояние не больше чем L. Для каждого пастбища ФД хочет знать, в скольки различных пастбищах могут оказаться коровы, сбежавшие с этого пастбища.
Замечание: используйте 64-битные целые (int64 в Pascal, long long в C/C++ и long в Java) для хранения расстояний.
PROBLEM NAME: runaway
Формат входных данных
* Строка 1: 2 целых числа, N и L (1 <= N <= 200,000, 1 <= L <= 10^18)
* Строки 2..N: i-ая строка содержит два целых числа p_i и l_i. p_i (1 <= p_i < i) - первое пастбище на кратчайшем пути между пастбищем i и амбаром l_i (1 <= l_i <= 10^12) - длина этого пути
Формат выходных данных
* Строки 1..N: По одному числу в строке. Число в строке i - количество пастбищ, которые могут быть достигнуты из пастбища i, выбирая дороги, строго удаляясь от амбара (пастбище 1) с суммарной длиной не превышающей L.
Примечание
Корова из пастбища 1 может добежать до пастбищ 1, 2, 4. Корова из пастбища 2 может добежать до пастбищ 2, 3. Пастбища 3 и 4 - конечные, оттуда некуда бежать, можно только остаться в них.

Дерево отрезков, RSQ, RMQ Деревья

✓ 0✗ 1—Войти и решать

First!#89809

Беси опять играет со строками. Она обнаружила, что изменяя порядок алфавита она може добиться, чтобы некоторая строка стала лексикографически раньше всех.
Например, среди строк
"omm", "moo", "mom", "ommnom"
она может сделать первой строку "mom", используя стандартный алфавит. и она может сделать первой строку "omm" используя алфавит "abcdefghijklonmpqrstuvwxyz". Однако Беси не знает как сделать первым слово "moo" или "ommnom"
Помогите Беси вычислить строки из ввода, которые можно сделать первыми изменив порядок букв в алфавите.
Чтобы определить, что строка X лексикографически раньше cтроки Y найдите индекс первого символа в котором они различаются j. Если такого индекса нет, тогда X лексикографически меньше чем Y, если X короче чем Y, иначе, X лексикографически раньше чем Y, если X[j] находится в алфавите раньше чем Y[j].

PROBLEM NAME: first
Формат входных данных
* Строка 1: целое N (1 <= N <= 30,000),количество строк, с которыми играет Беси
* Строки 2..1+N: Каждая строка содержит не пустую строку символов. Общее количество символов во всех строках не превысит 300,000. Все символы на вводе - маленькие латинские буквы от 'a' до 'z'. Во вводе нет повторяющихся строк.

Формат выходных данных
* Строка 1: одно число K, количество строк, которые могут быть лексикографически первыми.
* Строки 2..1+K: (1+i)-ая строка должна содержать i-ую строку, которая может быть лексикографически первой. Строки нужны выводить в том же порядке, в котором они следовали на вводе.
Примечание
Только "omm" и "mom" могут стать первыми.

Бор графы Топологическая сортировка

✓ 1✗ 1—Войти и решать

Cow Beauty Pageant (Silver Level)#89803

Problem 1: Cow Beauty Pageant (Silver Level) [Brian Dean]
Прослышав, что модно иметь коров с тремя пятнами, Фермер Джон купил целое стадо таких коров. К несчастью, мода меняется очень быстро, и сейчас в моде коровы с одним пятном.
ФД теперь хочет подкрасить своих коров так, чтобы они стали с одним пятном. Раскраска коровы задается двумерным массивом символов (N*M), например, так:
................ ..XXXX....XXX... ...XXXX....XX... .XXXX......XXX.. ........XXXXX... ..XXX....XXX....
Здесь 'X' обозначает часть пятна. Два символа 'X' принадлежат одному и тому же пятну, если они соседние вертикально или горизонтально (диагональные соседними не являются). Все коровы ФДЖ имеют ровно 3 пятна.
ФД хочет потратить как можно меньше краски, чтобы объединить три пятна в одно. На примере выше, он может сделать это, покрасив только 4 позиции, они обозначены символом ‘*’ на рис. ниже.
................ ..XXXX....XXX... ...XXXX*...XX... .XXXX..**..XXX.. ...*....XXXXX... ..XXX....XXX....
Помогите ФД определить минимальное количество клеток(символов), которые нужно закрасить, чтобы объединить три пятна в одно.
PROBLEM NAME: pageant
Формат входных данных
* Строка 1: Два разделенных пробелом целых числа, N и M (1 <= N,M <= 50).
* Строки 2..1+N: Каждая содержит строку из M символов 'X' и '.', указывающих соответствующую линию раскраски коровы.
Формат выходных данных
* Line 1: Минимальное количество сиволов 'X', которые нужно добавить ко введенным данным, чтобы получить единое пятно.
Примечание
4 символа ‘X’ нужно добавить, чтобы получить одно пятно.

Обход в ширину

—Войти и решать

Simplifying the Farm#89792

Фермер Джон изучает программирование на вечерних курсах при местном университете и сейчас проходит тему "минимальное остовное дерево". Он осознал, что проект его фермы не оптимален, и хочет его улучшить.
Ферма сейчас организована в виде графа, вершины которого представляют поля, а ребра представляют дорожки между этим полями, с каждой ассоциирована ее длина.
ФД заметил, что для каждой длины имеется не более трех дорожек, имеющих такую длину. ФД хочет удалить некоторые из дорожек на своей ферме так, чтобы получилось дерево - то есть, чтобы существовал единственный путь между любыми двумя полями. Более того, Фд хочет, чтобы это было минимальное остовное дерево, то есть дерево, которое имеет минимально возможную сумму длин всех дорожек.
Помогите ФД вычислить не только сумму длин всех дорожек в минимальном остовном дереве, но также количество различных возможных минимальных остовных деревьев, которые он может создать.
PROBLEM NAME: simplify
Формат входных данных
* Строка 1: Два целых числа N и M (1 <= N <= 40,000; 1 <= M <= 100,000), представляющих количество вершин и ребер соответственно. Вершины пронумерованы от 1 до N.
* Строки 2..M+1: Три целых числа a_i, b_i n_i (1 <= a_i, b_i <= N; 1 <= n_i <= 1,000,000) представляющих ребро от вершины a_i до b_i длиной n_i. Никакое ребро с длиной n_i не встретиться более трех раз.
Формат выходных данных
* Строка 1: Два целых числа, представляющих длину минимального остовного дерева и количество минимальных остовных деревьев (по модулю 1,000,000,007)
Примечание
Выбрав оба ребра с длиной 1 и любое ребро с длиной 2 мы получим минимальное остовное дерево с длиной 4.

Минимальный каркас

—Войти и решать

Grass Planting#89791

У Фермера Джона есть N пастбищ (2 <= N <= 100,000), соединенных N-1 двунаправленными дорогами так, что ровно один путь существует между любыми двумя пастбищами.
Бесси, любимая корова ФД пожаловалась, что на дорогах нет травы, и ФД решил посадить траву на дорогах.
Он делает это, используя процедуру, которая состоит из M шагов. (1 <= M <=100,000).
На каждом шаге происходит одна из двух вещей:
- ФД выбирает два пастбища и высаживает траву на каждой дороге пути между ними - Бесси спрашивает, сколько дорог засажено травой на конкретном пути, и ФД должен ей ответить.
Помогите ФД отвечать на вопросы.
PROBLEM NAME: grassplant
Формат входных данных
* Строка 1: Два разделенных пробелом целых числа N и M
* Строки 2..N: Два разделенных пробелом целых числа, описывающих конечные точки дороги.
* Строки N+1..N+M: Строка i+1 описывает шаг i. Первый символ этой строки либо P либо Q, которые описывают ФД садит траву или отвечает на вопрос. Затем следуют два разделенных пробелом целых числа A_i B_i (1 <= A_i, B_i <= N), которые описывают путь (для действия или вопроса)
Формат выходных данных
* Строки 1..???: Каждая строка содержит ответ на вопрос, в порядке поступления вопросов

Деревья

—Войти и решать

Все пути до листьев#81755

Выведите все пути от корня до каждого листа дерева.

Формат входных данных
JSON с деревом решений.

Формат выходных данных
Каждый путь на отдельной строке: id узлов через пробел от корня до листа. Пути отсортированы по id конечного листа (по возрастанию).

Деревья

✓ 4✗ 0—Войти и решать

Путь к узлу#81749

Дано дерево решений и id целевого узла. Найдите путь от корня (id=0) до этого узла.

Формат входных данных
Первая строка: JSON с деревом. Вторая строка: целевой id узла.

Формат выходных данных
ID узлов от корня до целевого, через пробел.

Деревья

✓ 6✗ 0—Войти и решать

Глубина дерева#81748

Найдите максимальную глубину дерева решений. Глубина корня равна 0.

Формат входных данных
JSON с деревом решений.

Формат выходных данных
Одно целое число — глубина дерева.

Деревья

✓ 5✗ 0—Войти и решать