Темы --> Информатика --> Алгоритмы
    Задачи на моделирование(78 задач)
    Арифметические алгоритмы(240 задач)
    Алгоритмы поиска(155 задач)
    Алгоритмы сортировки(194 задач)
    Динамическое программирование(355 задач)
    Алгоритмы на графах(319 задач)
    Перебор(154 задач)
    Игры и выигрышные стратегии(33 задач)
    Вычислительная геометрия(216 задач)
    Эвристические методы(30 задач)
    Алгоритмы на строках(45 задач)
    Пересечение множеств(10 задач)
    Жадный алгоритм(71 задач)
    Теория расписаний(5 задач)
    Обработка текста(31 задач)
    Дата и время(14 задач)
---> 1657 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 223 224 225 226 227 228 229 >> Отображать по:
#3346
Две окружности (AB)
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Пересечь две окружности

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

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

В первой строке входного файла находится число \(K\) (\(1 \leq K \leq 10000\)) – количество пар окружностей. Каждая последующая пара строк описывает пару окружностей: в каждой строке записаны 3 целых числа \(x\), \(y\), \(r\) – координаты центра и радиус соответствующей окружности (\(-1000 \leq x,y \leq 1000\), \(0 < r \leq 1000\)).

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

Для каждой пары окружностей вы должны вывети одну из следующих фраз: “There are no points!!!” – если окружности не пересекаются. “There are only i of them....” – если окружности пересекаются ровно в \(i\) точках. В этом случае последующие \(i\) строк должны содержать координаты точек пересечения в формате \(x\) \(y\). Точки должны быть выведены в лексикографическом порядке (сначала с меньшей координатой \(x\), а при равных \(x\) – сначала с меньшей \(y\)). Координаты следует выводить с 6 знаками после запятой. “I can't count them - too many points :(” – если точек пересечения бесконечно много. Все фразы должны быть выведены без кавычек. Вывод для каждой следующей пары окружностей должен быть отделен от предыдущего одной пустой строкой.

Примеры
Входные данные
2
0 0 2
4 0 2
0 0 1
1000 1000 1
Выходные данные
There are only 1 of them....
2.000000 0.000000

There are no points!!!
#3347
Кратчайший путь (AB)
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

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

Сеть дорог задана во входном файле следующим образом: первая строка содержит числа \(N\) и \(K\) (\(1 \leq N \leq 100000\), \(0 \leq K \leq 300000\)), где \(K\) – количество дорог. Каждая из следующих \(K\) строк содержит описание дороги с двусторонним движением – три целых числа \(a_i\), \(b_i\) и \(l_i\) (\(1 \leq a_i,b_i \leq N\), \(1 \leq l_i \leq 10^6\)). Это означает, что имеется дорога длины \(l_i\), которая ведет из города \(a_i\) в город \(b_i\). В последней строке находятся два числа \(А\) и \(В\) – номера городов, между которыми надо посчитать кратчайшее расстояние (\(1 \leq A, B \leq N\))

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

Вы должны вывести в выходной файл единственное число – расстояние между требуемыми городами. Если по дорогам от города \(А\) до города \(В\) доехать невозможно, выведите –1.

Примеры
Входные данные
6 4
1 2 7
2 4 8
4 5 1
4 3 100
3 1
Выходные данные
115
#3348
Сумма (AB)
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Рассматриваются все разбиения натурального числа \(N\) на сумму \(К\) неотрицательных слагаемых (\(1 \leq N \leq 32\), \(2 \leq K \leq 32\)). Суммы, отличающиеся только порядком слагаемых, считаем различными. Упорядочим все разбиения по убыванию первого слагаемого, а при равных первых слагаемых – по убыванию второго слагаемого, а при равных первых и вторых слагаемых – по убыванию третьего слагаемого и т. д. Пронумеруем их. Например, при \(N=4\), \(К=3\) имеем:

Номер1 слагаемое2 слагаемое3 слагаемое
1400
2310
3301
4220
5211
6202
7130
8121
9112
10103
11040
12031
13022
14013
15004
Напишите программу, которая находит разбиение по номеру либо номер по разбиению.

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

В первой строке входного файла записана последовательность чисел. Если первое число \(0\), то необходимо найти разбиение по номеру, а если \(1\), то номер по разбиению. В первом случае далее в файле записано количество слагаемых, сумма и номер разбиения. Во втором случае далее в файле записано количество слагаемых \(K\) и затем разбиение (\(K\) неотрицательных чисел, сумма которых \(N\)). Все числа разделены пробелами.

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

Выведите в выходной файл разбиение либо номер.

Примеры
Входные данные
0 3 4 9
Выходные данные
1 1 2
Входные данные
1 3 0 1 3
Выходные данные
14
#3349
Мины (AB)
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Миротворцы ООН в одной из горячих точек планеты обезвреживали минное поле следующим образом. Имея карту, на которой каждая мина задана своими декартовыми координатами, они, обратив внимание на то, что никакие 3 мины не лежат на одной прямой, протянули специальный шнур от мины к мине так, чтобы он образовал выпуклый многоугольник минимального периметра, при этом все остальные мины оказались внутри многоугольника. Обезвредив соединенные мины, они вновь протянули шнур по тому же принципу, и опять обезвредили соединенные шнуром мины. Так продолжалось до тех пор, пока очередной шнур оказалось невозможным протянуть, руководствуясь изложенными правилами. Сколько мин осталось обезвредить и сколько раз саперам приходилось протягивать шнур?

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

В первой строке входного файла записано целое число \(N\) (\(3 \leq N \leq 1000\)) – количество мин. Во второй строке записано \(2\times N\) целых чисел (\(N\) пар \(x_i\), \(y_i\)), описывающих координаты каждой мины (\(-32000 \leq x_i, y_i \leq 32000\)).

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

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

Примеры
Входные данные
9
0 0 0 8 6 8 6 0 1 1 1 7 5 7 5 1 3 2
Выходные данные
1 2
#3351
Конденсация графа (A)
  
ограничение по времени на тест
0.5 second;
ограничение по памяти на тест
64 megabytes

Вам задан связный ориентированный граф с \(N\) вершинами и \(M\) ребрами (\(1 \leq N \leq 20000\), \(1 \leq M \leq 200000\)). Найдите компоненты сильной связности заданного графа и топологически отсортируйте его конденсацию.

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

Граф задан во входном файле следующим образом: первая строка содержит числа \(N\) и \(M\). Каждая из следующих \(M\) строк содержит описание ребра – два целых числа из диапазона от 1 до \(N\) – номера начала и конца ребра.

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

На первой строке выведите число \(K\) – количество компонент сильной связности в заданном графе. На следующей строке выведите \(N\) чисел – для каждой вершины выведите номер компоненты сильной связности, которой принадлежит эта вершина. Компоненты сильной связности должны быть занумерованы таким образом, чтобы для любого ребра номер компоненты сильной связности его начала не превышал номера компоненты сильной связности его конца.

Примеры
Входные данные
10 14
4 9
7 8
2 5
1 4
9 2
10 6
6 5
8 3
5 9
4 3
8 7
5 1
2 1
6 10
Выходные данные
4
3 3 4 3 3 2 1 1 3 2
Страница: << 223 224 225 226 227 228 229 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест