Темы --> Информатика
    Язык программирования(952 задач)
    Алгоритмы(1657 задач)
    Структуры данных(279 задач)
    Интерактивные задачи(17 задач)
    Другое(54 задач)
---> 2656 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 193 194 195 196 197 198 199 >> Отображать по:
#1333
Долой списывание!
  

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

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

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

В первой строке находятся два числа \(N\) и \(M\) - количество студентов и количество пар студентов, обменивающихся записками (\(1 \le N \le 100\), \(0 \le M \le \frac{N \cdot (N-1)}{2}\)). Далее в \(M\) строках расположены описания пар студентов: два числа, соответствующие номерам студентов, обменивающихся записками (нумерация студентов идёт с 1). Каждая пара студентов перечислена не более одного раза.

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

Необходимо вывести ответ на задачу профессора Флойда. Если возможно разделить студентов на две группы - выведите YES; иначе выведите NO.

Примеры
Входные данные
3 2
1 2
2 3
Выходные данные
YES
Входные данные
3 3
1 2
2 3
1 3
Выходные данные
NO
#1334
Два профессора
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

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

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

В первой строке находятся два числа \(N\) и \(M\) - количество зданий и количество дорог, соединяющих здания (\(1 \le N \le 100, 0 \le M \le \frac{N \cdot (N-1)}{2}\)). Далее в \(M\) строках расположены описания дорог: 3 целых числа \(s_i\), \(e_i\), \(l_i\) - здания, в которых начинается и заканчивается дорога и длина дороги соответственно (\(1 \le s_i, e_i \le N, 0 \le l_i \le 100\), дороги двунаправленные).

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

Необходимо вывести одно число - искомое расстояние.

Примеры
Входные данные
3 2
1 2 1
2 3 2
Выходные данные
3
Входные данные
3 0
Выходные данные
0
#1335
Столовая
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

Помогите найти такое здание!

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

В первой строке находятся два числе \(N\) и \(M\) - количество зданий и количество дорог, соединяющих здания (\(1 \le N \le 100, 0 \le M \le \frac{N \cdot (N-1)}{2}\)). Далее в \(M\) строках расположены описания дорог: 3 целых числа \(s_i\), \(e_i\), \(l_i\) - здания, в которых начинается и заканчивается дорога и длина дороги соответственно (\(1 \le s_i, e_i \le N, 0 \le l_i \le 100\), дороги двунаправленные).

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

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

Примеры
Входные данные
3 2
1 2 1
2 3 2
Выходные данные
2
Входные данные
3 1
1 2 10
Выходные данные
1
#1336
Опасный маршрут
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Профессор Флойд живёт в очень опасном районе города. Ежедневно бандиты грабят на улицах прохожих. Читая криминальную хронику, профессор Флойд вычислил вероятность быть ограбленным при проходе по каждой улице города.

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

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

В первой строке находятся два числа \(N\) и \(M\) - количество зданий и количество улиц, соединяющих здания (\(1 \le N \le 100, 1 \le M \le \frac{N \cdot (N-1)}{2}\)). В следующей строке находятся числа \(S\) и \(E\) -- номер дома, в котором живёт профессор и номер дома, в котором находится университет соответственно. Далее в \(M\) строках расположены описания дорог: 3 целых числа \(s_i, e_i, p_i\) - здания, в которых начинается и заканчивается дорога и вероятность в процентах быть ограбленным, пройдя по дороге соответственно (\(1 \le s_i, e_i \le N, 0 \le p_i \le 100\), дороги двунаправленные). Гарантируется, что существует хотя бы один путь от дома профессора до университета.

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

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

Примеры
Входные данные
3 3
1 3
1 2 20
1 3 50
2 3 20
Выходные данные
0.36
#1337
Компьютерная сеть
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

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

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

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

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

1.Компьютеры размещаются на плоскости в точках с целочисленными координатами.

2.Координаты компьютеров x и y лежат в диапазоне 0 ≤ x, y ≤ 106.

3.Никакие два компьютера не располагаются в одной точке.

4.Кабели являются отрезками прямых.

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

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

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

В первой строке входного файла содержатся числа N и M — количество компьютеров и количество кабелей в схеме (1 ≤ N ≤ 100 000, 0 ≤ M ≤ 200 000). В последующих M строках содержатся пары чисел, разделенных пробелами. Каждая такая пара описывает один кабель, числа представляют собой номера соединенных компьютеров. Компьютеры пронумерованы от 1 до N. Никакая пара не встречается дважды, и никакой кабель не соединяет компьютер с самим собой.

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

Выходной файл должен содержать N строк. Строка с номером i должна содержать координаты i-го компьютера, разделенные пробелом. Сначала выводится координата x, затем y. Разрешается вывести любой вариант размещения компьютеров, при котором выполняются условия 1–5.

Примечания

Решения, корректно работающие при отсутствии циклов, будут оцениваться из 40 баллов.

Решения, корректно работающие при наличии только одного цикла, будут оцениваться из 60 баллов.

Пример входных и выходных данных

Ввод

 Вывод

13 14

11 12

11 13

1 3

3 5

5 8

8 9

8 6

6 3

4 6

4 2

6 10

10 11

10 7

7 4

1 0

3 0

1 1

3 1

0 2

2 2

4 2

1 3

1 4

3 3

3 4

2 5

4 5


Страница: << 193 194 195 196 197 198 199 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест