#3376

Кратчайший путь

Темы: [Обход в ширину]

Дан ориентированный взвешенный граф.
Найдите кратчайшее расстояние от одной заданной вершины до другой.

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

В первой строке входного файла два числа: N и M (1 ≤ N ≤ 100, 1 ≤ M ≤ 10000), где N - количество вершин графа, а M - количество ребер.
В следующей строке заданы числа S и F - начальная и конечная вершины.

Далее следует \(M\) троек чисел A_i, B_i, T_i (1 ≤ T_i ≤ 10) - номера вершин соединенных ребром и вес данного ребра.

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

Вывести искомое расстояние или -1, если пути между указанными вершинами не существует.

Примеры

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

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

#3377

Лесопосадки

Темы: [Обход в глубину]

Дан неориентированный невзвешенный граф. Необходимо определить, является ли он деревом.

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

В первой строке входного файла содержится одно натуральное число N (N ≤ 100) -- количество вершин в графе. Далее в N строках по N чисел -- матрица смежности графа: в i-ой строке на j-ом месте стоит 1, если вершины i и j соединены ребром, и 0, если ребра между ними нет. На главной диагонали матрицы стоят нули. Матрица симметрична относительно главной диагонали.

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

Вывести YES, если граф является деревом, NO иначе.

Примеры

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

2
0 1
1 0

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

YES

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

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

NO

#3378

Кроты и норки

Темы: [Вещественные числа]

Эффективные и точные вычисления вещественных чисел.

\(N\) кротов жили в домике Ненокку. У каждого крота была своя собственная норка. Но студент Токийского Государственного Университета посадил в саду суффиксное дерево, и почти все кроты перебрались поближе к природе. Но нашлись три мутировавших крота, которые сочли регрессивную обстановку в домике подходящей для их коварных планов. Их зовут Дима, Миша и Миша. И Ненокку не может различить двух Миш. Иногда кроты выглядывают из норок, чтобы посмотреть вокруг. Но только один крот Дима, самый странный из них, не слеп. И когда они высовываются из норки, Дима смотрит на Миш. Но, так как его зрение оставляет желать лучшего, он не видит их не под любым углом. Угол между Мишами (назовем его \(A\)) должен быть острым и целая часть числа \(90/A\) (\(A\) в градусах) должна быть равна третьему знаку в десятичной записи числа \(cos(A)\).

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

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

Первая строка содержит число \(N\) (\(3 \leq N \leq 400\)). В следующих \(N\) строках задаются координаты норок: каждая строка содержит два числа, разделенных пробелом. Координаты не превосходят \(1000\) по абсолютной величине. Никакие две норки не совпадают. Все числа во входном файле целые.

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

Выведите одно целое число – количество способов.

Примеры

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

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

#3379

Служба поддержки

Темы: [Динамическое программирование: два параметра]

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

Кассы занумерованы от \(1\) до \(L\). При поступлении нового вызова, один из инженеров едет к этой кассе из своего текущего положения (или остается там же, если он к тому моменту был в этой кассе). В одной кассе может находиться только один инженер. Вызовы должны обслуживаться в том порядке, в котором они поступают. В каждый момент времени перемещаться может только один инженер. Перемещаться инженеры могут только при вызове и только к той кассе, в которую их вызывают в данный момент. Изначально инженеры находятся в кассах 1, 2 и 3 соответственно. Перемещение инженера из кассы \(p\) в кассу \(q\) стоит \(C(p, q)\) рублей. При этом стоимость проезда из \(p\) в \(q\) и обратно может различаться. Также инженер может совершенно бесплатно оставаться в той же кассе (т.е. \(C(p, p) = 0\)). Цель компании – снизить расходы на обслуживание вызовов. Кроме этого требуется по известной последовательности вызовов определить для каждого из них, каким инженером этот вызов будет обслужен.

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

В первой строке содержаться два числа \(L\) и \(N\) (\(3 \leq L \leq 200\), \(1 \leq N \leq 1000\)) – количество касс и вызовов соответственно. В каждой из следующих \(L\) строк записано по \(L\) целых неотрицательных чисел. Число, стоящее в строке \(p+1\) входного файла и столбце \(q\), задает \(C(p, q)\). Стоимость проезда между двумя кассами – целое неотрицательное число, не превышающее 2000. После этого задано \(N\) чисел – номера касс в той последовательности, в которой происходили вызовы.

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

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

Примеры

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

5 9
0 1 1 1 1
1 0 2 3 2
1 1 0 4 1
2 1 5 0 1
4 2 3 4 0
4 2 4 1 5 4 3 2 1

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

5
1 2 1 2 2 1 3 1 3

#3380

Лифт

Темы: [Жадный алгоритм] [Бинарный поиск по ответу]

Высокое здание, состоящее из \(N\) этажей, оснащено только одним лифтом. Парковка находится ниже фундамента здания, что соответствует одному этажу ниже первого. Этажи пронумерованы от \(1\) до \(N\) снизу вверх. Про каждый этаж известно количество человек, желающих спуститься на лифте на парковку. Пусть для i-го этажа эта величина равна \(A_i\). Известно, что лифт не может перевозить более \(C\) человек единовременно, а также то, что на преодоление расстояния в один этаж (не важно вверх или вниз) ему требуется \(P\) секунд. Какое наибольшее количество человек лифт может перевезти на парковку за \(T\) секунд, если изначально он находится на уровне парковки?

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

В первой строке входного файла содержатся целые числа \(N\), \(C\), \(P\), \(T\) (\(1 \leq N \leq 100\), \(1 \leq C \leq 10^9\), \(1 \leq P \leq 10^9\), \(1 \leq T \leq 10^9\)). Вторая строка содержит последовательность \(N\) целых чисел \(A_1\), \(A_2\), ..., \(A_N\) (\(0 \leq A_i \leq 10^9\)). Сумма всех значений последовательности не превосходит \(10^9\).

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

Выведите наибольшее количество человек, которое лифт успеет перевезти на парковку.

Примеры

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

4 5 2 15
0 1 2 3

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

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

4 5 2 18
0 1 2 3

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

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

3 2 1 9
1 1 1

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