Страница: << 45 46 47 48 49 50 51 >> Отображать по:
#1316
Школы
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Во взвешенном графе необходимо найти два минимальных остовных дерева.

С целью подготовки к проведению олимпиады по информатике мэр решил обеспечить надежным электроснабжением все школы города. Для этого необходимо провести линию электропередач от альтернативного источника электроэнергии “Майбуття” к одной из школ города (к какой неважно), а также соединить линиямии электропередач некоторые школы между собой.

Считается, что школа имеет надежное электроснабжение, если она напрямую связана с источником “Майбуття”, либо с одной из тех школ, которые имеют надежное электроснабжение.

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

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

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

В первой строке входного файла находятся два натуральных числа, разделенных пробелом:N (3 ≤ N ≤ 100), количество школ в городе, и M – количество возможных соединений между ними. В каждой из последующих M строк находятся по три числа: Ai, Bi, Ci, разделенных пробелами, где Ci – стоимость прокладки линии электроснабжения (1 ≤ Ci ≤ 300) от школы Ai до школы Bi (i=1,2,…,N).

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

В единственной строке выходного файла должны содержаться два натуральных числа S1 и S2, разделенных пробелом – две наименьшие стоимости схем (S1 ≤ S2). S1=S2 тогда и только тогда, когда существует несколько схем надежного электроснабжения наименьшей стоимости.

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

Примеры
Входные данные
5 8
1 3 75
3 4 51
2 4 19
3 2 95
2 5 42
5 4 31
1 2 9
3 5 66
Выходные данные
110 121
#1317
Квадрат
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
8 megabytes
X1,Y1), (X2,Y2), (X3,Y3). Найти длину L стороны квадрата минимальной площади, в который можно поместить этот треугольник так, чтобы все вершины треугольника находились внутри квадрата либо на его сторонах.

Составьте программу, которая по координатам вершин треугольника находит длину L стороны квадрата минимальной площади, в который можно поместить этот треугольник. L достаточно найти с точностью 10-4.

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

Файл содержит в одной строке действительные числа X1 Y1 X2 Y2 X3 Y3, разделенные пробелами, – координаты вершин треугольника (-10000 X1, Y1, X2, Y2, X3, Y3 10000).

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

Файл должен содержать одно число - длину L стороны искомого квадрата.

Примеры
Входные данные
0.0 0.0 1.1 0.0 0.0 1.1
Выходные данные
1.100000000
#1318
Лабиринт
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
8 megabytes

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

Лабиринт имеет форму квадрата, который состоит из N на N квадратных клеток, внутри которого вдоль сторон клеток могут быть расположены стены.

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

Одним ходом считается перемещение путешественника в соседнюю по горизонтали или по вертикали клетку. Путешественник может K раз проходить сквозь стену и не может выходить за пределы лабиринта.

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

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

Входной текстовый файл в первой строке содержит числа N, K, P, Q (2≤N≤200, 0≤K≤250, 1≤P,Q≤N). Следующие N-1 строк содержат поN целых чисел — признаков наличия горизонтальных стен между клетками. Следующие N строк содержат N-1 целых чисел — признаков наличия вертикальных стен между клетками. 0 означает отсутствие стены, 1 – присутствие.

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

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

Рисунок к примеру тестов

Примеры
Входные данные
3 1 2 3
0 0 0
0 1 0
1 0
1 0
0 0
Выходные данные
3
#1319
Забавный конфуз
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Пусть A — массив, состоящий из N элементов A1,...,AN. Обозначим его максимальное и минимальное значение как max(A) и min(A>) соответственно. Вычислим сумму элементов S, S=A1+A2+…+AN. Заменим каждый элемент массива на разницу S и этого элемента: Ai:=S-Ai, 1 ≤ i ≤N. Такое преобразование массива A назовем операцией Confuse.

Напишите программу, которая по массиву B, полученному в результате K–кратного применения операции Confuse к некоторому массиву A, вычислит разность max(A)-min(A).

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

Первая строка входного файла содержит целые числа N и K, где N — количество элементов массива B (2 ≤ N ≤ 10000), а K — количество применений операции Confuse к начальному массиву A, 1 ≤ K ≤ 100. Вторая строка файла содержит N элементов массиваB. Элементы массива B — целые числа, принадлежащие диапазону от -2 000 000 000 до 2 000 000 000.

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

Единственная строка выходного файла должна содержать целое число, которое есть разностью max(A) и min(A).

Примеры
Входные данные
3 2
5 6 7
Выходные данные
2
#1320
Соревнование
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

В спортивном турнире принимает участие N человек, с номерами от 1 до N. Турнир проходит по круговой системе: каждый участник должен сыграть с каждым другим участником по одной партии, которая заканчивается победой одного из игроков. Считается, что по окончании турнира участник занимает место P, если:

  1. у него выиграли (P-1) участников, и ему проиграли все остальные;
  2. все участники, которые победили его, выиграли свои партии у всех участников, которые ему проиграли.

Для остальных участников итоговое место определить нельзя.

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

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

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

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

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

Примеры
Входные данные
6 6
3 4
4 5
1 2
4 1
1 6
5 3
Выходные данные
3
Страница: << 45 46 47 48 49 50 51 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест