Темы --> Информатика --> Алгоритмы
    Задачи на моделирование(78 задач)
    Арифметические алгоритмы(240 задач)
    Алгоритмы поиска(155 задач)
    Алгоритмы сортировки(194 задач)
    Динамическое программирование(355 задач)
    Алгоритмы на графах(319 задач)
    Перебор(154 задач)
    Игры и выигрышные стратегии(33 задач)
    Вычислительная геометрия(216 задач)
    Эвристические методы(30 задач)
    Алгоритмы на строках(45 задач)
    Пересечение множеств(10 задач)
    Жадный алгоритм(71 задач)
    Теория расписаний(5 задач)
    Обработка текста(31 задач)
    Дата и время(14 задач)
---> 1657 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 201 202 203 204 205 206 207 >> Отображать по:
#2912
ACM
  

Андрей популярный писатель-фантаст, он проводит мастер-классы для своих читателей. Наиболее популярным из них является Alien Communication Masterclass (ACM), на котором он учит как поступать в случае встречи с пришельцем или нахождении инопланетного артефакта.

Одна из лекций посвящена извлечению информации из инопланетных записей. Исследования Андрея базируется на математических формулах пришельцев, которые могут дать некоторые знания об организмах пришельцев (например, мы используем десятичную систему счисления потому что у нас 10 пальцев на верхних конечностях).

Предположим для простоты, что пришельцы используют те же самые цифры, что и мы и таким же образом трактуют сложение, вычитание, умножение, скобки и равенство.

Для своей лекции Андрей хочет найти пример равенства, которое выполняется в системах счисления с основаниями a1, a2, .., aN, но не выполняется в системах счисления с основаниями b1, b2, …, bM. Найдите для него пример такой формулы.

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

Первая строка входного файла содержит два целых числа N и M (1 ≤ N, M ≤ 8).

Вторая строка содержит N чисел a1, a2, .., aN

Третья строка содержит M чисел b1, b2, …, bM

Все числа ai и bi различны и лежат в пределах от 2 до 10.

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

Вывод должен представлять собой корректное математическое равенство, которое выполняется в системах счисления с основаниями a1, a2, .., aN и не выполняется в системах с основаниями b1, b2, …, bM.

Равенство может содержать цифры от 0 до 9, знак плюс +, минус и унарный минус –, знак умножения *, скобки ( и ) и знак равенства =. Знак равенства должен быть ровно один.

Все пробельные символы будут проигнорированы при проверке. Количество непробельных символов не должно превышать 10000.

Примеры тестов

Входные данные
1 2
2
3 9
Выходные данные
(10 - 1) * (10 - 1) + 1 = 10
Входные данные
2 2
9 10
2 3
Выходные данные
2 + 2 = 4
#2913
Рамки
  
Техническая задача. Сложность чуть выше средней.

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

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

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

На первом рисунке указаны (1) неправильные рамки, (2) правильные рамки, (3) пересечение рамок.

Площадь рамки вычисляется как W∙H – w∙h, где W, H – размеры внешнего прямоугольника, а w, h - размеры внутреннего (0 < w < W; 0 < h < H).

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

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

Каждая рамка описывается с помощью четырех точек — двух противоположных углов внешнего прямоугольника и двух противоположных углов внутреннего прямоугольника. Точки описываются своими координатами x и y, которые являются целыми числами и не превосходят 108 по модулю.

В первой строке содержится описание первой рамки, во второй — второй.

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

Первая строка выходного файла должна содержать целое число A – максимальная площадь области пересечения данных рамок достижимая с помощью переноса.

Вторая строка должна содержать пару целых чисел x и y – координаты вектора переноса второй рамки который даст область пересечения A. Координаты не должны превосходить 1018 по абсолютному значению.

Примеры
Входные данные
2 2 5 6 3 3 4 5
0 0 10 10 2 2 3 3
Выходные данные
10
0 -4
#2914
Сусанин
  
Сложность выше среднего

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

Длина каждой дороги указана на карте Стефана. Поэтому Стефан знает минимальное расстояние от каждой деревни до Домнино, аналогично Константин знает минимальное расстояние до Домнино по своей карте. Иван Сусанин каждый раз выбирает дорогу для Стефана или тропу для Константина так, что минимальное расстояние между войском и Домнино по соответствующей карте все время строго убывает.

Помогите Ивану найти самый длинный путь в Домнино, удовлетворяющий этим условиям. Гарантируется, что Домнино достижимо из каждой деревни.

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

Первая строка входа содержит три целых числа N, S и T – количество деревень, номер начальной деревни и номер деревни Домнино (2 ≤ N ≤ 1000, 1 ≤ s, t ≤ N). Начальная точка не совпадает с Домнино.

Далее идут описание карты Стефана и карты Константина

Первая строка описания карты содержит число M – количество дорог или троп соответственно (1 ≤ M ≤ 100000). Каждая из следующих М строк содержит 3 целых числа a, b и l – описывающих дорогу/тропу между пунктами a и b с указанием длины l (1 ≤ a, b ≤ N; 1 ≤ l ≤ 106).

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

Выведите общую длину пути (вдоль дорог и троп), который Сусанин заставит пройти польскую армию. Если он может заставить армию ходить вечно, так и не достигая Домнино, то выведите -1.

Примеры
Входные данные
5 1 5
5
1 2 2
1 4 2
2 3 1
3 4 1
5 3 1
4
1 2 2
2 4 2
2 3 1
2 5 2
Выходные данные
-1
Входные данные
3 1 3
4
1 2 10
2 3 10
1 3 20
2 3 30
4
2 1 10
1 3 10
1 1 10
2 3 10
Выходные данные
20
#2915
Кухня
  
ограничение по времени на тест
4.0 second;
ограничение по памяти на тест
256 megabytes

Роботы начинают все чаще использоваться в домашнем хозяйстве. Один программист решил сделать робота для своих хозяйственных нужд. Как известно, многие программисты потребляют напиток "Живчик", от которого на столе остаются разбросанные пустые бутылки. Поэтому он решил запрограммировать робота собирать пустые бутылки со стола.

Стол имеет форму прямоугольника длиной l и шириной w. Робот стартует в точке xr, yr, а N бутылок расположены в точках xi, yi (для i от 1 до N).

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

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

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

Первая строка входного файла содержит два целых числа w и l. (2 ≤ w, l ≤ 1000). Вторая строка входных данных содержит N – число бутылок на столе (1 ≤ N ≤ 18). Каждая из следующих N строк содержит два целых числа xi, yi – координаты i-й бутылки на столе (0<xi<w; 0<yi<l). Никакие две бутылки не находятся в одной точке.

Последняя строка входного файла содержит 2 целых числа xr, yr – координаты начальной позиции робота (опять же не у края стола и не в точке с бутылкой).

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

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

Примеры
Входные данные
3 4
2
1 1
2 3
2 1
Выходные данные
5.60555127546399
#2916
Дровосек
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Ответ считается как функции Гранди поддеревьев (\(X_i + 1\))

Двое играют в следующую игру: имеется дерево с отмеченной вершиной (корнем). За ход игрок разрубает ветку (стирает ребро), причем из двух получившихся компонент связности остается только та, которая содержит корень, другая удаляется. Проигрывает тот, кто не может сделать ход. Определите, может ли выиграть первый игрок, и если да, то укажите любой из его выигрышных ходов.

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

В первой строке вводится 2 числа — количество вершин 1 < N ≤ 100000 и номер корня 1 ≤ R ≤ N. В следующих N – 1 строках идут пары чисел — описания ребер.

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

В первой строке выведите число 1 или 2 – номер победителя при правильной игре.

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

Примеры
Входные данные
2 1
1 2
Выходные данные
1
1
Входные данные
5 2
1 3
3 4
2 3
2 5
Выходные данные
2
Страница: << 201 202 203 204 205 206 207 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест