Темы --> Информатика --> Алгоритмы --> Алгоритмы на графах --> Кратчайшие пути в графе --> Обход в ширину
    0-1 BFS(3 задач)
---> 62 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 5 6 7 8 9 10 11 >> Отображать по:
#1748
Задача из ЕГЭ
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Вася, решая задачи демо-версии ЕГЭ, дошел до задачи B5, которая звучит так.

«У исполнителя Калькулятор две команды:

· прибавь 3

· умножь на 4

Выполняя первую из них, Калькулятор прибавляет к числу на экране 3, а выполняя вторую, умножает его на 4.»

Далее в задаче требовалось получить из числа 3 число 57 не более, чем за 6 команд. Однако Вася заинтересовался, как можно для произвольных чисел \(a\) и \(b\) построить программу наименьшей длины получения числа \(b\) из числа \(a\).

Напишите программу, которая по заданным числам \(a\) и \(b\) вычислит наименьшее количество команд Калькулятора, которое нужно, чтобы получить из \(a\) число \(b\).

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

Вводятся два натуральных числа, не превышающих 1000 — \(a\) и \(b\).

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

Выведите наименьшее число команд, которое нужно, чтобы получить из \(a\) число \(b\). Если число \(b\) получить нельзя, выведите –1 (минус 1).

Примеры
Входные данные
3 57
Выходные данные
5
Входные данные
43 57
Выходные данные
-1
Входные данные
10 10
Выходные данные
0
#1764
Два коня
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
На шахматной доске находится два коня. Для них заданы начальные и конечные клетки. Требуется вывести минимальную последовательность ходов коней так, чтобы они не находились на одной и той же клетке.

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

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

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

Во входном файле записаны четыре клетки шахматной доски в следующем порядке: начальное положение белого коня, начальное положение черного коня, конечное положение белого коня, конечное положение черного коня. Клетка шахматной доски задается горизонталью (буква от «a» до «h») и вертикалью (цифра от 1 до 8), не разделенными пробелами. Описания клеток отделяются друг от друга одним пробелом.

Гарантируется, что исходно кони находятся на различных клетках, и в конце кони также должны оказаться на различных клетках.

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

Выведите в первой строке выходного файла количество необходимых ходов. Далее выведите последовательность ходов. Ход описывается следующим образом: буква, соответствующая цвету коня («W» для белого или «B» для черного) и клетка, на которую нужно пойти. Клетку выведите в таком же формате, как во входном файле.

Если искомой последовательности ходов не существует, выведите на первой строке выходного файла число -1.

Примеры
Входные данные
a1 a2 a1 a6
Выходные данные
2
B b4
B a6
#1786
Лабиринт
  

Открыв глаза, Принц Персии обнаружил, что находится на верхнем уровне подземного лабиринта Джаффара. Лабиринт состоит из \(h\) уровней, расположенных строго друг под другом. Каждый уровень представляет собой прямоугольную площадку, разбитую на \(m\) × \(n\) участков. На некоторых участках стоят колонны, поддерживающие потолок, на такие участки Принц заходить не может.

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

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

На одном из участков нижнего уровня Принца ждет Принцесса, отказавшаяся выйти замуж за злого Джаффара. Помогите Принцу найти Принцессу, потратив на это как можно меньше времени.

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

В первой строке входного файла содержатся натуральные числа \(h\), \(m\) и \(n\) – высота и горизонтальные размеры лабиринта (2 ≤ \(h\), \(m\), \(n\) ≤ 50). Далее во входном файле приведены \(h\) блоков, описывающих уровни лабиринта в порядке от верхнего к нижнему.

Каждый блок содержит \(m\) строк, по \(n\) символов в каждой: «.» (точка) обозначает свободный участок, «o» (строчная латинская буква «o») обозначает участок с колонной, «1» обозначает свободный участок, в котором оказался Принц в начале своего путешествия, «2» обозначает свободный участок, на котором томится Принцесса.

Символы «1» и «2» встречаются во входном файле ровно по одному разу: символ «1» – в описании самого верхнего уровня, а символ «2» – в описании самого нижнего.

Соседние блоки разделены одной пустой строкой.

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

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

Примеры
Входные данные
3 3 3
1..
oo.
...

ooo
..o
.oo

ooo
o..
o.2
Выходные данные
60
#1939
Эвакуация
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

Организации понадобилось составить план эвакуации персонала на случай экстренной ситуации. Для этого для каждого из бункеров необходимо узнать, сколько времени потребуется для того, чтобы добраться до ближайшего из выходов. Вам, как специалисту по таким задачам, поручено рассчитать необходимое время для каждого из бункеров по заданному описанию помещения Сверхсекретной организации. Для вашего же удобства бункеры занумерованы числами от 1 до \(N\).

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

Сначала вводятся два натуральных числа \(N\), \(K\) (\(1\) ≤ \(N\) ≤ 100000, \(1\) ≤ \(K\) ≤ \(N\)) — количество бункеров и количество выходов соответственно.

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

Потом идёт число \(M\) (1 ≤ \(M\) ≤ 100000) — количество туннелей. Далее вводятся M пар чисел – номера бункеров, соединенных туннелем. По каждому из туннелей можно двигаться в обе стороны. В организации не существует туннелей, ведущих из бункера в самого себя, зато может существовать более одного туннеля между парой бункеров.

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

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

Примеры
Входные данные
3
1
2 
3
1 2
3 1
2 3
Выходные данные
1 0 1
Входные данные
10
2
10 8 
9
6 7
7 5
5 8
8 1
1 10
10 3
3 4
4 9
9 2
Выходные данные
1 4 1 2 1 3 2 0 3 0
#1944
Заливка
  

Максимальное время работы на одном тесте:

2 секунды

Максимальный объем используемой памяти:

64 мегабайта

 

 

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

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

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

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

Формат входных данных

Вводятся два натуральных числа N, M (1 ≤ N ≤ 100, 1 ≤ M ≤ 100) — количество строк и столбцов у таблицы, соответствующей данному изображению. В следующих N строках содержатся по M символов. В i‑й строке и j-м столбце стоит 0, если соответствующая клетка белая, и 1, если чёрная.

Формат выходных данных

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

Пример

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

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

3 5

10101

01010

10101

3
Страница: << 5 6 7 8 9 10 11 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест