Темы --> Информатика --> Алгоритмы
    Задачи на моделирование(78 задач)
    Арифметические алгоритмы(240 задач)
    Алгоритмы поиска(155 задач)
    Алгоритмы сортировки(194 задач)
    Динамическое программирование(355 задач)
    Алгоритмы на графах(319 задач)
    Перебор(154 задач)
    Игры и выигрышные стратегии(33 задач)
    Вычислительная геометрия(216 задач)
    Эвристические методы(30 задач)
    Алгоритмы на строках(45 задач)
    Пересечение множеств(10 задач)
    Жадный алгоритм(71 задач)
    Теория расписаний(5 задач)
    Обработка текста(31 задач)
    Дата и время(14 задач)
---> 1657 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 264 265 266 267 268 269 270 >> Отображать по:
#111554
Правила дорожного движения
  
Темы: [0-1 BFS]
ограничение по времени на тест
4.0 second;
ограничение по памяти на тест
256 megabytes

В столице одной небольшой страны очень сложная ситуация. Многокилометровые пробки буквально парализовали движение в городе, и власти на многих улицах ввели одностороннее движение, не анализируя, можно ли будет теперь проехать из любого места в городе в любое другое, не нарушая правила. Транспортная система столицы представляет собой N площадей, соединенных M полосами для движения, в том числе круговыми полосами, проходящими по площади. Каждая полоса предназначена для движения только в одну определенную сторону. При этом на магистралях есть полосы, направленные как в одну, так и в другую сторону. По круговой полосе можно двигаться только внутри площади и только против часовой стрелки.

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

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

Иннокентий еще не решил, откуда именно и в какой магазин он собирается ехать, поэтому ему необходимо ответить на несколько вопросов вида «Какой минимальный штраф надо заплатить, чтобы добраться из пункта A в пункт B?». Отвечая на потребности жителей столицы, известная поисковая система Индекс разрабатывает соответствующий сервис.

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

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

В первой строке входных данных содержатся два числа N и M — количество площадей и полос движения в городе соответственно (1 ≤ N ≤ 5000, 1 ≤ M ≤ 10 000). Далее содержатся описания полос, по которым движение разрешено. Каждая полоса описывается номерами двух площадей, которые она соединяет. Движение разрешено в направлении от первой из указанных площадей ко второй.

В следующей строке содержится одно число K — количество вопросов у Иннокентия (1 ≤ K ≤ 10 000, N·K ≤ 2·107). В следующих строках описываются вопросы, каждый вопрос описывается номерами двух площадей, между которыми требуется найти самый дешевый путь. Путь необходимо проложить от первой из указанных площадей ко второй.

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

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

Примечание

Тесты к этой задаче состоят из четырех групп.

  • Тест –1. Тест из условия, оценивается в ноль баллов.
  • Тесты 2–-10. В тестах этой группы N не превосходит 10, M не превосходит 20. Эта группа оценивается в 30 баллов.
  • Тесты 11-–20. В тестах этой группы N не превосходит 2000, M не превосходит 3000, K равно 1. Эта группа оценивается в 30 баллов.
  • Тесты 21–-47. В тестах этой группы дополнительные ограничения отсутствуют. Эта группа оценивается в 40 баллов. Решение будет тестироваться на тестах этой группы только в случае прохождения всех тестов из второй и третьей групп.

Баллы за каждую группу тестов ставятся только при прохождении всех тестов группы.

Примеры
Входные данные
5 5
2 1
2 4
3 2
4 3
5 4
3
5 1
1 5
2 3
Выходные данные
0
2
0
#111556
Расшифровка
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

Недавно на уроке во время контрольной Мария Ивановна перехватила записку Саше от Оли. Мария Ивановна очень хочет знать, что в записке, но, к сожалению, записка зашифрована. Мария Ивановна знает, что её ученики для шифровки заменяют каждую букву исходного сообщения на какую-то другую. Замена происходит таким образом, что одинаковые буквы всегда заменяются одной и той же буквой, а разные — разными.

Мария Ивановна подозревает, что записка — это ответы к контрольному тесту (ведь её длина случайно оказалась равной длине строки с правильными ответами). Однако она знает, что ответы Оли не обязательно полностью правильны. На каждый вопрос возможен один из K вариантов ответа. Естественно, Мария Ивановна знает правильные ответы.

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

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

В первой строке задана длина каждой из строк N (1 ≤ N ≤ 2 000 000) и K — количество возможных ответов на каждый вопрос (1 ≤ K ≤ 52). Ответы нумеруются в порядке abcde...xyzABCDE...XYZ. То есть, при K = 6 возможные ответы выглядят как abcdef, а при K = 30 "— abcde...xyzABCD.

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

В третьей строке заданы правильные ответы — строка той же длины, что и первая, состоящая из строчных и заглавных латинских букв.

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

В первой строке выведите единственное число — максимально возможное количество правильных ответов у Оли.

Во второй строке выведите расшифровку — строчку длины K, где по порядку для каждой буквы из шифра учеников указано, какому ответу она соответствует.

Если несколько расшифровок дают правильный ответ, выведите любую.

Примечание

Тесты к этой задаче состоят из четырех групп.

  • Тесты 1-–3. Тесты из условия, оцениваются в ноль баллов.
  • Тесты 4-–15. В тестах этой группы K = 2. Решение оценивается в 15 баллов.
  • Тесты 16–-40. В тестах этой группы K ≤ 9. Решение оценивается в 15 баллов.
  • Тесты 41-–75. В тестах этой группы K ≤ 26. Решение оценивается в 30 баллов.
  • Тесты 76–-115. Дополнительные ограничения отсутствуют. Решение будет тестироваться на тестах этой группы только в случае прохождения всех предыдущих групп. Группа оценивается в 40 баллов.

Баллы за каждую группу тестов ставятся только при прохождении всех тестов группы. Тестирование на очередной группе начинается только после полного прохождения предыдущей.

Примеры
Входные данные
10 2
aaabbbaaab
bbbbabbbbb
Выходные данные
7
ba
Входные данные
10 2
aaaaaaabbb
bbbbaaabbb
Выходные данные
6
ab
Входные данные
9 4
dacbdacbd
acbdacbda
Выходные данные
9
cdba
#111572
Военный полигон
  
Ограничение по времени, сек0.75
Ограничение по памяти, мегабайт256





Министерство обороны Флатландии планирует построить новый военный полигон. Полигон должен иметь форму круга.

Поскольку генералы в министерстве волнуются о секретности проводимых на полигоне испытаний, он должен быть надежно защищен. Флатландия защищена сверху несколькими специальными силовыми щитами, каждый из них имеет форму прямоугольника со сторонами, параллельными осям координат. Генералы хотят выбрать такое место для полигона, где он был бы полностью защищен хотя бы двумя конкретными силовыми щитами (недостаточно, чтобы каждая точка просто была защищена хотя бы двумя щитами, должно быть два щита, каждый из которых защищает полигон полностью).

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

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

Первая строка входного файла содержит число \(N\) — количество силовых щитов. Каждая из следующих N строк описывает силовой щит (\(1 \leq N \leq 200000\)). Описание представляет собой четверку координат: \(x_{min}\), \(y_{min}\), \(x_{max}\), \(y_{max}\). Все координаты целые и не превышают 100000 по абсолютной величине.

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

Выведите три вещественных числа — координаты центра полигона и его радиус. Все числа следует выводить ровно с одним знаком после десятичной точки.

Если построить полигон невозможно, выведите “Impossible” на первой строке выходного файла.

Примеры тестов
Входные данные
4
0 0 2 3
1 -1 4 1
1 1 4 4
2 0 5 5
Выходные данные
3.0 2.0 1.0
Входные данные
1
0 0 1 1
Выходные данные
Impossible
Входные данные
2 
0 0 3 3
0 0 3 3
Выходные данные
1.5 1.5 1.5
Решения, работающие при \(1 \leq N \leq 5 000\), будут набирать не менее 50 баллов
#111586
Факториальная система счисления
  

В факториальной системе счисления основаниями являются последовательность факториалов bk = k!, и каждое натуральное число x представляется в виде:

, где 0 ≤ dk ≤ k

Ваша задача определить по данному в факториальной системе счисления числу его остаток от деления на p.

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

В первой строке даны два натуральных числа n и p, где n - максимальный индекс такой, что dn ≠ 0 (1 ≤ n ≤ 200, 2 ≤ p ≤ 104). Во второй строке задана последовательность dn, ..., d1, корректно определяющая некоторое натуральное число x.

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

Выведите одно число — остаток от деления x на p.

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

Входные данные
5 6
1 3 3 2 1
Выходные данные
5

Примечание

В исходном примере x = 215

#111587
Фибоначчи
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Числа Фибоначчи - элементы числовой последовательности, в которой каждое последующее число равно сумме двух предыдущих чисел. Более формально, последовательность чисел Фибоначчи {Fn} задается линейным рекуррентным соотношением:

F1 = 1, F2 = 2, Fn = Fn - 1 + Fn - 2, n ≥ 2

Рассмотрим систему счисления с двумя цифрами 0 и 1, в которой, в отличие от двоичной системы весами являются не степени двойки 1,2,4,8,16,..., а числа Фибоначчи 1,2,3,5,8,13,.... В этой системе счисления каждое положительное целое число единственным образом представляется в виде строки нулей и единиц, которая начинается с 1 и в которой нет двух единиц, стоящих рядом.

Даны две строки, представляющие натуральные числа A и B. Найти строку, представляющую число A+B.

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

Даны две строки, представляющие A и B, состоящие из нулей и единиц. Длина каждой из строк не превышает 104.

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

Выведите строку, представляющую число A + B. Обратите внимание, что она должна начинаться с единицы.

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

Входные данные
10101
100
Выходные данные
100010

Примечание

Исходные строки '10101' и '100' представляют числа 8 + 3 + 1 = 12 и 3. Ответом является строка '100010', представляющая строку 13 + 2 = 15 = 12 + 3.

Страница: << 264 265 266 267 268 269 270 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест