Мальчик Вася застрял в лабиринте. Лабиринт представляет собою произвольный несамопересекающийся многоугольник с N вершинами и параллельными к осям координат сторонами. Так как у него вечером занятия по программированию, то Вася хочет выбраться как можно быстрее. Вася находится в точке (Xs, Ys) внутри лабиринта, а выход находится в точке (Xe, Ye). Для простоты решения представим Васю как квадрат со сторонами A условных единиц. Стороны квадрата всегда параллельны осям координат. Считается что Вася вышел из лабиринта, если его центр достигнет точки выхода. Найдите минимальное возможное время, за которое Вася сможет выйти из лабиринта. Скорость передвижения Васи равняется V у.е/c. Если Вася не может выбраться из лабиринта, вывести -1.
В первой строке заданы вещественные числа Xs и Ys (0 ≤ Xs, Ys ≤ 100). В следующей строке заданы вещественные числа Xe, Ye (0 ≤ Xe, Ye ≤ 100). В последующих двух строках заданы вещественные числа A и V (0.5 ≤ A, V ≤ 10) соответственно. Далее задан многоугольник: сначала дано целое число N (1 ≤ N ≤ 100), в последующих N строках находятся по два вещественных числа: координаты вершин многоугольника Xi и Yi (0 ≤ Xi, Yi ≤ 100). Гарантируется, что при умножении любого вещественного числа из входных данных на 2, получится целое число.
В единственной строке вывести ответ. Ответ считается верным, если его относительная погрешность не превышает 10 - 6.
Баллы за каждый тест начисляются независимо.
1.5 4.5
4.5 1.5
1
1
6
0 0
0 6
3 6
3 3
6 3
6 0
4.472135955
На планете Либерлун есть N станций связи, вокруг которых могут находиться ретрансляторы. Каждой станции в начальный момент времени талантливый астроном Айтал с Земли посылает сообщения в виде сигналов, которые доходят мгновенно, но с некоторыми потерями и отклонениями. Известно, что по p-ой части направленного станции сообщения попадает ретрансляторам (чем больше вокруг ретрансляторов, тем больше сигналов попадает к ним), и q-ая часть теряется. Ретранслятору требуется 3 часа, чтобы передать сообщение адресату. Ту часть сообщения, которая потерялась, компьютер Айтала повторно отправляет лишь через 10 часов. Считается, что станция получила читаемое сообщение, если полученная суммарная доля не меньше S.
Айтал просит вас подсчитать, сколько станций получат читаемое сообщение за H часов.
В первой строке записаны числа натуральное число N (1 ≤ N ≤ 106) и вещественные числа p, q (0 ≤ p, q ≤ 1) — количество станций и соответствующие доли. Во второй строке записаны N целых чисел a1, a2, ..., an, где ai означает количество соседних ретрансляторов у i-й станции (0 ≤ ai ≤ 106). В третьей строке записаны вещественные числа H, S (0 ≤ H ≤ 1000, 0 ≤ S ≤ 1).
Гарантируется, что для всех i выполнено условие p × ai + q ≤ 1.
Выведите единственное целое число — количество станций, которые получат читаемое сообщение за H часов.
Представленное на проверку решение сначала проходит тестирование на тестах из примеров, приведенных в условии задачи. Если на этих тестах решение участника выдает правильные ответы, то тогда это решение проверяется с использованием комплекта тестов для этой задачи (при этом баллы за каждый тест начисляются независимо). В противном случае решение участника считается неверным, и за него участнику не начисляются какие-либо баллы.
2 0.01 0.5
0 1
0 0.5
1
4 0.2 0.2
0 1 2 3
8 0.3
4
1. Сразу после отправления первая станция получает половину, а вторая — 0.49 объема сообщения. Следовательно, только первая станция получила читаемое сообщение.
2. По прошествии 3 часов 2, 3 и 4 станции получат сообщения от своих соседних ретрансляторов. Соответственно, у всех станций доли полученного сигнала будут равны 0.8.
В Cтране Дураков, как известно, в ходу два вида валюты – золотые и деревянные. При этом имеют хождение монеты номиналом a1, a2, …, aK деревянных, а также 1 золотой. По распоряжению Буратино – мудрого правителя Страны Дураков, денежная система устроена так, что любую сумму от 1 до M деревянных можно заплатить не более чем N монетами. Определите, какое наименьшее и наибольшее количество деревянных может быть в одном золотом, при условии, что золотой не дороже M деревянных? Если вариант только один, укажите его и как наименьший, и как наибольший.
Гарантируется, что указ Буратино выполняется, и золотой не дороже M деревянных.
В первой строке записаны три целых числа K, M, N (1 ≤ K ≤ 500, 1 ≤ M, N ≤ 2000). Во второй строке – K целых чисел a1, a2, ..., aK (1 ≤ ai ≤ 500).
Два целых числа через пробел — соответственно, минимально и максимально возможные числа деревянных в одном золотом.
Представленное на проверку решение сначала проходит тестирование на тестах из примеров, приведенных в условии задачи. Если на этих тестах решение участника выдает правильные ответы, то тогда это решение проверяется с использованием комплекта тестов для этой задачи (при этом баллы за каждый тест начисляются независимо). В противном случае решение участника считается неверным, и за него участнику не начисляются какие-либо баллы.
3 10 2
1 2 3
7 7
3 15 3
1 2 5
4 13
Молодой программист Гриша каждую субботу ходит за продуктами. В этот раз он решил минимизировать свои расходы.
В городе, где проживает Гриша, имеется N продовольственных магазинов. Для удобства он пронумеровал магазины от 1 до N. Между некоторыми магазинами ходят маршрутные такси. Стоимость проезда с i-го магазина в j-й составляет pij рублей. Всего продается K разных типов продуктов. В магазинах имеется определенное количество единиц того или иного продукта. Также Гриша знает, сколько стоит каждый продукт в каждом из магазинов. Цены на продукты в различных магазинах могут быть разными.
Гриша живет рядом с магазином с номером 1. Для того, чтобы добраться до этого магазина, он ничего не платит. Конечным магазином может быть любой из N магазинов. На обратную дорогу домой Гриша ничего не тратит.
Имея список покупок, определите наименьшую сумму денег, которую Гриша должен взять с собой.
В первой строке находится единственное целое число N (1 ≤ N ≤ 17) — количество магазинов.
Следующие N строк содержат матрицу N × N. Элемент матрицы pij (0 ≤ pij ≤ 2000) указывает стоимость проезда с i-го магазина в j-й. Если pij равно 0, то это значит, что нет прямого маршрута с i-го магазина в j-й. Матрица симметрична. Элементы на главной диагонали всегда равны нулю.
В следующей строке находится единственное целое число K (1 ≤ K ≤ 50) — количество различных продуктов.
Далее идут K целых чисел Qi (1 ≤ Qi ≤ 2000) — количество единиц каждого вида продукта, которое нужно купить.
Затем идут K блоков, которые указывают, в каких магазинах продаются товары, и по какой стоимости. Каждый i-й блок начинается со строки, где находится единственное целое M — количество магазинов, где продается i-й продукт. Далее в M строках имеется по три целых числа v p q (1 ≤ v ≤ n, 0 ≤ p ≤ 2000, 1 ≤ q ≤ 2000) — в магазине с номером v продается i-й продукт по цене p за штуку, и в этом магазине имеется q товаров этого типа.
В единственной строке выведите наименьшую сумму денег, которую Гриша должен взять с собой. Если нет возможности купить все товары, то надо вывести одно число - 1.
Представленное на проверку решение сначала проходит тестирование на тесте из примера, приведенного в условии задачи. Если на этом тесте решение участника выдает правильный ответ, то тогда это решение проверяется с использованием комплекта тестов для этой задачи (при этом баллы за каждый тест начисляются независимо). В противном случае решение участника считается неверным, и за него участнику не начисляются какие-либо баллы.
5
0 1 3 0 2
1 0 5 0 5
3 5 0 7 2
0 0 7 0 2
2 5 2 2 0
3
3 5 5
3
1 3 2
3 2 1
5 4 3
3
2 4 3
3 5 4
5 2 1
4
1 9 1
2 8 2
3 7 3
4 6 1
70