Два коридора пересекаются под прямым углом. Ширина первого a метров, ширина второго b метров. Напишите программу, которая вычислит, какой максимальной длины лестницу можно перенести из одного коридора в другой. Можно считать, что лестница – отрезок ненулевой длины.
В единственной строке входных данных содержатся два целых числа a и b (1 ≤ a, b ≤ 1015).
Выведите единственное число – ответ на задачу. Ваш ответ будет считаться верным, если абсолютная или относительная погрешность не будет превосходить 10 - 9.
5 5
14.1421356237
Петр – следователь по особо важным делам в городе Брагинске. Совсем недавно из банка организованная банда преступников похитила огромную сумму денег. В местном полицейском участке Петру приказали отыскать воришек. Днём и ночью работал Пётр, но никак не удавалось напасть на след злоумышленников. Однако воскресным днём поступил странный звонок, в котором сообщалось, что некоторая группа людей катается на новеньком maserati по дорогам города, причём каждые несколько часов их замечают на одном и том же перекрёстке. Сомнений не осталось – только те самые преступники могли так дерзко рассекать по городу. Но Петру также известно, что в Брагинске гаишники настолько суровые, что даже похищенных денег не хватит, чтобы от них откупиться, поэтому преступники ездят по правилам (да-да!). Дороги в Брагинске односторонние и каждая из них соединяет ровно два перекрестка. Теперь перед Петром стоит задача попроще – ему нужно узнать, может ли он выбрать перекрёсток, так что, устроив засаду на нём, он гарантировано сможет поймать банду.
Первая строка входных данных содержит два целых числа n, m (1 ≤ n ≤ 1000, 1 ≤ m ≤ 105) – количество перекрестков и односторонних дорог Брагинска соответственно. В каждой из следующих m строк записано по два числа ui и vi – начало и конец i-той односторонней дороги (1 ≤ ui, vi ≤ n, ui ≠ vi). Гарантируется, что граф содержит хотя бы один цикл.
Выведите единственное число k – номер перекрестка, на котором Петр должен устроить засаду, если возможных ответов несколько – выведите любой. Если таких перекрестков в Брагинске нет, то выведите «–1» (без кавычек).
5 6
1 2
2 3
3 1
3 4
4 5
5 3
3
Преступники могли перемещаться по одному из трех маршрутов: (1 - 2 - 3 - 1), (3 - 4 - 5 - 3), (1 - 2 - 3 - 4 - 5 - 3 - 1), если Петр устроит засаду на перекрестке #3, то, в независимости от того, какой на самом деле был маршрут бандитов, он сможет их поймать.
Два друга Петя и Вася очень любят следующую игру: Петя записывает к себе в тетрадь какое-то количество слов (необязательно различных), а Васе необходимо попытаться запомнить за 1 минуту все слова, после чего написать их уже в своей тетрадке. Во время очередной игры оказалось, что Вася сумел воспроизвести все слова, кроме одного. Однако узнать, какое именно слово забыл Вася, им так и не удалось.
Вам даны все слова из тетрадей Васи и Пети, возможно в перемешанном порядке. Ваша задача – помочь ребятам найти потерявшееся слово.
Первая строка входных данных содержит одно целое нечетное число n (1 ≤ n ≤ 105) – общее количество слов. Слово – непустая строка из латинских строчных букв длиной не более 100 символов. В каждой из следующих n строк записано ровно по одному слову.
Выведите слово, которое забыл переписать в тетрадь Вася.
1
brzd
brzd
5
aa
aa
bb
bb
c
c
Обратите внимание, что в данной задаче стоит ограничение по памяти 6 МБ.
В нереально крутой real-time стратегии «Supreme Commander: Forged Alliance» есть два типа ресурсов: электричество и материя. Материю могут добывать только mass extractor'ы, которые, в свою очередь, можно проапгрейдить максимум до 3 уровня. Наш друг Вася хочет как можно скорее накопить K единиц материи, чтобы наконец достроить парагон. Известно, что mass extractor первого уровня добывает 3 единицы материи в секунду, второго уровня – 9, третьего – 27. Апгрейд с первого до второго уровня длится l2 секунд, со второго до третьего – l3 секунд. Во время апгрейда mass extractor не добывает материю. Изначально у Васи 0 материи и всего 1 mass extractor первого уровня.
Помогите вычислить Васе, за какое наименьшее время он сможет накопить необходимое количество материи.
В единственной строке входных данных содержится 3 числа: K, l2, l3 (1 ≤ K ≤ 109; 1 ≤ l2, l3 ≤ 1000) – количество материи, которое хочет накопить Вася, время апгрейда до 2 уровня и время апгрейда до 3 уровня соответственно.
Выведите единственное вещественное число с абсолютной или относительной погрешностью не более 10 - 6 – минимально возможное время в секундах, за которое Вася может накопить массу.
1 100 1000
0.3333333333
Дано поле размера n × m, в каждой клетке которого записано по одной заглавной латинской букве. Вам необходимо найти такой маршрут длины k, что выписывая буквы из клеток на пути, полученная строка будет лексикографически минимальна. Из одной клетки можно пойти в другую, если у них есть общая сторона. Ходить за пределы поля и из клетку в саму себя не разрешается. Стартовать можно в любой клетке.
В первой строке даны три числа: n, m (1 ≤ n, m ≤ 100, n·m ≥ 2) – размеры поля и k (1 ≤ k ≤ 105) – длина строки. В следующих n строках записано ровно по m символов в каждой – описание поля. В таблице встречаются только латинские заглавные буквы.
Выведите лексикографически минимальную строку, которую можете получить, соблюдая описанные в условии ограничения.
1 4 1
BRZD
B
Наверняка многие из вас помнят игру на мобильном телефоне, в которой нужно было, управляя мотоциклистом, проехать двумерный трек. Трек из себя представляет некоторую ломаную на плоскости. Так вот! Недавно британские ученые сделали сенсационное открытие: самыми сложными уровнями в этой игре были уровни, которые получили кодовое название «пила». «Пилу» можно описать пронумерованным набором чисел, для которого выполняются следующие условия:
Ваш давний друг Петя хочет создать новый мод данной игры, в котором будут лишь уровни по типу «пилы», состоящие из n звеньев ломанной. Но Петя коварен, он хочет сделать мод непроходимым (призовой 822сс не достанется никому :С ), поэтому решил добавить всевозможные конфигурации данного уровня, а именно всевозможные наборы чисел X, для которых выполняются все вышеописанные ограничения. Петя не силен в математике, поэтому попросил Вас посчитать, какое количество уровней будет в его моде.
Первая строка входных данных содержит единственное целое положительное число n (1 ≤ n ≤ 10000) – длину для каждого уровня Пети.
Выведите единственное число – ответ на задачу.
1
90
Один из примеров «пилы» изображен на рисунке:
Есть шахматная доска размера n × m и k королей. Король бьет все соседние по вертикали, горизонтали и диагонали клетки. Назовем расстановку фигур на доске правильной, если никакие два короля не бьют друг друга. Ваша задача – посчитать количество правильных расстановок k королей по модулю 109 + 9.
Единственная строка входных данных содержит три целых положительных числа n, m, k (1 ≤ n, m ≤ 70, 1 ≤ k ≤ n·m ≤ 70).
Выведите единственное число – количество правильных расстановок по модулю 109 + 9.
2 2 1
4
На плоскости даны n точек, заданные своими координатами. Требуется посчитать количество таких треугольников, у которых хотя бы одна сторона параллельна осям координат, а площадь лежит в отрезке от A / 2 до B / 2 включительно. Два треугольника считаются одинаковыми, если наборы номеров точек, которые задают вершины треугольников, совпадают как множества.
В первой строке входных данных содержится три целых числа n, A, B – количество точек (3 ≤ n ≤ 2000) и границы отрезка (1 ≤ A ≤ B ≤ 2·109). В каждой из последующих n строк содержится два целых числа xi и yi – координаты i-той точки (|xi|, |yi| ≤ 109). Координаты всех точек различны.
Выведите единственное целое число – ответ на задачу.
4 2 4
0 0
0 1
2 0
-1 0
2
Есть веревка, концы которой закреплены на плоскости в двух точках A(0, - 10) и B(0, 10). Эта веревка пересекает прямую y = 0 в n точках (но не касается!). Для каждой точки пересечения известен порядковый номер при движении по веревке от точки A к точке B. Если выписать все пересечения слева направо, то получится перестановка a1, a2, ..., an. Смотрите первый тестовый пример и рисунок для лучшего понимания.
В первой строке дано число n (1 ≤ n ≤ 105) – размер перестановки. Во второй строке даны n различных чисел ai (1 ≤ ai ≤ n) – перестановка, описанная в условии.
Если возможно уложить веревку требуемым образом выведите «Yes», иначе выведите «No».
11
9 10 11 8 1 2 5 6 7 4 3
Yes
5
1 3 2 4 5
No
Даны массив чисел a длины n и m запросов. Каждый запрос задаёт отрезок массива, на котором нужно посчитать сумму различных чисел, то есть сумму, в которую каждое число из отрезка входит ровно один раз.
В первой строке содержится целое число n: 1 ≤ n ≤ 105.
Во второй строке содержатся n целых чисел ai, разделённые пробелом: 0 ≤ ai ≤ 109.
В третьей строке содержится целое число m: 1 ≤ m ≤ 106.
Далее следуют m строк с запросами. В каждой строке содержится пара целых чисел Li и Ri, разделённые пробелом: 0 ≤ Li ≤ Ri < n – левая и правая границы отрезка, на котором нужно посчитать сумму различных чисел.
Выведите m строк, в i-й строке ответ на i-й запрос.
10
2 10 5 4 10 3 5 10 10 2
11
0 9
1 5
2 4
3 7
3 8
4 7
4 9
5 8
7 7
7 8
8 9
24
22
19
22
22
18
20
18
10
10
12
Соревнования по велогонкам проходят на кольцевом треке. В них участвуют n велосипедистов. В начале все они стартуют в одной точке. Для каждого велосипедиста известна его скорость, выраженная в количестве кругов, которые он проедет за час. Все скорости различны. Есть фляжка, которая изначально находится у самого быстрого гонщика. Каждый раз, когда в одной точке трека оказываются несколько велосипедистов, у одного из которых есть фляжка, фляжка передается самому быстрому из невладеющих ей велосипедистов в этой точке трека.
Определите, сколько кругов проедет фляжка в течение часа.
В первой строке дано целое положительное число n (1 ≤ n ≤ 100) – число велосипедистов. Во второй строке даны n чисел a1, a2, ..., an – скорости всех велосипедистов (1 ≤ ai ≤ 100).
Выведите одно число k – количество кругов, которое фляжка проедет за час, округленное до ближайшего целого числа.
2
2 1
2