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

67 задачвместе с подтемами
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.
РейтингЛюбойдо 800800–11991200–15991600+Без рейтинга
СначалаПодходящиеНовыеПопулярныеПростыеСложные
3.5. Алекс и настройка радиосвязи#100096

Алекс настраивает связь между исследовательскими станциями. Есть n станций и m возможных двусторонних каналов. Канал между станциями u и v начинает работать, если общая настройка мощности P не меньше указанного для него порога w.

Сообщение нужно передать со станции s на станцию t, использовав не более k каналов подряд. Использование одного канала считается одним переходом. Промежуточные станции могут пересылать сообщение.

Найдите минимальную целую мощность P ≥ 0, при которой это возможно. Если подходящего маршрута нет даже при работающих всех каналах, сообщите об этом.

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

Первая строка содержит пять целых чисел n, m, k, s, t (2 ≤ n ≤ 50 000, 0 ≤ m ≤ 100 000, 1 ≤ k ≤ n − 1, 1 ≤ s, t ≤ n, s ≠ t).

Следующие m строк содержат u, v, w (1 ≤ u, v ≤ n, u ≠ v, 0 ≤ w ≤ 109). Между одной парой станций не более одного канала.

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

Выведите минимальную мощность либо −1, если передать сообщение за допустимое число переходов невозможно.

Пояснения к примерам

Пример 1. При мощности 7 подходит маршрут 1 → 3 → 5. При мощности 6 доступен маршрут 1 → 3 → 4 → 5, но он слишком длинный.

Пример 2. Связь существует, но сообщение должно пройти два канала, а разрешён только один.

АлгоритмыБинарный поиск по ответуОбход в ширину
—Войти и решать
3.4. Алекс и ночной музей#100095

Алекс тестирует навигацию в музее. План музея — прямоугольная таблица из n строк и m столбцов. Клетка # занята стеной, клетка . свободна. В клетке S находится Алекс, а в клетке T — пульт управления.

За один шаг можно перейти в соседнюю по стороне свободную клетку. Клетки S и T тоже свободны. Выходить за границы таблицы нельзя.

Найдите минимальное количество шагов от S до T и число различных маршрутов такой длины. Маршруты различны, если различаются последовательности посещённых клеток. Количество маршрутов выведите по модулю 1 000 000 007.

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

Первая строка содержит целые числа n и m (1 ≤ n, m ≤ 500, 2 ≤ nm ≤ 200 000). Далее идут n строк по m символов ., #, S, T. Символы S и T встречаются ровно по одному разу и находятся в разных клетках.

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

Выведите два целых числа: длину кратчайшего маршрута и количество таких маршрутов по модулю 1 000 000 007. Если пульт недостижим, выведите -1 0.

Пояснения к примерам

Пример 1. Можно обойти стены сверху и справа либо слева и снизу. Оба маршрута содержат пять шагов.

Пример 2. Стена полностью перекрывает путь.

АлгоритмыДинамическое программирование на графахОбход в ширину
—Войти и решать
1.4. Алекс и одноразовый пропуск#100085

Алекс должен пройти из зала s в зал t научного центра. Есть n залов и m двусторонних переходов. Каждый переход занимает одну минуту.

Часть переходов открыта, а часть закрыта. У Алекса есть одноразовый электронный пропуск: он позволяет один раз пройти по одному закрытому переходу. После использования пропуск исчезает, а сам переход остаётся закрытым. По открытым переходам можно ходить без пропуска.

Найдите минимальное время пути. Использовать пропуск необязательно. Если добраться до цели невозможно, выведите −1.

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

Первая строка содержит целые числа n, m, s, t (1 ≤ n ≤ 100 000, 0 ≤ m ≤ 200 000, 1 ≤ s, t ≤ n). Старт и финиш могут совпадать.

Следующие m строк содержат u, v, c (1 ≤ u, v ≤ n, u ≠ v). При c = 0 переход открыт, при c = 1 — закрыт. Между парой залов не более одного перехода.

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

Выведите минимальное время в минутах либо −1, если допустимого маршрута нет.

Пояснения к примерам

Пример 1. Нужно идти 1 → 2 → 3 → 4 → 5 и использовать пропуск в конце. Быстрый переход 1 → 3 потратил бы пропуск слишком рано.

Пример 2. Чтобы пройти этот маршрут, понадобились бы два пропуска.

АлгоритмыОбход в ширину
—Войти и решать
План эвакуации#97010

Этаж здания представляет собой прямоугольник из \(n\times m\) квадратных комнат. Из каждой комнаты есть проходы в соседние комнаты. В двух комнатах находятся лестницы. Необходимо разработать план эвакуации — указать для каждой комнаты направление движения в одну из соседних комнат так, чтобы, передвигаясь по комнатам только в указанных направлениях, можно было бы достичь одной из двух лестниц, пройдя минимальное расстояние.

На рисунке изображён возможный план эвакуации для примера из условия. Комнаты с лестницами обозначены звёздочками.

image

Первая строка входных данных содержит число \(n\) — количество строк в плане эвакуации, \(1\le n\le 100\). Вторая строка входных данных содержит число \(m\) — количество столбцов в плане эвакуации, \(2\le m\le 100\). Следующие две строки содержат числа \(r_1\) и \(c_1\) — номера строки и столбца комнаты, в которой находится первая лестница, \(1\le r_1\le n\), \(1\le c_1\le m\). Следующие две строки содержат числа \(r_2\) и \(c_2\) — номера строки и столбца комнаты, в которой находится вторая лестница, \(1\le r_2\le n\), \(1\le c_2\le m\). Гарантируется, что \(r_1\ne r_2\) или \(c_1\ne c_2\). Строки нумеруются сверху вниз числами от 1 до \(n\), столбцы нумеруются слева направо числами от 1 до \(m\).

Программа должна вывести \(n\) строк, каждая строка должна содержать \(m\) символов. Каждый символ соответствует одной комнате. В двух комнатах с лестницами должен находиться символ <<S>> (прописная английская буква). В остальных комнатах находятся символы, указывающие направление движения:

<<<>> (символ <<меньше>>) — налево.

<<>>> (символ <<больше>>) — направо.

<<^>> (символ находится на клавише <<6>>) — вверх.

<<v>> (строчная английская буква) — вниз.

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

 

Решения, правильно работающие, когда \(n=1\), будут оцениваться в 20 баллов.

Решения, правильно работающие, когда \(c_1=c_2\), будут оцениваться в 20 баллов.

Решения, правильно работающие, когда лестницы находятся в двух противоположных углах здания, будут оцениваться в 20 баллов.

Обход в ширину
✓ 5✗ 1—Войти и решать
Cow Navigation#90394

Амбар описывается решёткой \(N \times N\) (\(2 \leq N \leq 20\)) символов, некоторые из них пусты, некоторые заняты. Бесси начинает в левом нижнем углу (1,1) и должна пройти в правый верхний угол \(N,N\). Вы можете управлять ею посредством последовательности инструкций вида "вперёд", "повернись влево на 90 градусов", "повернись вправо на 90 градусов". Вы хотите задать кратчайшую последовательность, которая приведёт ее к цели. Есл инструкицю выполнить невозможно, Бесси пропускает её и переходит к следующей инструкции.

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

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

Первая строка ввода содержит \(N\).

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

Каждый символ или H (непроходимы стог сена) или E - пустая ячейка.

Гарантируется, что ячейки 1,1 и \(N,N\) будут пустые, также гарантируется существование пути по пустым ячейкам из 1,1 в \(N, N\).

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

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

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

3
EHE
EEE
EEE

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

9

В этом примере Инструкции "Вперёд, Вправо, Вперёд, Вперёд, Влево, Вперёд, Влево, Вперёд, Вперёд" приведут Бесси к назначению вне зависимости от начальной ориентации.

Problem credits: Brian Dean

Обход в ширину
—Войти и решать
Lasers and Mirrors#90360
Коровы Фермера Джона любят производить лазерные шоу.

Для своего последнего шоу, они купили огромный мощный лазер - такой большой, что они не смогли перместить его легко из того места, где он был приобретен. Он хотят послать свет от лазера в амбар ФД. И лазер, и амбра могут рассматриваться как точки на плоскости - карте фермы ФД. В панах коров направить лазер так, чтобы он послал лч света горизонтально или вертикально (то есть вдоль оси x или вдоль оси y). Затем они планируют ментяь направление луча посредством зеркал, чтобы направить луч в амбар.

На этой ферме есть \(N\) (\(1 \leq N \leq 100,000\)) точек изгороди, расположенных в различных точках на плоскости, (и отличающихся также от точек лазера и амбара), на которых могут крепится зеркала. Коровы могут выбрать не крепить зеркало к некоторым точкам, тогда луч просто проходит через эту точку без поворотов (не меняя направление). Если коровы монтируют зеркало в точке изгороди, они выравнивают его диагонально так / или так \, что соответсвенно пернаправляет горизонтальный в вертикальный и наоборот.

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

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

Первая строка ввода содержит 5 целых чисел, разделённых одиночными пробелами. \(N, x_L, y_L, x_B, y_B\), где \((x_L, y_L)\) - это размещение лазера, \((x_B, y_B)\) - размещение амбара. Все координаты между \(0\) и \(1,000,000,000\).

Каждая из следующих \(N\) строк содержит \(x\) и \(y\) - координаты точек изгороди - целые числа в интервале \(0 \ldots 1,000,000,000\).

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

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

Обход в ширину
—Войти и решать
Switching on the Lights#90355
Фермер Джон недавно построил огромный амбар, состоящий из \(N \times N\) решётки комнат, (\(2 \leq N \leq 100\)), пронумерованных от \((1,1)\) до \((N,N)\). Беси, будучи коровой которая боится темноты, хочет включить свет в как можно большем количестве комнат.

Беси начинает в комнате \((1,1)\), - единственной комнате, в которой изначально был включён свет. В некоторых комнатах она найдёт переключатели, которые могут переключать свет в других комнатах. Например, в комнате \((1,1)\) может находиться переключатель света в комнате \((1,2)\). Беси может ходить только в те комнаты, где уже горит свет. И также она может переходить из комнаты \((x,y)\) только в четыре соседние комнаты \((x-1,y)\), \((x+1,y)\), \((x,y-1)\), \((x,y+1)\) (или, возможно, в меньшее количество комнат, если она находится на границе решётки.

Определите максимальное количество комнат, в которые Беси может включить свет.

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

Первая строка ввода содержит целые числа \(N\) и \(M\) ($1 \leq M \leq 20,000$).

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

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

Одна строка, задающая максимальное количество комнат, в которых Беси может включить свет.

ПРИМЕР ВЫВОДА

5

Здесь Беси может использовать переключатель в комнате \((1,1)\), чтобы включить свет в комнатах \((1,2)\) и \((1,3)\). Затем она может перейти в комнату \((1,3)\) и включить свет в комнате \((2,1)\), где она может включить свет в комнате \((2,2)\). Переключатель в комнате \((2,3)\) недоступен для неё, поскольку он находится в комнате, где свет не включён. Поэтому Беси может посетить не более 5 комнат.

Авторы: Austin Bannister и Brian Dean

графыОбход в ширину
—Войти и решать
Switching on the Lights#90352
Фермер Джон недавно построил огромный амбар, состоящий из \(N \times N\) решётки комнат, (\(2 \leq N \leq 100\)), пронумерованных от \((1,1)\) до \((N,N)\). Беси, будучи коровой которая боится темноты, хочет включить свет в как можно большем количестве комнат.

Беси начинает в комнате \((1,1)\), - единственной комнате, в которой изначально был включён свет. В некоторых комнатах она найдёт переключатели, которые могут переключать свет в других комнатах. Например, в комнате \((1,1)\) может находиться переключатель света в комнате \((1,2)\). Беси может ходить только в те комнаты, где уже горит свет. И также она может переходить из комнаты \((x,y)\) только в четыре соседние комнаты \((x-1,y)\), \((x+1,y)\), \((x,y-1)\), \((x,y+1)\) (или, возможно, в меньшее количество комнат, если она находится на границе решётки.

Определите максимальное количество комнат, в которые Беси может включить свет.

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

Первая строка ввода содержит целые числа \(N\) и \(M\) ($1 \leq M \leq 20,000$).

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

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

Одна строка, задающая максимальное количество комнат, в которых Беси может включить свет.

ПРИМЕР ВЫВОДА

5

Здесь Беси может использовать переключатель в комнате \((1,1)\), чтобы включить свет в комнатах \((1,2)\) и \((1,3)\). Затем она может перейти в комнату \((1,3)\) и включить свет в комнате \((2,1)\), где она может включить свет в комнате \((2,2)\). Переключатель в комнате \((2,3)\) недоступен для неё, поскольку он находится в комнате, где свет не включён. Поэтому Беси может посетить не более 5 комнат.

Авторы: Austin Bannister и Brian Dean

графыОбход в ширину
—Войти и решать
Bessie's Dream#90341
После столь обильного поедания фруктов на кухне Фермера Джона, Беси посетили странные мечты. Она попала в лабиринт в форме решётки клеток \(N \times M\) (\(1 \le N, M \le 1,000\)). Она начинает в левой верхней клетке и хочет попасть в правую нижнюю. Когда она стоит в клетке, он может шагнуть в любом из четырёх направлений (вверх, вниз, вправо, вверх).

Однако подождите! Каждая клетка имеет свой цвет, и каждый цвет имеет различные свойства:

  • Если клетка red (красная), то в неё ходить нельзя
  • Если клетка pink (розовая), то в неё можно ходить
  • Если клетка orange (оранжевая), то в неё можно ходить, но Беси станет пахнуть как апельсин.
  • Если клетка blue (синяя) , то она содержит пираний, которые позволят Беси пройти только если она пахнет как апельсин.
  • Если клетка purple (пурпурная), то Беси проскальзывает в следующую клетку в этом направлении (если только в следующую клетку можно заходить). Если следующая клетка также пурпурная, Беси продолжает скользить, пока не попадёт в не пурпурную клетку или остановится перед непроходимой клеткой. Скольжение одной клетки засчитывается как один шаг. Пурпурные клетки также удаляют запах.

(Пример ниже подробнее поясняет "пурпурные" клетки)

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

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

Первая строка ввода содержит два целых числа \(N\) и \(M\), представляющие количество строк и столбцов лабиринта.

Каждая из следующих \(N\) строк имеет по \(M\) целых чисел, представляющих лабиринт:

  • Целое число '0' это красная клетка
  • Целое число '1' это розовая клетка
  • Целое число '2' это оранжевая клетка
  • Целое число '3' это синяя клетка
  • Целое число '4' это пурпурная клетка

Левая-верхняя и правая-нижняя клетки всегда будут '1'.

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

Одно целое число, представляющее минимальное количество ходов, которое должна использовать Беси, чтобы пройти лабиринт, или -1, если невозможно пройти.

Обход в ширину
—Войти и решать
Bessie's Dream#90338
После столь обильного поедания фруктов на кухне Фермера Джона, Беси посетили странные мечты. Она попала в лабиринт в форме решётки клеток \(N \times M\) (\(1 \le N, M \le 1,000\)). Она начинает в левой верхней клетке и хочет попасть в правую нижнюю. Когда она стоит в клетке, он может шагнуть в любом из четырёх направлений (вверх, вниз, вправо, вверх).

Однако подождите! Каждая клетка имеет свой цвет, и каждый цвет имеет различные свойства:

  • Если клетка red (красная), то в неё ходить нельзя
  • Если клетка pink (розовая), то в неё можно ходить
  • Если клетка orange (оранжевая), то в неё можно ходить, но Беси станет пахнуть как апельсин.
  • Если клетка blue (синяя) , то она содержит пираний, которые позволят Беси пройти только если она пахнет как апельсин.
  • Если клетка purple (пурпурная), то Беси проскальзывает в следующую клетку в этом направлении (если только в следующую клетку можно заходить). Если следующая клетка также пурпурная, Беси продолжает скользить, пока не попадёт в не пурпурную клетку или остановится перед непроходимой клеткой. Скольжение одной клетки засчитывается как один шаг. Пурпурные клетки также удаляют запах.

(Пример ниже подробнее поясняет "пурпурные" клетки)

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

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

Первая строка ввода содержит два целых числа \(N\) и \(M\), представляющие количество строк и столбцов лабиринта.

Каждая из следующих \(N\) строк имеет по \(M\) целых чисел, представляющих лабиринт:

  • Целое число '0' это красная клетка
  • Целое число '1' это розовая клетка
  • Целое число '2' это оранжевая клетка
  • Целое число '3' это синяя клетка
  • Целое число '4' это пурпурная клетка

Левая-верхняя и правая-нижняя клетки всегда будут '1'.

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

Одно целое число, представляющее минимальное количество ходов, которое должна использовать Беси, чтобы пройти лабиринт, или -1, если невозможно пройти.

Обход в ширину
—Войти и решать
Piggyback#90334

Беси и её сестра Эльза пасутся на различных полях в течение дня, а вечером обе хотят вернуться в амбар отдыхать. Будучи умными коровами, они хотят составить план, чтобы минимизировать суммарное количество энергии, которое они обе потратят на это путешествие.
Беси тратит B единиц энергии, когда она переходит с одного поля на соседнее поле, а Эльза тратит E единиц энергии при переходе на соседнее поле. Однако, если Беси и Эльза оказались на одном поле, то Беси может нести Эльзу на своих плечах, и тогда обе могут переместиться на соседнее поле, потратив только P единиц энергии, (где P может быть существенно меньше, чем B+E - количество энергии, которое затрачивается двумя коровами вместе, если они перемещаются на соседнее поле по отдельности). Если P очень маленькое, то коровам выгоднее перемещаться вместе, а если P очень большое - то по отдельности.
По заданным B, E, P и расположению полей на ферме, вычислите минимальное количество энергии, которое потребуется Беси и Эльзе, чтобы добраться до амбара.
Формат входных данных
Первая строка ввода содержит положительные числа B, E, P, N, M. Все они не превышают 40,000. B, E, P описаны выше. N - количество полей на ферме, пронумерованных от 1 до N, N>=3. M - количество дорожек между полями. Беси и Эльза начинают в полях 1 и 2 соответственно. Амбар расположен в поле N.
Каждая из следующих M строк ввода описывает дорожку между парой различных полей, указанную номерами этих полей. Дорожки двунаправленные. Всегда можно добраться от поля 1 до поля N и от поля 2 до поля N посредством некоторого количества дорожек.

Формат выходных данных
Одно целое число, указывающее минимальное количество энергии, которое суммарно потратят Беси и Эльза, чтобы добраться до амбара. В примере, приведенном выше, Беси перемещается от 1 к 4, Эльза перемещается от 2 к 3, затем к 4. Потом они перемещаются вместе от 4 к 7, затем к 8.

Обход в ширину
—Войти и решать
Telephone#90133
\(N\) коров Фермера Джона, последовательно пронумерованные, \(1 \ldots N\) выстроены в ряд (\(1\le N\le 5\cdot 10^4\)). \(i\)-ая корова имеет идентификатор породы \(b_i\) в интервале \(1 \ldots K\), with \(1\le K\le 50\). Коровы нуждаются в Вашей помощи чтобы узнать, как быстрее передать сообщение от коровы \(1\) корове \(N\).

\(|i-j|\) минут требуется, чтобы передать сообщение от коровы \(i\) к корове \(j\). Однако не все породы готовы взаимодействовать друг с другом, что описано в матрице \(S\) размером \(K \times K\), где \(S_{ij} = 1\) если корова породы \(i\) готова передать сообщение корове породы \(j\) и 0 в противном случае. Необязательно истина то, что \(S_{ij}=S_{ji}\), и даже может быть случай, когда \(S_{ii} = 0\), то есть корова породы \(i\) не будет передавать сообщение корове своей породы.

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

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

Первая строка содержит \(N\) и \(K\).

Следующая строка содержит \(N\) разделённых пробелом целых чисел \(b_1,b_2,\ldots,b_N\).

Следующие \(K\) строк описывают матрицу \(S\). Каждая строка состоит из строки из K бит. \(S_{ij}\) \(j\)-ый бит \(i\)-ой строки сверху.

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

Выведите одно целое число - минимальное количество требуемого времени. Если невозможно передать сообщение от коровы \(1\) к корове \(N\), выведите \(-1\).

графыкратчайшие путиОбход в ширину
—Войти и решать
Bucket Brigade#90072
На ферме пожар и коровы должны спасаться.

Ферма описывается решёткой \(10 \times 10\) символов: 

..........
..........
..........
..B.......
..........
.....R....
..........
..........
.....L....
..........

Символ 'B' представляет амбар, который горит. Символ 'L' представляет озеро, символ 'R' представляет огромную скалу.

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

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

Корова не может находится в квадрате, содержащем скалу, амбар или озеро. Гарантируется, что они не будут соседними друг другу.

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

Входной файл содержит 10 строк, каждая по 10 символов, описывающих план фермы.

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

Выведите одно целое число - минимальное количество коров, требуемых для того, чтобы сформировать "ведерную бригаду".

Обход в ширину
—Войти и решать
A Pie for a Pie#89979
У Беси и Эльзы по N (\(1 \leq N \leq 10^5\)) пирогов. Каждый из \(2N\) пирогов имеет величину вкусности по мнению Беси и величину вкусности (возможно отличающуюся) по мнению Эльзы.

Беси хочет отдать один из своих пирогов Эльзе. Если Эльза получит пирог от Беси, она должна будет отдать один из своих пирогов Беси. Чтобы не оказаться ни скупой, ни щедрой, Эльза постарается выбрать пирог, как минимум, такой же вкусный (по мнению Эльзы) как она получила, но не более чем на \(D\) единиц вкуснее (\(0 \leq D \leq 10^9\)). Такой пирог может не существовать, в этом случае Эльза сбежит в Японию.

Но если Эльза отдаст Беси пирог взамен, то Беси аналогично постарается отдать Эльзе пирог, как минимум такой же вкусный (по мнению Беси), но не более чем на \(D\) единиц вкуснее, чем кусок, который она получила. Если Беси не сможет, то тоже сбежит. Иначе отдаст кусок Эльзе. Этот цикл продолжается, пока возможно, или пока одна из коров не получит кусок с величиной вкусности равной \(0\), в этом случае процесс заканчивается и обе коровы счастливы.

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

Для каждого из \(N\) кусков Беси может выбрать его как начальный подарок Эльзе. Определите минимальное количество кусков, которые могут быть подарены так, чтобы обе коровы оказались счастливы.

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

Первая строка содержит два целых числа \(N\) и \(D\).

Следующие \(2N\) строк содержат по два целых числа, разделённых пробелом, соответственно обозначающие вкусность данного куска по мнению Беси и по мнению Эльзы.

Первые \(N\) строк о кусках Беси, а оставшиеся \(N\) строк о кусках Эльзы.

Гарантируется, что все величины вкусности в интервале \([0,10^9]\).

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

На выводе должно быть \(N\) строк. Строка \(i\) должна содержать одно целое число: минимальное количество кусков, которое может быть подарено при счастливом исходе, если Беси начнёт с куска \(i\). Если счастливый исход при начале с куска \(i\) невозможен, то строка \(i\) должна содержать \(-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).
Обход в ширину
—Войти и решать
Island Travels#89883

Фермер Джон отвез саоих коров на океан. Коровы живут на N (1<=N<=15) островах, которые расположены на решетке R x C (1 <= R, C <= 50). Остров - это максимальная связная группа квадратов на решетке, помеченная символами 'X', где два 'X' связны, только если они имеют общую сторону. Квадраты имеющие общий угол, не обязательно связны.
Беси опоздала, она прилетела с ФД на вертолете. Она может приземлиться на любом острове. Она хочет посетить все N островов хотя бы один раз.
Вокруг островов находится мелководье (обозначено буквой 'S'). Беси может плыть по нему в четырех направлениях (север, юг, запад, восток) для того, чтобы путешествовать между островами. Она также может путешествовать между островом и мелководьем и наоборот.
Определите минимальное расстояние, которое Беси должна проплыть, чтобы посетить все острова (гарантируется, что это возможно). Расстояние, которое проплывет Беси, равно количеству различных раз, когда Беси посетит клеточку 'S'.
PROBLEM NAME: island
Формат входных данных
* Строка 1: Два разделенных пробелом целых числа: R и C.
* Строки 2..R+1: Строка i+1 содержит C символов, определяющих i-ую строку решетки. Глубокая вода обозначена '.', острова 'X', мелководье 'S'.
Формат выходных данных
* Строка 1: Одно целое число, представляющее минимальное расстояние, которое должна проплыть Беси, чтобы посетить все острова.
Примечание
Бэси может проплыть от левого верхнего сотрова к среднему, проплыв 1 клеточку, а затем от среднего острова к правому нижнему, проплыв 2 клеточки - всего 3.
графыМинимальный каркасОбход в ширину
—Войти и решать
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. Вместе они представляют не менее половины фермы.

Бинарный поиск по ответуОбход в ширинуПоиск компонент связности
—Войти и решать
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 позиции на восток, то границы трех фигур разъединятся.

графыЗадачи на моделированиеОбход в ширину
—Войти и решать
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 стог.

Обход в ширину
—Войти и решать
Поделиться
Класснуть