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

Why Did the Cow Cross the Road III#90434

Ферма Джона представляет собой квадратную решётку из $N \times N$ полей ($2 \leq N \leq 100$). Определённые пары соседних полей (север-юг или запад-восток) разделены дорогами, и высокий забор идёт вокруг периметра всей решётки, не давая коровам возможности покинуть ферму. Коровы могут свободно перемещаться с любого поля на любое соседнее поле (на сервер, юг, запад, восток), хотя они предпочитают переходить дороги только когда это абсолютно необходимо.

Имеется $K$ коров ($1 \leq K \leq 100, K \leq N^2$) на ферме, каждая расположена в различном поле. Пара коров называется "далёкой", если для того чтобы одна корова смогла посетить другую, необходимо перейти хотя бы одну дорогу. Помогите ФД посчитать количество пар удалённых коров.

ФОРМАТ ВВОДА (файл countcross.in):

Первая строка ввода содержит $N$, $K$, $R$. Следующие $R$ строк описывают $R$ дорог существующие между парами соседних полей. Каждая строка имеет вид $r$ $c$ $r'$ $c'$ (целые числа в интервале $1 \ldots N$), указывающих, что имеется дорога между соседними полями (строка $r$, колонка $c$ и строка $r'$, колонка $c'$). Последние $K$ строк описывают местоположение $K$ коров (строка, колонка).

ФОРМАТ ВЫВОДА (файл countcross.out):

Выведите количество пар "далёких" коров.

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

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

Moocast#90367

$N$ ($1 \leq N \leq 200$) коров Фермера Джона хотят организовать безопасную сеть передачи сообщений.

Каждая корова получает "воки-токи". Каждый "воки-токи" имеет ограниченный радиус передачи: "воки-токи" с мощностью $P$ может передавать сигнал на расстояние не более $P$. Заметим, что "воки-токи" однонаправленный: чтобы получить сигнал от другого "воки-токи", нужно чтобы он имел соотвествующую мощность.К счастью, коровы могут передавать по эстафете сообщения другу другу (в том числе и чужие) и поэтому нет необходимости для каждой коровы быть способной непосредственно передать сообщение каждой другой.

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

ФОРМАТ ВВОДА (файл moocast.in):

Первая строка ввода содержит $N$.

Каждая из следующих $N$ строк содержат $x$ и $y$ координаты одной коровы ( целые числа в диапазоне $0 \ldots 25,000$) за которыми следует $p$, мощность "воки-токи" этой коровы.

ФОРМАТ ВЫВОДА (файл moocast.out):

Напишите одну строку - максимальное количество коров, которым можно передать информацию от одной коровы.

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

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

Moocast#90361

$N$ ($1 \leq N \leq 1000$) коров Фермера Джона хотят организовать безопасную систему для передачи важных сообщений.

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

Коровам нужно решить сколько денег необходимо потратить на "воки-токи". Если они потратят \$X, они получат "воки-токи", способно передавать на расстояние до $\sqrt{X}$. То есть, квадрат расстояния между коровами стоит не более $X$ чтобы обеспечить их коммуникацией.

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

ФОРМАТ ВВОДА (файл moocast.in):

Первая строка ввода содержит $N$.

Каждая из $N$ последующих строк содержит $x$ и $y$ координаты одной коровы. И то и другое - целое в интервале $0 \ldots 25,000$.

ФОРМАТ ВЫВОДА (файл moocast.out):

Напишите в одну строку целое $X$ - минимальное количество денег, которое коровы должны потратить на "воки-токи"

Бинарный поиск по ответу графы Поиск компонент связности

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

Connecting Two Barns#90130

Ферма Джона состоит из множества $N$ полей $(1 \leq N \leq 10^5)$, последовательно пронумерованных $1 \ldots N$. Между этими полями имеется $M$ двунаправленных дорожек $(0 \leq M \leq 10^5)$, соединяющих пары полей.

На этой ферме имеется два амбара - один в поле $1$, другой в поле $N$. ФД хочет быть уверен, что имеется путь между двумя амбарами последовательностью дорожек. Оно готов построить до двух новых дорожек, чтобы добиться своей цели. Стоимость построения дорожки между полями $i$ и $j$ есть $(i-j)^2$.

Помогите ФД определить минимальную стоимость сделать так, чтобы амбары $1$ и $N$ стали достижимы друг для друга.

ФОРМКАТ ВВОДА (с клавиатуры / stdin):

Каждый входной тест содержит $T$ под тестов ($1\le T\le 20$), все из которых должны быть решены правильно, чтобы пройти этот тест.

Первая строка ввода содержит $T$, за которым следуют $T$ подтестов.

Каждый подтест начинается с двух целых чисел $N$ и $M$. Каждая из последующих $M$ строк содержит два целых числа $i$ и $j$, означающих путь между двумя различными полями $i$ и $j$. Гарантируется, что имеется не более одного пути между любыми двумя полями. и что сумма $N+M$ для всех подтестов не более $5 \cdot 10^5$.

ФОРМАТ ВЫВОДА (на экран / stdout):

Выведите $T$ строк. $i$-ая строка должна содержать одно целое число, минимальную стоимость для $i$-го подтеста.

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

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

Wormhole Sort#90113

Коровы Фермера Джона устали от ежедневных сортировок перед выходом из амбара. Они получили Ph.D по квантовой физике и готовы ускорить этот процесс.

Этим утром, как обычно $N$ коров ($1 \leq N \leq 10^5$), последовательно пронумерованных $1 \dots N$, находятся в амбаре на различных позициях, также пронумерованных $1 \dots N$, так что корова $i$ находится в позиции $p_i$. Однако этим утром имеется $M$ туннелей ($1 \leq M \leq 10^5$), которые пронумерованы $1 \dots M$, при этом туннель $i$ двунаправленно связывает позиции $a_i$ и $b_i$ и имеет ширину $w_i$ ( $1\le a_i,b_i\le N, a_i\neq bi, 1\le w_i\le 10^9$ ).

В любой момент времени две коровы, расположенные на противоположных концах туннеля могут параллельно поменяться позициями через него. Коровы могут таким образом меняться позициями сколько угодно раз пока корова $i$ не окажется в позиции $i$ для $1 \leq i \leq N$.

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

ОЦЕНИВАНИЕ:

Тесты 3-5 удовлетворяют ограничениям $N,M\le 1000.$
Тесты 6-10 не имеют дополнительных ограничений.

ФОРМАТ ВВОДА:

Первая строка содержит два целых числа $N$ и $M$.

Вторая строка содержит $N$ целых чисел $p_1, p_2, \dots, p_N$. Гарантируется, что $p$ есть перестановка чисел $1\ldots N.$

Для каждого $i$ между $1$ и $M$, строка $i+2$ содержит целые числа $a_i$, $b_i$, и $w_i$.

ФОРМАТ ВЫВОДА:

Одно целое число: наибольшая минимальная ширина туннеля, в которую поместится коров во время процесса сортировки. Если коровы не используют туннели во время сортировки выведите $-1$.

Бинарный поиск по ответу Поиск компонент связности

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

Fence Planning#90082

У Фермера Джона $N$ коров, последовательно пронумерованных d $1 \ldots N$ ($2 \leq N \leq 10^5$). Они организованы в сложную социальную структуру "moo networks" - маленькие группы коров взаимодействуют внутри группы, но не с другими группами.

Каждая корова расположена в точке $(x,y)$ на двумерной карте фермы. И нам известны $M$ ($(1 \leq M < 10^5)$) пар коров, принадлежащих к одной и той же группе.

ФД хочет построить прямоугольную изгородь со сторонами параллельными осям координат. ФД хочет гарантировать, что как минимум одна группа коров целиком окажется внутри изгороди. Коровы на границе, считаются принадлежащими прямоугольной изгороди. Определите минимально возможный периметр такой изгороди. Допускается, что такая изгородь может иметь нулевую ширину или высоту.

ФОРМАТ ВВОДА (файл fenceplan.in):

Первая строка ввода содержит $N$ и $M$. Каждая из следующих $N$ строк содержит $x$ и $y$ - координаты коров (неотрицательные целые числа не более $10^8$). Каждая из следующих $M$ строк содержит два целых числа $a$ и $b$, описывающих принадлежность коров с номерами $a$ и $b$ к одной группе. Каждая корова присутствует как минимум в одной из таких пар. Никакие пары во вводе не повторяются.

ФОРМАТ ВЫВОДА (файл fenceplan.out):

Выведите минимальный периметр, удовлетворяющий ограничениям ФД.

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

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

Icy Perimeter#90070

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

Конфигурация мороженого, которое производится машиной, может быть описано решёткой $N \times N$ grid ($1 \leq N \leq 1000$):

##....
....#.
.#..#.
.#####
...###
....##

Каждый символ '.' представляет пустое место, а каждый символ '#' представляет $1 \times 1$ квадратную ячейку мороженого.

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

ФД хочет найти площадь и периметр сгустка, который имеет наибольшую площадь. Площадь сгустка равна количеству символов '#' в его картинке. Если несколько сгустков имеют одинаковую площадь, он хочет знать минимальный периметр из них. На рисунке выше, маленький сгусток имеет площадь 2 и периметр 6, а больший сгусток имеет площадь 13 и периметр 22.

Заметим, что сгусток может иметь "дыру" внутри (пустое пространство, окружённое мороженым). В таком случае граница "дыры" также учитывается в периметре сгустка. Сгусток может находиться внутри другого сгустка, в этом случае они рассматриваются как независимые сгустки. Например, ниже представлен сгусток площади 1 внутри сгустка площади 16:

#####
#...#
#.#.#
#...#
#####

ФОРМАТ ВВОДА (файл perimeter.in):

Первая строка ввода содержит $N$, а следующие $N$ строк описывают вывод машины. Присутствует, как минимум, один символ '#'.

ФОРМАТ ВЫВОДА (файл perimeter.out):

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

Задачи на моделирование Клеточная геометрия Поиск компонент связности

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

Milk Visits#90046

Фермер Джон построил $N$ ($1 \leq N \leq 10^5$) ферм, соединённых $N-1$ дорогами, формируя дерево (то есть, каждая ферма достижима от любой другой, и отсутствуют циклы). Каждая ферма содержит коров, чья марка Guernsey или Holstein.

$M$ друзей ФД ($1 \leq M \leq 10^5$) часто посещают его фермы. Во время визита друга $i$, ФД идёт с эти другом по уникальному маршруту от фермы $A_i$ до фермы $B_i$ (возможен случай, когда $A_i = B_i$). Дополнительно они могут попробовать некоторое количество молока вдоль пути, по которому они идут. Поскольку большинство друзей ФД сами фермеры, у них есть сильные предпочтения по молоку. Некоторые из его друзей пьют молоко только коров Guernsey, а оставшиеся пьют только молоко Holstein. Любой из друзей ФД будет счастлив только если он сможет попить предпочитаемое молоко во время визита.

Определите, каждый ли друг останется счастлив после визита.

ОЦЕНИВАНИЕ:

Тесты 2-5 удовлетворяют $N\le 10^3, M\le 2\cdot 10^3.$

ФОРМАТ ВВОДА (файл milkvisits.in):

Первая строка содержит два целых числа $N$ и $M$.

Вторая строка содержит строку длину длины $N$. $i$-ый символ строки есть 'G' если корова на $i$-ой ферме Guernsey, или 'H', если корова на $i$-ой ферме Holstein.

Каждая их следующих $N-1$ строк содержит два целых числа $X$ и $Y$ ($1 \leq X, Y \leq N$), указывающих, что существует дорога между фермами $X$ и $Y$.

Последующие $M$ строк содержат целые числа $A_i$, $B_i$ и символ $C_i$. $A_i$ и $B_i$ представляют конечные точки пути $i$'-го друга, а $C_i$ либо G либо H - тип молока, предпочитаемый $i$-ым другом.

ФОРМАТ ВЫВОДА (файл milkvisits.out):

Выведите двоичную строку длины $M$. $i$-ый символ строки должен быть '1' если $i$-ый друг будет счастлив, или '0' в противном случае.

графы Деревья Поиск компонент связности

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

Mooyo Mooyo#89999

Имея много свободного времени, коровы Фермера Джона часто играют в видеоигры. Одна из их любимых игр похожа на Puyo Puyo. Коровья версия этой игры называется Му-Му.

Игра Му-Му происходит на высокой узкой решётке из $N$ ячеек в высоту и ($1 \leq N \leq 100$) и 10 ячеек в ширину. Вот пример для $N = 6$:

Каждая ячейка или пустая (обозначена 0) или содержит стог сена одного из 9 различных цветов (обозначенных символами 1..9). Гравитация вынуждает стоги сена падать вниз, поэтому никогда 0 не будет ниже, чем стог сена.

Две ячейки принадлежат одному и тому же связному региону, если они имеют общую вертикальную или горизонтальную сторону и один и тот же цвет, отличный от 0. Каждый раз, когда регион начинает содержать $K$ или более ячеек, все его стоги сена исчезают - превращаются в 0. Если в один момент времени существует несколько таких регионов они исчезают все одновременно. Затем, гравитация может вынудить стоги сена заполнить некоторые из ячеек, которые стали нулевыми. В получившейся конфигурации могут снова образоваться региона размера не менее $K$ ячеек. В этом случае они также исчезают (одновременно, если есть несколько таких регионов). Затем гравитация вновь двигает вниз стоги сена и процесс повторяется, пока есть хоть один регион, в котором не менее $K$ стогов.

По заданной конфигурации доски для Му-Му вычислите финальную картинку доски после выполнения всех операций.

ФОРМАТ ВВОДА (файл mooyomooyo.in):

Первая строка ввода содержит $N$ и $K$ ($1 \leq K \leq 10N$). Оставшиеся $N$ строк задают начальное состояние доски.

ФОРМАТ ВЫВОДА (файл mooyomooyo.out):

Выведите $N$ строк, описывающих финальное состояние поля.

Задачи на моделирование Поиск компонент связности реализация

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

Closing the Farm#89966

Фермер Джон и его коровы планируют уехать на длинные каникулы, и поэтому ФД хочет временно закрыть ферму.

Ферма состоит из $N$ амбаров, соединённых $M$ двунаправленными дорожками между некоторыми парами амбаров ($1 \leq N, M \leq 200,000$). ФД закрывает один амбар за раз. После того как амбар закрыт, все дорожки, прилегающие к нему тоже становятся закрытыми и не могут больше использоваться.

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

ФОРМАТ ВВОДА (файл closing.in):

Первая строка ввода содержит числа $N$ и $M$. Каждая из следующих $M$ строк описывает дорожку , задавая пару амбаров, которые она соединяет (амбары пронумерованы последовательно $1 \ldots N$). Последние $N$ строк задают перестановку $1 \ldots N$ описывающую порядок, в котором будут закрываться амбары.

ФОРМАТ ВЫВОДА (файл closing.out):

Вывод содержит $N$ строк, каждая есть "YES" или "NO". Первая строка отвечает на попрос была ли ферма полностью связанной изначально, а далее строка $i+1$ указывает, осталась ли ферма полностью связной после $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).

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

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

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: Два разделённых пробелом целых числа, описывающих количество регионов в этом рисунке для человека и коровы.

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

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

Tractor#89878

Одно из полей Фермера Джона весьма холмисто. И он хочет купить новый трактор для работы на этом поле. Поле описывается решеткой из N x N (1 <= N <= 500) неотрицательных целых высот ячеек. Трактор может перемещаться из ячейки в соседнюю (на один шаг на север, юг, запад или восток), с разницей их высот D ровно за D единиц денег.
ФД хочет заплатить достаточно, так чтобы его трактор, начиная с некоторой ячейки поля мог посетить как минимум половину ячеек поля. Если число ячеек в поле - нечетное, то половина, округленная вверх.
Определите минимальную стоимость покупки трактора способного выполнить эту задачу.

PROBLEM NAME: tractor
Формат входных данных
* Строка 1: Значение N.
* Строки 2..1+N: Каждая строка содержит N разделенных одиночными пробелами неотрицательных целых чисел (каждое не более миллиона), определяющих строку поля ФД.
Формат выходных данных
* Line 1: Минимальная стоимость трактора, который способен объехать не менее половины этого поля.
Примечание
Трактор стоимостью 3 способен перемещаться из ячейки с высотой 0 в ячейку с высотой 3. Поэтому он может посетить все ячейки с высотами 0 и 3. Вместе они представляют не менее половины фермы.

Бинарный поиск по ответу Обход в ширину Поиск компонент связности

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

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. Заметьте, что дыра в середине не вносит значение в периметр.

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

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

65817#65817

В далёком заснеженном города Снежнокрибирске очень мало пеших тропинок, так как город просто не успевает их чистить, потому люди передвигаются в основном только на внедорожниках: ездят в магазин, отвозят детей в школу, ездят на работу и так далее.
В один из последних дней перед зимними каникулами ребятам в школе задали проект на каникулы, который можно делать как самому, так и в группе, но не более 3 человек. Но так как проект связан с совместной работой, а в городе нет никакой связи: ни телефонной, ни интернета, то ребята решили собираться у кого-нибудь дома, чтобы делать проект вместе. Так как проект может делать до трёх человек, то ученики составили карту своих домов в городе, а также отметили на них тропинки. У них встал вопрос о том, как делать большинство проектов максимальным возможным количеством человек, но так, чтобы как можно меньше учеников делали проект одни. Помогите ребятам по описанию карты их города и тропинкам составить возможный план, как им лучше распределить проекты между собой.

Формат входных данных
На первой строке подаются два числа N, M (1 <= N,M <= 100) – количество домов и тропинок между ними соответственно.
Далее на M строках подаются дорожки в виде номеров домов (если существует дорога 1-2, то значит существует дорожка и 2-1).
Формат выходных данных
Выведите на первой строке количество учеников, которые делают проект в одиночку.
На второй – количество групп учеников, делающих проект в паре.
На третьей – количество групп учеников, делающих проект втроём.

Примечание: ребята стараются разбиться на группы по максимуму человек (по 3), если остался кто-то один, но он мог делать проект не один, то стараемся минимизировать одиночек.

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

✓ 32✗ 58800средняяВойти и решать

Водостоки#55446

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

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

Разрешается в некоторых квадратах построить водостоки. Когда на каком-то квадрате строят водосток, то вся вода, которая раньше скапливалась в этом квадрате, будет утекать в водосток.

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

Требуется определить, какое минимальное количество водостоков нужно построить, чтобы после дождя вся вода утекала в водостоки.

Входные данные
В первой строке записаны числа N и M, задающие размеры карты — натуральные числа, не превышающие 100. Далее идет N строк, по M чисел в каждой, задающих высоту квадратов карты над уровнем моря. Высота задается натуральным числом, не превышающим 10000. Считается, что квадраты, расположенные за пределами карты, имеют высоту 10001 (то есть вода никогда не утекает за пределы карты).

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

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

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

Ski Course Rating#27302

Лыжный маршрут описывается M x N решеткой высот (1 <= M,N <= 500), каждая высота в интервале 0 .. 1,000,000,000.

Некоторые из этих ячеек помечены как стартовые точки маршрута. Организаторы хотят вычислить рейтинг трудности каждой стартовой точке. Рейтинг трудности стартовой точки P – это минимальное число D такое, что корова сможет успешно достичь как минимум T ячеек решётки (1 <= T <= MN), если она стартует в P и может двигаться в соседнюю ячейку (на север, юг, запад или восток), только если абсолютная величина разности высот в этих ячейках не превосходит D.

Вычислите рейтинг трудности для каждой стартовой точки и выведите их сумму.

INPUT FORMAT:

* Строка 1: Целые числа M, N, T.

* Строки 2..1+M: Каждая из этих M строк содержит N целых высот.

* Строки 2+M..1+2M: Каждая из этих M строк содержит N величин равных 0 или 1, где 1 означает, что это ячейка – стартовая точка

OUTPUT FORMAT:

* Строка 1: Сумма рейтингов трудности всех стартовых точек (заметим, что это число может не поместиться в 32-битное целое, даже если каждый рейтинг в отдельности поместится).

INPUT DETAILS:

Местность описывается решеткой из 3 х 5 высот.

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

Из каждой стартовой точки мы должны быть способны добраться до 10 ячеек.

OUTPUT DETAILS:

Рейтинг трудности верхнего левого угла равен 4.

Рейтинг трудности правого нижнего угла равен 20.

Ввод	Вывод
3 5 10 20 21 18 99 5 19 22 20 16 17 18 17 40 60 80 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1	24

Бинарный поиск по ответу графы Поиск компонент связности

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

Легкая, вариант -2#24896

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

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

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

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

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

В первой строке находится натуральное число n (2 ≤ n ≤ 100) — количество сотрудников в фирме.

Следующая строка содержит n-1 натуральное число — номера непосредственных начальников сотрудников с номерами от 2 до n в соответствующем порядке. Числа отделены друг от друга одним пробелом. Гарантируется, что номер непосредственного начальника очередного сотрудника меньше номера самого сотрудника.

Следующая строка содержит одно натуральное число x (1 ≤ x ≤ n) — номер отправляемого в командировку сотрудника.

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

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

Пример входных и выходных данных

Ввод	Вывод
9 1 2 1 4 4 2 7 8 2	4

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

✓ 32✗ 57500лёгкаяВойти и решать

Легкая, вариант-1#24758

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

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

В первой строке находится натуральное число n (2 ≤ n ≤ 100) — количество сотрудников в фирме.

Следующая строка содержит одно натуральное число x (1 ≤ x ≤ n) — номер отправляемого в командировку сотрудника.

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

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

Пример входных и выходных данных

Ввод	Вывод
9 1 2 1 4 4 2 7 8 2	5

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

✓ 41✗ 67600лёгкаяВойти и решать

Друзья#21825

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

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

В первой строке входного файла INPUT.TXT заданы два числа: N и S (1 <= N <= 100; 1 <= S <= N), где N - количество человек в клубе, а S – номер конкретного человека. В следующих N строках записано по N чисел - матрица смежности, состоящая из единиц и нулей. Причем единица, стоящая в i-й строке и j-м столбце гарантирует, что люди с номерами i и j – друзья, а 0 – выражает неопределенность.

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

В выходной файл OUTPUT.TXT выведите количество гарантированных друзей у человека с номером S, помня о транзитивности дружбы.

Пример

Ввод:

3 1

0 1 0

1 0 1

0 1 0

Вывод
2

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

✓ 0✗ 51 200средняяВойти и решать