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

План эвакуации#97010

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

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

Первая строка входных данных содержит число $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 баллов.

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

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

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

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

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

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):

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

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

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

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

графы Обход в ширину

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

Switching on the Lights#90352

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

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

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

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

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

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

Авторы: 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

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

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

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

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

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

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

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

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

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

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

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

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

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 стог.

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

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

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’ нужно добавить, чтобы получить одно пятно.

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

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

Побег с космической станции#56223

Представьте, что вы состоите на службе во внешней разведке Межгалактического Альянса Республиканских Сил (МАРС). Одному из агентов разведки крупно не повезло, и он был захвачен на засекреченной космической базе. К счастью, внешней разведке МАРС удалось заполучить план этой базы. И вот теперь вам поручено разработать план побега.

База представляет собой прямоугольник размером NхM, со всех сторон окружённый стенами, и состоящий из квадратных отсеков единичной площади. База снабжена K выходами, до одного из которых агенту необходимо добраться. В некоторых отсеках базы находятся стены. Ваш агент может перемещаться из отсека в любой из четырех соседних с ним, если в том отсеке, куда он хочет переместиться, нет стены.

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

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

Входные данные
В первой строке входного файла записаны числа N и M (2≤N≤100, 2≤M≤100), задающие размеры базы: N — количество строк в плане базы, M — количество столбцов. Во второй строке записаны начальные координаты агента X_A,Y_A (1≤X_A≤N, 1≤Y_A≤M). Первая координата задает номер строки, вторая — номер столбца. Строки нумеруются сверху вниз, столбцы слева направо.

Далее следуют N строк по M чисел, задающих описание стен внутри базы: 1 соответствует стенке, 0 — её отсутствию.

Далее в отдельной строке записано число H (0≤H≤1000) — количество гипертуннелей. В последующих H строках идут описания гипертуннелей. Каждый гипертуннель задается 4 числами: X₁, Y₁, X₂, Y₂ (1≤X₁,X₂≤N; 1≤Y₁,Y₂≤M) — координатами входа и выхода гипертуннеля. Никакие два гипертуннеля не имеют общего входа.

После этого в отдельной строке следует число K (1≤K≤10) — количество выходов с базы. В последующих K строках идут описания выходов с базы. Каждый выход задается двумя координатами X и Y (1≤X≤N; 1≤Y≤M).

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

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

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

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

Левый лабиринт#55694

В спортзале размером NxM метров построили современный аттракцион под названием "Левый лабиринт". Для этого на полу спортзала с интервалом в 1 метр начертили линии, параллельные стенам спортзала. Таким образом, спортзал разбили на NxM клеток. Дальше некоторые из этих клеток покрасили в черный цвет.

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

Участнику запрещено ходить по черным клеткам.
Придя в какую-то клетку, участник может пойти либо прямо, либо налево, либо направо (если в соответствующем направлении клетка не покрашена в черный цвет): ходить назад, а также ходить по диагонали запрещается.
За все время пути участнику разрешается повернуть направо (то есть пойти из текущей клетки направо относительно того, откуда он пришел в данную клетку) не более K раз.
В начальной клетке участник может встать лицом в ту сторону, в какую ему захочется. С какой стороны участник прибежит в конечную клетку также не важно.

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

Входные данные
Во входном файле сначала записано число K — количество разрешенных поворотов направо (целое число из диапазона от 0 до 5), затем записаны числа N и M, задающие размеры спортзала — натуральные числа, не превышающие 20. Далее записано N строк по M чисел в каждой. Число 0 обозначает непокрашенную клетку, число 1 — покрашенную, число 2 — клетку, откуда стартует участник и число 3 — клетку, куда нужно добежать (клетки, помеченные 2 и 3 являются непокрашенными). В лабиринте всегда есть ровно одна начальная клетка и ровно одна клетка, в которую нужно попасть.

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

Алгоритм Дейкстры Динамическое программирование на таблицах Обход в ширину

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