Темы --> Информатика --> Алгоритмы
    Задачи на моделирование(78 задач)
    Арифметические алгоритмы(240 задач)
    Алгоритмы поиска(155 задач)
    Алгоритмы сортировки(194 задач)
    Динамическое программирование(355 задач)
    Алгоритмы на графах(319 задач)
    Перебор(154 задач)
    Игры и выигрышные стратегии(33 задач)
    Вычислительная геометрия(216 задач)
    Эвристические методы(30 задач)
    Алгоритмы на строках(45 задач)
    Пересечение множеств(10 задач)
    Жадный алгоритм(71 задач)
    Теория расписаний(5 задач)
    Обработка текста(31 задач)
    Дата и время(14 задач)
---> 1657 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 159 160 161 162 163 164 165 >> Отображать по:
#1712
L-фигуры
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Будем говорить, что два отрезка образуют L-фигуру, если угол между ними составляет 90˚ и конец одного отрезка совпадает с концом другого. На плоскости заданы N отрезков, занумерованных от 1 до N. Требуется определить количество различных L-фигур, образованных этими отрезками. L-фигуры считаются различными, если они содержат отрезки с разными номерами.

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

Первая строка содержит натуральное число N (1 ≤ N ≤ 5 000) – количество отрезков. Каждая из следующих N строк описывает один отрезок и содержит 4 целых числа x1, y1, x2, y2 (-10 000 ≤ x1, y1, x2, y2 ≤ 10 000), где (x1, y1) и (x2, y2) – концы отрезка. Конечные точки отрезка не совпадают.

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

Необходимо вывести одно число — количество различных пар отрезков, образующих L-фигуру.

Пояснение: В примере L-фигуры образованы парами отрезков: (1, 4), (1, 7), (2, 3), (4, 5), (5, 7). Обратите внимание, что отрезки 4 и 7 совпадают, но пары (1, 4) и (1, 7) считаются различными.
#1720
НОВП
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Входные данные

Во входном файле записаны две последовательности. Каждая последовательность описывается двумя строками следующим образом: в первой строке идет длина последовательности \(M\) (1 \(\le\) \(M\) \(\le\) 500), во второй идут \(M\) целых чисел \(a_i\) (\(−2^{31}\) \(\le\) \(a_i\) < \(2^{31}\)) – члены последовательности. Нужно найти возрастающую последовательность наибольшей длины, являющейся подпоследовательностью обоих данных последовательностей.

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

В первой строке выходного файла выведите \(N\) - длину наибольшей общей возрастающей подпоследовательности.

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

Примеры
Входные данные
5
1 4 2 5 -12
4
-12 1 2 4
Выходные данные
2
1 2
#1721
Кенгуренок Лео
  
#1722
Морской бой
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Совсем недавно появилась в продаже новая компьютерная игра «Морской бой—3». Вася купил себе эту игру и теперь играет в нее в свободное от занятий время. Особенно ему нравится в одной из миссий управлять самолетом. Изначально самолет находится на палубе неподвижного авианосца и готов в любой момент к взлету. Задача игрока в этой миссии состоит в уничтожении \(N\) кораблей противника. После уничтожения всех кораблей самолет должен вернуться обратно на авианосец.

Для простоты будем считать плоской поверхность моря, где располагается авианосец. Введем прямоугольную декартову систему координат и разместим авианосец в начале координат. Каждый из кораблей в начальный момент игры находится в некоторой точке (\(x\), \(y\)), и сразу после начала игры движется равномерно и прямолинейно так, что его вектор скорости равен (\(V_x\), \(V_y\)).

Конструктивные особенности самолета таковы, что он может двигаться с любой скоростью, не превосходящей \(U\). Для того, чтобы сбросить бомбу, которая была специально придумана для этой игры, самолету необходимо находиться непосредственно над кораблем. Корабли считаются точками, т.е. размером кораблей можно пренебречь. Считается также, что самолет может мгновенно взлететь с палубы авианосца, и время падения бомбы на цель равно нулю.

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

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

Первая строка входного файла содержит число \(N\), определяющее количество кораблей (1 \(\le\) \(N\) \(\le\) 9). Вторая строка входного файла содержит целое число \(U\) (1 \(\le\) \(U\) \(\le\) 10000), задающее скорость самолета в метрах в секунду. Последующие \(N\) строк описывают все корабли. Каждая строка содержит четыре целых числа \(x\), \(y\), \(V_x\), \(V_y\), не превосходящих 10000 по модулю и определяющих начальные координаты и скорость корабля, соответственно. Координаты кораблей заданы в метрах, скорости — в метрах в секунду.

Гарантируется, что самолет летит быстрее, чем плывет любой из кораблей.

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

В первой строке выходного файла выведите минимальное время, требуемое на выполнение миссии. Требуемая точность — не менее \(10^{−3}\).

Примеры
Входные данные
1
1000
10 10 0 0
Выходные данные
0.0282842712474619
#1726
Внеземные цивилизации
  
Страница: << 159 160 161 162 163 164 165 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест