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

26/12/2017 by Павел Жуков

Задача

Бедный Иа

Возвращаясь домой, после захватывающей игры в гостях у Винни Пуха, ослик Иа решил немного прогуляться. Поскольку во время прогулки он все время думал о своем приближавшемся дне рождения, то не заметил, как заблудился. Известно, что ослик во время прогулки всегда передвигается по определенному алгоритму: в начале прогулки он всегда начинает движение на северо-восток, делает при этом один шаг (перемещаясь при этом в точку [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](0leq n,k,t,vleq 100)[/latex] . Во второй строке размещено два целых числа [latex]x_{h}[/latex], [latex]y_{h}[/latex] – координаты домика ослика [latex](-10^5leq 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

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

#include <iostream>
#include <cmath>
using namespace std;
 
int main() {
    long int n, k, t, v, hx, hy;
    long int x = 0, y = 0;
    cin >> n >> k >> t >> v;
    cin >> hx >> hy;
    for(long int i = 0; i <= k; i++){
         if(i%4 == 0){ 
             x += 1 + n*i;
             y += 1 + n*i; 
         } else if (i%4 == 1){ 
             x += 1 + n*i;
             y -= 1 + n*i; 
         } else if(i%4 == 2){
             x -= 1 + n*i; 
             y -= 1 + n*i; 
         } else if(i%4 == 3){ 
             x -= 1 + n*i; 
             y += 1 + n*i; 
         } 
    } 
    if(t * t * v * v * 2 >= (x - hx) * (x - hx) + (y - hy) * (y - hy)){
        cout << "Good night Ia";
    } else {
        cout << "Poor Ia";
    }
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

long int n, k, t, v, hx, hy;

long int x = 0, y = 0;

cin >> n >> k >> t >> v;

cin >> hx >> hy;

for(long int i = 0; i <= k; i++){

if(i%4 == 0){

x += 1 + n*i;

y += 1 + n*i;

} else if (i%4 == 1){

x += 1 + n*i;

y -= 1 + n*i;

} else if(i%4 == 2){

x -= 1 + n*i;

y -= 1 + n*i;

} else if(i%4 == 3){

x -= 1 + n*i;

y += 1 + n*i;

}

if(t * t * v * v * 2 >= (x - hx) * (x - hx) + (y - hy) * (y - hy)){

cout << "Good night Ia";

} else {

cout << "Poor Ia";

}

return 0;

}

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

#include <iostream>
using namespace std;

int main() {
    long int n, k, t, v, hx, hy;
    cin >> n >> k >> t >> v >> hx >> hy;
    long int s1, s2, s3, s4;
    long int m1, m2, m3, m4;
    m1 = ((k + 1) % 4 >= 1) ? (k + 1) / 4 + 1 : (k + 1) / 4;
    m2 = ((k + 1) % 4 >= 2) ? (k + 1) / 4 + 1 : (k + 1) / 4;
    m3 = ((k + 1) % 4 >= 3) ? (k + 1) / 4 + 1 : (k + 1) / 4;
    m4 = (k + 1) / 4;
    s1 = (1 + (m1 - 1) * 2 * n) * m1;
    s2 = (1 + n + 2 * n * (m2 - 1)) * m2;
    s3 = (1 + 2 * n + 2 * n * (m3 - 1)) * m3;
    s4 = (1 + 3 * n + 2 * n * (m4 - 1)) * m4;
    long int x = s1 + s2 - s3 - s4, y = s1 - s2 - s3 + s4;
    if (t * t * v * v * 2 >= (x - hx) * (x - hx) + (y - hy) * (y - hy)){
        cout << "Good night Ia";
    } else {
        cout << "Poor Ia";
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

long int n, k, t, v, hx, hy;

cin >> n >> k >> t >> v >> hx >> hy;

long int s1, s2, s3, s4;

long int m1, m2, m3, m4;

m1 = ((k + 1) % 4 >= 1) ? (k + 1) / 4 + 1 : (k + 1) / 4;

m2 = ((k + 1) % 4 >= 2) ? (k + 1) / 4 + 1 : (k + 1) / 4;

m3 = ((k + 1) % 4 >= 3) ? (k + 1) / 4 + 1 : (k + 1) / 4;

m4 = (k + 1) / 4;

s1 = (1 + (m1 - 1) * 2 * n) * m1;

s2 = (1 + n + 2 * n * (m2 - 1)) * m2;

s3 = (1 + 2 * n + 2 * n * (m3 - 1)) * m3;

s4 = (1 + 3 * n + 2 * n * (m4 - 1)) * m4;

long int x = s1 + s2 - s3 - s4, y = s1 - s2 - s3 + s4;

if (t * t * v * v * 2 >= (x - hx) * (x - hx) + (y - hy) * (y - hy)){

cout << "Good night Ia";

} else {

cout << "Poor Ia";

}

return 0;

}

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

Вариант 1

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

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

То есть, результат функции [latex]f(x,y)[/latex] это вектор, на который передвинулся Иа в итерации номер [latex]x[/latex] с изменением шага [latex]y[/latex], а результат [latex]sumlimits_{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 = displaystylefrac{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 = displaystylefrac{k+1}{4} + 1,$ если$ (k+1)vdots 4 >=1$ иначе, $m_1=displaystylefrac{k+1}{4}$

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

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

Для направления на северо-запад:
$$a_4 = 1+3n, d = 4n Rightarrow S_{4} = m_4(1+3n+2n(m_4-1)),$$
где $m_4 = displaystylefrac{k+1}{4} + 1,$ если$ (k+1)vdots 4 >=4$ иначе, $m_4=displaystylefrac{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

Related Images:

Похожее

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

Яна Колчинская says: 26/12/2017 at 23:20

Откорректируй пробелы, в основном в последнем if при умножении.

Войдите, чтобы ответить
- Павел Жуков says: 27/12/2017 at 09:25
  
  Спасибо, я сам не заметил
Мазурок Игорь Евгеньевич says: 27/12/2017 at 12:19

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

Войдите, чтобы ответить
Мазурок Игорь Евгеньевич says: 26/06/2018 at 21:44

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

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

Войдите, чтобы ответить

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

#include <iostream>
using namespace std;
int main() {
    long int n, k, t, v, hx, hy, x, y;
    cin >> n >> k >> t >> v >> hx >> hy;
    y = ((k + 1)%4==1)? (n*k + 1):((k + 1) % 4 == 2)? (-1)*n: ((k + 1) % 4 == 3)?((-1)*n*(k+1)-1):0;
    x= ((k)%4==1)? (nk + 2):((k) % 4 == 2)? (-1)n+1: ((k) % 4 == 3)?(-1)n(k+1):1;
    if (t * t * v * v * 2 >= (x - hx) * (x - hx) + (y - hy) * (y - hy)) {
        cout << "Good night Ia";
    } else {
        cout << "Poor Ia";
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

long int n, k, t, v, hx, hy, x, y;

cin >> n >> k >> t >> v >> hx >> hy;

y = ((k + 1)%4==1)? (n*k + 1):((k + 1) % 4 == 2)? (-1)*n: ((k + 1) % 4 == 3)?((-1)*n*(k+1)-1):0;

x= ((k)%4==1)? (nk + 2):((k) % 4 == 2)? (-1)n+1: ((k) % 4 == 3)?(-1)n(k+1):1;

if (t * t * v * v * 2 >= (x - hx) * (x - hx) + (y - hy) * (y - hy)) {

cout << "Good night Ia";

} else {

cout << "Poor Ia";

}

return 0;

}

Мазурок Игорь Евгеньевич says: 21/09/2018 at 22:19

Если в Вашем решении исправить опечатки, возникшие при копировании, то оно полностью совпадет со вторым вариантом кода в статье. Возможно я ошибаюсь. Исправьте, пожалуйста, опечатки в вашем комментарии, чтобы можно было понять.
Для корректировки комментария имеется кнопка «Edit» в строке с Вашей фамилией и датой комментария.
А про два условных оператора я не понял. Вроде и у автора и у вас он один. И тот логичнее заменить на тернарную операцию. Число ветвлений алгоритма у Вас 7. Три из них точно лишние. Должно быть не более чем 4, как и у автора.
Евгений Рудницкий says: 21/09/2018 at 22:40

Ну у него 8 лишних переменных и ненужные действия вместо того, чтобы сразу посчитать х и у
Мазурок Игорь Евгеньевич says: 24/09/2018 at 23:58
- Код из Вашего комментария все еще выдает массу синтаксических ошибок. Пожалуйста, отнеситесь серьезнее к своим замечаниям.
- «Лишние переменные» не являются проблемой. Особенно если они помогают лучше объяснить алгоритм решения.
- А вот «ненужные действия» действительно плохо. Вы видите у автора какие-то вычисления, которые в дальнейшем не используются? Пожалуйста, укажите какие именно.

Поскольку Евгений Рудницкий так и не откорректировал свое решение, попробуем порассуждать без него. Наверное логично было бы сделать так:

#include <iostream>
using namespace std;
int main() {
    unsigned n, k, t, v, hx, hy, x, y;
    std::cin >> n >> k >> t >> v >> hx >> hy;
    y = k%4 == 0? n*k+1: k%4 == 1? -n: (k%4 == 2)? -n*(k+1)-1: 0;
    x = k%4 == 1? n*k + 2: k%4 == 2? -n + 1: k%4 == 3? -n*(k+1): 1;
    std::cout << (2*t*t*v*v >= (x-hx)*(x-hx)+(y-hy)*(y-hy)? "Good night Ia": "Poor Ia");
    return 0;
}

#include <iostream>

using namespace std;

int main() {

unsigned n, k, t, v, hx, hy, x, y;

std::cin >> n >> k >> t >> v >> hx >> hy;

y = k%4 == 0? n*k+1: k%4 == 1? -n: (k%4 == 2)? -n*(k+1)-1: 0;

x = k%4 == 1? n*k + 2: k%4 == 2? -n + 1: k%4 == 3? -n*(k+1): 1;

std::cout << (2*t*t*v*v >= (x-hx)*(x-hx)+(y-hy)*(y-hy)? "Good night Ia": "Poor Ia");

return 0;

}

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

#include <iostream>
using namespace std;
int main() {
    unsigned n, k, t, v, hx, hy, x, y;
    std::cin >> n >> k >> t >> v >> hx >> hy;
    if (k % 4 == 0) {y = n * k + 1; x = 1;}
    else if (k % 4 == 1) {y = -n; x = n * k + 2;}
    else if (k % 4 == 2) {y = -n * (k + 1) - 1; x = -n + 1;}
    else {y = 0; x = -n * (k + 1);}
    std::cout << (2*t*t*v*v >= (x-hx)*(x-hx)+(y-hy)*(y-hy)? "Good night Ia": "Poor Ia");
    return 0;
}