Роботы начинают все чаще использоваться в домашнем хозяйстве. Один программист решил сделать робота для своих хозяйственных нужд. Как известно, многие программисты потребляют напиток "Живчик", от которого на столе остаются разбросанные пустые бутылки. Поэтому он решил запрограммировать робота собирать пустые бутылки со стола.
Стол имеет форму прямоугольника длиной 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
Андрей Сергеевич — учитель математики в начальной школе. Вчера на уроке он записал на доске выражение вида
a1 ? a2 ? ... ? aN - 1 ? aN = S
и попросил детей заменить вопросительные знаки на знаки сложения и умножения так, чтобы получилось верное равенство. Разумеется, дети быстро справились с заданием. Особенно понравилось Андрею Сергеевичу то, что мальчик Петя нашел сразу два варианта расстановки знаков. Тогда он попросил класс посчитать, сколько всего существует вариантов правильной расстановки знаков. Напишите программу, которая решает данную задачу.
В первой строке содержится число N (1 ≤ N ≤ 30) — количество чисел в левой части равенства, записанного на доске и число S, записанное в правой части равенства (1 ≤ S ≤ 106). В следующей строке даны N целых чисел в том порядке, в каком они были выписаны на доске. Все числа неотрицательные и не превышают 106.
Выведете на экран одно число –— количество различных вариантов расстановки знаков между числами, приводящих к правильному результату в записанном на доске выражении.
2 4 2 2
2
2 46 4 6
0
4 8 2 2 2 2
5
Робот Бендер решил открыть аттракцион «Кручу-Верчу» с целью своего обогащения. Аттракцион состоит в следующем: Бендер прячет шарик под одним из \(k\) одинаковых стаканчиков, расположенных на позициях от 1 до \(k\), затем \(n\) раз быстро меняет местами какие-то пары стаканчиков, после чего предлагает отгадать под каким из стаканчиков сейчас шарик.
Бендер — робот, поэтому действует он по определенной программе. Бендер строит последовательность целых чисел \(x_i\), при этом \(x_1 = c\), а \(x_i = a \cdot x_{i-1} + b\) для \(i > 1\).
На \(i\)-ом шаге Бендер меняет местами стаканчики на позициях с номерами \((x_i \bmod k) + 1\) и \(\left( (x_i + 1) \bmod k \right) + 1\).
В начале робот прячет шарик под стаканчик на позиции с номером \(r\). Бендер хочет, чтобы после \(n\) обменов шарик оказался под стаканчиком на позиции с номером \(l\).
Найдите такие \(a\), \(b\) и \(c\), чтобы стаканчик с шариком переместился с \(r\)-й позиции на \(l\)-ю.
В единственной строке входного файла четыре целых числа \(n\), \(k\), \(r\) и \(l\) (\(1 \le n \le 10^5\); \(2 \le k \le 10\); \(1 \le r, l \le k\)).
Если таких чисел не существует, выведите в выходной
файл единственное слово «Impossible».
Иначе выведите три целых неотрицательных числа \(a\), \(b\) и \(c\).
Числа не должны превосходить \(1000\).