e-olymp 72. Дорога домой

Задача

Бедный Иа

Бедный Иа

Возвращаясь домой, после захватывающей игры в гостях у Винни Пуха, ослик Иа решил немного прогуляться. Поскольку во время прогулки он все время думал о своем приближавшемся дне рождения, то не заметил, как заблудился. Известно, что ослик во время прогулки всегда передвигается по определенному алгоритму: в начале прогулки он всегда начинает движение на северо-восток, делает при этом один шаг (перемещаясь при этом в точку [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

9 thoughts on “e-olymp 72. Дорога домой

  1. Да, запутанная задача.
    Какой-то Ia появился, хотя все знают, что ослика звали Eeyore.
    — Для возведения числа в квадрат следует его умножить на себя, а не использовать функцию возведения в действительную степень разложением в ряд Тейлора.
    — Зачем извлекать корень, когда можно возвести в квадрат левую часть? Вы же в курсе, что корень не всегда удается извлечь точно?
    — Константный сомножитель в математически формулах принято ставить в начале, а не в конце.
    — В последней формуле ошибка. Видимо, просто опечатка.
    — Отступы в программе нужно поправить.
    — И, самое главное, что тут делают циклы? В принципе, я могу засчитать это решение как задание по циклам. Но для этого нужно найти решение без циклов. Возможно Вам поможет если заметить, что каждый из размеров спирали увеличивается по арифметической прогрессии, про которую Вы все знаете ещё со школы?

  2. Хорошо, молодец! У Вас получилось добротное, подробное описание. Только исправьте от -105 до 105. Там степени.
    Давайте засчитаем задачу. Но, не могу не по ерничать.
    Сегодня исполняется ровно 6 месяцев как Вы начали работать над этой задачей! Полгода, бедный ослик Иа вынужден был где-то скитаться и не мог попасть домой. Он давно пропустил свой день рождения по Вашей вине!
    Если бы это была не программа, а новорожденный ребенок, то за полгода…

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

  3. Тут всего два условных оператора

    • Если в Вашем решении исправить опечатки, возникшие при копировании, то оно полностью совпадет со вторым вариантом кода в статье. Возможно я ошибаюсь. Исправьте, пожалуйста, опечатки в вашем комментарии, чтобы можно было понять.
      Для корректировки комментария имеется кнопка «Edit» в строке с Вашей фамилией и датой комментария.
      А про два условных оператора я не понял. Вроде и у автора и у вас он один. И тот логичнее заменить на тернарную операцию. Число ветвлений алгоритма у Вас 7. Три из них точно лишние. Должно быть не более чем 4, как и у автора.

          • Код из Вашего комментария все еще выдает массу синтаксических ошибок. Пожалуйста, отнеситесь серьезнее к своим замечаниям.
          • «Лишние переменные» не являются проблемой. Особенно если они помогают лучше объяснить алгоритм решения.
          • А вот «ненужные действия» действительно плохо. Вы видите у автора какие-то вычисления, которые в дальнейшем не используются? Пожалуйста, укажите какие именно.
  4. Поскольку Евгений Рудницкий так и не откорректировал свое решение, попробуем порассуждать без него. Наверное логично было бы сделать так:

    При всей лаконичности код не лишен недостатков — здесь 7 ветвлений. Можно сделать 4 как и у автора:

Добавить комментарий