Страница: << 33 34 35 36 37 38 39 >> Отображать по:
#2914
Сусанин
  
Сложность выше среднего

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

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

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

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

Первая строка входа содержит три целых числа N, S и T – количество деревень, номер начальной деревни и номер деревни Домнино (2 ≤ N ≤ 1000, 1 ≤ s, t ≤ N). Начальная точка не совпадает с Домнино.

Далее идут описание карты Стефана и карты Константина

Первая строка описания карты содержит число M – количество дорог или троп соответственно (1 ≤ M ≤ 100000). Каждая из следующих М строк содержит 3 целых числа a, b и l – описывающих дорогу/тропу между пунктами a и b с указанием длины l (1 ≤ a, b ≤ N; 1 ≤ l ≤ 106).

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

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

Примеры
Входные данные
5 1 5
5
1 2 2
1 4 2
2 3 1
3 4 1
5 3 1
4
1 2 2
2 4 2
2 3 1
2 5 2
Выходные данные
-1
Входные данные
3 1 3
4
1 2 10
2 3 10
1 3 20
2 3 30
4
2 1 10
1 3 10
1 1 10
2 3 10
Выходные данные
20
#2915
Кухня
  
ограничение по времени на тест
4.0 second;
ограничение по памяти на тест
256 megabytes

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

Стол имеет форму прямоугольника длиной l и шириной w. Робот стартует в точке xr, yr, а N бутылок расположены в точках xi, yi (для i от 1 до N).

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

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

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

Первая строка входного файла содержит два целых числа w и l. (2 ≤ w, l ≤ 1000). Вторая строка входных данных содержит N – число бутылок на столе (1 ≤ N ≤ 18). Каждая из следующих N строк содержит два целых числа xi, yi – координаты i-й бутылки на столе (0<xi<w; 0<yi<l). Никакие две бутылки не находятся в одной точке.

Последняя строка входного файла содержит 2 целых числа xr, yr – координаты начальной позиции робота (опять же не у края стола и не в точке с бутылкой).

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

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

Примеры
Входные данные
3 4
2
1 1
2 3
2 1
Выходные данные
5.60555127546399
#2920
Перекраска полоски
  

Дана полоска Nx1 клетку, каждая клетка которой раскрашена в один из M цветов. За один ход разрешается перекрасить непрерывную область одного цвета в любой другой цвет.

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

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

В первой строке находятся два числа N и M – ширина полоски и количество цветов соответственно. 1 ≤ N ≤ 100, 1 ≤ M ≤ 100. Во второй строке находятся N чисел, соответствующих цветам каждой из клеток полоски от 1 до N (сами цвета лежат в диапазоне от 1 до M, каждый цвет встречается хотя бы один раз).

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

Выведите одно число – минимальное число перекрашиваний, за которое можно получить полоску одного цвета.

Примеры
Входные данные
5 3
3 2 1 1 3
Выходные данные
2
#2962
Ход конем - 2
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Дана прямоугольная доска N × M (N строк и M столбцов). В левом верхнем углу находится шахматный конь, которого необходимо переместить в правый нижний угол доски. При этом конь может ходить только так, как показано на рисунке:

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

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

В первой строке входного файла находятся два натуральных числа N и M (1 ≤ N, M ≤ 15).  

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

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

Примеры
Входные данные
4 4
Выходные данные
2
Входные данные
7 15
Выходные данные
13309
#2963
Калькулятор
  
ограничение по времени на тест
3.0 second;
ограничение по памяти на тест
64 megabytes

Имеется калькулятор, который выполняет три операции:

  1. Прибавить к числу X единицу.
  2.  Умножить число X на 2.
  3. Умножить число X на 3.

Определите, какое наименьшее число операций необходимо для того, чтобы получить из числа 1 заданное число N.

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

Программа получает на вход одно число, не превосходящее 106.

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

Требуется вывести одно число: наименьшее количество искомых операций.

Примеры
Входные данные
1
Выходные данные
0
Входные данные
5
Выходные данные
3
Входные данные
32718
Выходные данные
17
Страница: << 33 34 35 36 37 38 39 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест