Задача

В пустой прямоугольной комнате размерами $A \times B \times C$ (длина, ширина, высота) на пол упала уснувшая муха. Паук, находившийся на одной из стен, или на полу комнаты, начал двигаться к ней по кратчайшему пути.

На какое расстояние он при этом переместится?

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

В первой строке заданы размеры комнаты $A$, $B$, $C$. Во второй строке — координаты мухи $X_1$,$Y_1$ и паука $X_2$, $Y_2$, $Z_2$.

Все входные данные — целые числа, не превышающие $500$.

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

Единственное число — расстояние, на которое переместится паук, вычисленное с точностью до 2-х знаков после запятой.

Тесты

Входные данные	Выходные данные
$3$ $4$ $8$ $0$ $0$ $3$ $4$ $0$	$5.00$
$2$ $2$ $8$ $1$ $1$ $2$ $1$ $4$	$5.00$
$6$ $4$ $3$ $5$ $1$ $0$ $2$ $1$	$6.08$
$30$ $60$ $27$ $13$ $21$ $8$ $0$ $17$	$38.33$
$40$ $40$ $40$ $10$ $5$ $8$ $40$ $37$	$72.03$

Код программы

Решение задачи

Суть решения задачи заключается в переходе от трехмерного пространства комнаты к двумерному с помощью «развёртки» комнаты на координатную плоскость.

Переведя координаты паука в комнате в его новые координаты в двумерном пространстве, все, что нам остается сделать — вычислить кратчайшее расстояние между двумя точками на плоскости с помощью функции $distance$.
В простейшем случае, если паук находится на полу комнаты, т.е. его координата $Z2$ нулевая, координаты паука $X2$ и $Y2$ в точности описывают его положение в координатной плоскости развёртки, и преобразовывать их не требуется.
В противном случае отдельно рассматриваем варианты расположения паука на каждой из стен. В зависимости от того, на какой стене он находится, мы изменяем координаты в соответствии с развёрткой комнаты и находим расстояние от паука до мухи с помощью функции $distance$.
В случае местонахождения паука в каком-либо из углов комнаты, но не на полу, мы должны рассмотреть два варианта его положения в развёртке и найти минимальное из них.

Ссылки

Условие задачи на сайте e-olymp
Код решения задачи

Задача

Возвращаясь домой, после захватывающей игры в гостях у Винни Пуха, ослик Иа решил немного прогуляться. Поскольку во время прогулки он все время думал о своем приближавшемся дне рождения, то не заметил, как заблудился. Известно, что ослик во время прогулки всегда передвигается по определенному алгоритму: в начале прогулки он всегда начинает движение на северо-восток, делает при этом один шаг (перемещаясь при этом в точку [latex]\left \langle 1,1 \right \rangle[/latex]), потом меняет направление и двигается на юго-восток, далее на юго-запад, на северо-запад и так далее. При каждом изменении направления ослик всегда делает на [latex]n[/latex] шагов больше, чем было сделано до изменения направления.

Когда ослик все же решил возвратится домой, то обнаружил, что зашел глубоко в лес. Надвигалась ночь и Иа захотел поскорее попасть домой. Помогите узнать, удастся ли сегодня ослику попасть домой до заката солнца, если известно, что солнце зайдет через [latex]t[/latex] часов, а скорость передвижения ослика [latex]v[/latex] шагов в час (длина шага у ослика постоянна). Известно, что движение ослик начинал из точки с координатами [latex]\left \langle 0,0 \right \rangle[/latex], а его дом расположен в точке [latex]\left \langle x_{h},y_{h} \right \rangle[/latex], и направление движения он менял [latex]k[/latex] раз.

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

В первой строке задано четыре целых числа [latex]n[/latex], [latex]k[/latex], [latex]t[/latex], [latex]v[/latex] [latex](0\leq n,k,t,v\leq 100)[/latex] . Во второй строке размещено два целых числа [latex]x_{h}[/latex], [latex]y_{h}[/latex] – координаты домика ослика [latex](-10^5\leq x_{h}, y_{h}\leq 10^5)[/latex] .

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

Вывести Good night Ia, если ослик успеет дойти домой до заката солнца или Poor Ia в противоположном случае.

Тесты

Входные данные	Выходные данные
[latex]1[/latex] [latex]5[/latex] [latex]3[/latex] [latex]2[/latex]   [latex]5[/latex] [latex]7[/latex]	Good night Ia
[latex]5[/latex] [latex]2[/latex] [latex]3[/latex] [latex]9[/latex]   [latex]15[/latex] [latex]15[/latex]	Good night Ia
[latex]4[/latex] [latex]4[/latex] [latex]3[/latex] [latex]20[/latex]   [latex]105[/latex] [latex]-105[/latex]	Poor Ia
[latex]3[/latex] [latex]4[/latex] [latex]2[/latex] [latex]3[/latex]   [latex]40[/latex] [latex]-20[/latex]	Good night Ia
[latex]1[/latex] [latex]3[/latex] [latex]7[/latex] [latex]2[/latex]   [latex]-24[/latex] [latex]0[/latex]	Poor Ia
[latex]1[/latex] [latex]3[/latex] [latex]7[/latex] [latex]2[/latex]   [latex]-23[/latex] [latex]0[/latex]	Good night Ia

Первый вариант кода программы

Второй вариант кода программы

Решение задачи

Вариант 1

Разделим решение задачи на две части: поиск местоположения Иа после прогулки и расчет пути домой.
Имеем следующую формулу вычисления вектора нахождения Иа после прогулки:
[latex]\sum\limits_{i=0}^k f(i, n)[/latex], где [latex]n[/latex] — изменение количества шагов Иа в каждой итерации, [latex]k[/latex] — cколько раз он менял движение, и функции:

[latex]f(x,y) = \begin{cases} \left \langle1 + xy, 1 + xy\right \rangle & \textit{if } x\vdots 4 = 0 \\\\ \left \langle1 + xy, (-1) \cdot (1 + xy)\right \rangle & \textit{if } x\vdots 4 = 1 \\\\ \left \langle(-1) \cdot (1 + xy), (-1) \cdot (1 + xy)\right \rangle & \textit{if } x\vdots 4 = 2 \\\\ \left \langle(-1) \cdot (1 + xy), 1 + xy\right \rangle & \textit{if } x\vdots 4 = 3 \end{cases}[/latex]

То есть, результат функции [latex]f(x,y)[/latex] это вектор, на который передвинулся Иа в итерации номер [latex]x[/latex] с изменением шага [latex]y[/latex], а результат [latex]\sum\limits_{i=0}^k f(i, n)[/latex] — это вектор [latex]\left \langle a,b \right \rangle[/latex] местоположения Иа в конце прогулки. Теперь нужно посчитать расстояние между местоположением Иа и его домом. Считаем из вектора [latex]\left \langle a,b \right \rangle[/latex] и вектора [latex]\left \langle x_{h},y_{h} \right \rangle[/latex]:

$$\sqrt{(x_{h} — a)^2 + (y_{h} — b)^2}$$

И считаем максимальное расстояние, которое может пройти Иа до заката солнца. Тут нужно учесть то, что скорость в условии измеряется в шагах в час, а шаг это расстояние между [latex]\left \langle 0,0 \right \rangle[/latex] и [latex]\left \langle 1,1 \right \rangle[/latex], то есть — [latex]\sqrt{2}[/latex].

$$ \sqrt{2} tv$$

Итого, выводим Good night Ia, если [latex]2t^2v^2 \geq (x_{h} — a)^2 + (y_{h} — b)^2[/latex] и Poor Ia в противном случае.

Вариант 2

Если рассмотреть каждое направление спирали, как элемент арифметической прогрессии, то можно следующим образом получить алгоритм решения данной задачи с вычислительной сложностью [latex]O(1)[/latex]. Используем сумму арифметической прогрессии $S = \displaystyle\frac{a_1 + a_m}{2}$, где $a_m = 1+(m-1)d$

Для направления на северо-восток:
$$a_1 = 1, d = 4n \Rightarrow S_{1}=\frac{1 + 1 +4n(m_1-1)}{2}\Rightarrow S_{1} = m_1(1+2n(m_1-1)),$$
где $m_1 = \displaystyle\frac{k+1}{4} + 1,$ если$ (k+1)\vdots 4 >=1$ иначе, $m_1=\displaystyle\frac{k+1}{4}$

Для направления на юго-восток:
$$a_2 = 1+n, d = 4n \Rightarrow S_{2} = m_2(1+n+2n(m_2-1)),$$
где $m_2 = \displaystyle\frac{k+1}{4} + 1,$ если$ (k+1)\vdots 4 >=2$ иначе, $m_2=\displaystyle\frac{k+1}{4}$

Для направления на юго-запад:
$$a_3 = 1+2n, d = 4n \Rightarrow S_{3} = m_3(1+2n+2n(m_3-1)),$$
где $m_3 = \displaystyle\frac{k+1}{4} + 1,$ если$ (k+1)\vdots 4 >=3$ иначе, $m_3=\displaystyle\frac{k+1}{4}$

Для направления на северо-запад:
$$a_4 = 1+3n, d = 4n \Rightarrow S_{4} = m_4(1+3n+2n(m_4-1)),$$
где $m_4 = \displaystyle\frac{k+1}{4} + 1,$ если$ (k+1)\vdots 4 >=4$ иначе, $m_4=\displaystyle\frac{k+1}{4}$

Тогда, для вычисления координат [latex]\left \langle x,y \right \rangle[/latex] воспользуемся следующей формулами:
$$x = S_{1} + S_{2} — S_{3} — S_{4}$$
$$y = S_{1} — S_{2} — S_{3} + S_{4}$$
Последующие вычисления эквивалентны первому варианту решения.

Ссылки

Условие задачи на e-olymp
Код решения первого варианта на ideone.com
Код решения второго варианта на ideone.com