e-olymp 798. Платформы

12/12/2019 by Анна Цивинская

Условие

В старых играх можно столкнуться с такой ситуацией. Герой прыгает по платформам, висящим в воздухе. Он должен перебраться от одного края экрана до другого. При прыжке с платформы на соседнюю у героя уходит $|y_{2} — y_{1}|$ энергии, где $y_{1}$ и $y_{2}$ — высоты, на которых расположены эти платформы. Кроме того, есть суперприём, позволяющий перескочить через платформу, но на это затрачивается $3\cdot\left|y_{2} — y_{1}\right|$ энергии.

Известны высоты платформ в порядке от левого края до правого. Найдите минимальное количество энергии, достаточное, чтобы добраться с $1$-ой платформы до $n$-ой (последней) и список (последовательность) платформ, по которым нужно пройти.

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

Первая строка содержит количество платформ $n (2 \leqslant n \leqslant 100000)$, вторая $n$ целых чисел, значения которых не превышают по модулю $400$ — высоты платформ.

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

В первой строке выведите минимальное количество энергии. Во второй — количество платформ, по которым нужно пройти, а в третьей выведите список этих платформ.

Тесты

№	Ввод	Вывод
1	4 1 2 3 30	29 4 1 2 3 4
2	2 7 23	16 2 1 2
3	5 0 1 0 1 0	0 3 1 3 5

Код

#include <iostream>
#include <cmath>
using namespace std;

#define MAX 100001

int main() {
    int amount_of_pltf;
    int heights[MAX], energy[MAX], platforms[MAX], list_of_pltf[MAX];
    cin >> amount_of_pltf;
    for (int i = 1; i <= amount_of_pltf; i++) cin >> heights[i];
    
    energy[1] = 0;
    energy[2] = abs(heights[2] - heights[1]);
    platforms[1] = -1;
    platforms[2] = 1;
    
    //В цикле вычисляем значения ячеек energy[j] и platforms[j](3 ≤ j ≤ amount_of_pltf)
    for (int j = 3; j <= amount_of_pltf; j++){
        if((energy[j-1] + abs(heights[j] - heights[j-1])) < (energy[j-2] + 3 * abs(heights[j] - heights[j-2]))){
            energy[j] = energy[j-1] + abs(heights[j] - heights[j-1]);
            platforms[j] = j - 1;
        } else {
            energy[j] = energy[j-2] + 3 * abs(heights[j] - heights[j-2]);
            platforms[j] = j - 2;
        }
    }
    
    //В переменной final_amount вычисляем конечное количество платформ, по которым нужно пройти.
    int final_amount = 0;
    for (int l = amount_of_pltf; l > 0; l = platforms[l]) list_of_pltf[final_amount++] = l;
    
    cout << energy[amount_of_pltf] << "\n" << final_amount << "\n";
    for(int k = final_amount - 1; k >= 0; k--) cout << list_of_pltf[k] << " ";
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

#define MAX 100001

int main() {

int amount_of_pltf;

int heights[MAX], energy[MAX], platforms[MAX], list_of_pltf[MAX];

cin >> amount_of_pltf;

for (int i = 1; i <= amount_of_pltf; i++) cin >> heights[i];

energy[1] = 0;

energy[2] = abs(heights[2] - heights[1]);

platforms[1] = -1;

platforms[2] = 1;

//В цикле вычисляем значения ячеек energy[j] и platforms[j](3 ≤ j ≤ amount_of_pltf)

for (int j = 3; j <= amount_of_pltf; j++){

if((energy[j-1] + abs(heights[j] - heights[j-1])) < (energy[j-2] + 3 * abs(heights[j] - heights[j-2]))){

energy[j] = energy[j-1] + abs(heights[j] - heights[j-1]);

platforms[j] = j - 1;

} else {

energy[j] = energy[j-2] + 3 * abs(heights[j] - heights[j-2]);

platforms[j] = j - 2;

}

//В переменной final_amount вычисляем конечное количество платформ, по которым нужно пройти.

int final_amount = 0;

for (int l = amount_of_pltf; l > 0; l = platforms[l]) list_of_pltf[final_amount++] = l;

cout << energy[amount_of_pltf] << "\n" << final_amount << "\n";

for(int k = final_amount - 1; k >= 0; k--) cout << list_of_pltf[k] << " ";

return 0;

}

Решение

Для решения данной задачи используем несколько массивов для хранения значений затраченной энергии и подсчета платформ. Начнём с энергии. По условию у нас есть два приема для прыжка с одной платформы на другую:

Прыжок с платформы на соседнюю. Затрачивается $|y_{2} — y_{1}|$ энергии. В дальнейшем для упрощения этот вид прыжка будет называться «обычным».
Суперприём — прыжок, позволяющий перескочить через платформу. В этом случае затрачивается $3·|y_{2} — y_{1}|$ энергии. Далее по тексту этот прием будет называться «суперпрыжок».

Нам необходимо проверить какой прием эффективнее. Для этого мы сравниваем сумму затраченной энергии при «обычных» прыжках с первой платформы до третей, с энергией, затраченной при «суперпрыжке» с первой сразу на третью. Этот алгоритм мы рассматриваем для каждой платформы, начиная с $3$ и до последней. Последнее значение, которое мы получим в ходе применения наиболее выгодного приема, и будет являться минимальным количеством энергии.

Параллельно подсчету энергии необходимо нумеровать платформы, на которые мы прыгнули. Опять же, если «суперпрыжок» с первой на третью оказался выгоднее, чем «обычные» прыжки с первой до третей, то третья платформа окажется второй по счету, на которую мы прыгнули. Продолжая эти рассуждения мы подсчитываем нужные нам платформы.

Чтобы вывести список платформ, по которым мы прошли, мы записываем в новый массив номера платформ начиная с последнего значения массива platforms[amount_of_pltf]. Там же, с помощью счетчика считаем общее количество платформ.

Ссылки

Related Images:

e-olymp 806. Платформы — 3

08/12/2019 by Мария Жаркая

Задача

В старых играх можно столкнуться с такой ситуацией. Герой прыгает по платформам, висящим в воздухе. Он должен перебраться от одного края экрана до другого. При прыжке с платформы на соседнюю, у героя уходит $|y_{2} — y_{1}|^2$ энергии, где $y_{1}$ и $y_{2}$ — высоты, на которых расположены эти платформы. Кроме того, есть суперприём, позволяющий перескочить через платформу, но на это затрачивается $3|y_{3} -y_{1}|^2$ энергии.

Известны высоты платформ в порядке от левого края до правого. Найдите минимальное количество энергии, достаточное, чтобы добраться с $1$-й платформы до $n$-й (последней).

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

Первая строка содержит количество платформ $n$ $(2 \leqslant n \leqslant 10^5)$, вторая — $n$ целых чисел, значения которых не превышают по модулю $4000$ — высоты платформ.

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

Выведите единственное целое число — искомую величину энергии.

Тесты

№	Входные данные	Выходные данные
1	4 1 2 3 30	731
2	4 0 1 6 8	40
3	8 1 15 16 23 42 10 84 5	828
4	7 57 54 -55 -34 21 88 -100	55189
5	7 -4000 4000 -4000 4000 -4000 4000 -4000	0

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

#include <iostream>
using namespace std;

int main() {
    int n; long long j, sj, bj; // "цены" прыжка, суперприёма и 3-го типа прыжка
    cin >> n;
    int platforms[n]; long long energy[n]; // создаём массивы для платформ и энергии
    for (int i = 0; i < n; ++i) { 
                cin >> platforms[i]; //считываем высоты платформ  
    }
    energy[0] = 0; 
    for (int i = 1; i < n; ++i) {
        // обычный прыжок
        j = (platforms[i] - platforms[i - 1]) * (platforms[i] - platforms[i - 1]);
        // 3-й тип прыжка
        bj = (platforms[i] - platforms[i + 1]) * (platforms[i] - platforms[i + 1]) + 
        3 * (platforms[i + 1] - platforms[i - 1])*(platforms[i + 1] - platforms[i - 1]);
        // суперприём 
        if (i == 1) sj = max(j, bj);
        else sj = 3 * (platforms[i] - platforms[i - 2]) * (platforms[i] - platforms[i - 2]);
        if (i == n - 1) bj = max(j, sj);
        //количество энергии на i-й платформе
        energy[i] = min(energy[i - 1] + bj, min(energy[i - 1] + j, energy[i - 2] + sj));
    }
    cout << energy[n - 1];
}

#include <iostream>

using namespace std;

int main() {

int n; long long j, sj, bj; // "цены" прыжка, суперприёма и 3-го типа прыжка

cin >> n;

int platforms[n]; long long energy[n]; // создаём массивы для платформ и энергии

for (int i = 0; i < n; ++i) {

cin >> platforms[i]; //считываем высоты платформ

}

energy[0] = 0;

for (int i = 1; i < n; ++i) {

// обычный прыжок

j = (platforms[i] - platforms[i - 1]) * (platforms[i] - platforms[i - 1]);

// 3-й тип прыжка

bj = (platforms[i] - platforms[i + 1]) * (platforms[i] - platforms[i + 1]) +

3 * (platforms[i + 1] - platforms[i - 1])*(platforms[i + 1] - platforms[i - 1]);

// суперприём

if (i == 1) sj = max(j, bj);

else sj = 3 * (platforms[i] - platforms[i - 2]) * (platforms[i] - platforms[i - 2]);

if (i == n - 1) bj = max(j, sj);

//количество энергии на i-й платформе

energy[i] = min(energy[i - 1] + bj, min(energy[i - 1] + j, energy[i - 2] + sj));

}

cout << energy[n - 1];

}

Решение

Чтобы решить задачу, мы создадим массив $energy$, где будем хранить минимальную энергию, которую герой потратит для прыжка на очередную $i$-ю платформу. Для этого необходимо для каждой платформы, начиная со второй, рассмотреть три вида прыжка:

прыжок с предыдущей $i — 1$ платформы.
суперприём, то есть прыжок c $i — 2$ платформы.
3-й вид: суперприём с $i — 1$ платформы на $i + 1$ и прыжок назад на $i$.

«Цены» за обычный прыжок и суперприём мы можем найти из формул данных в условии, с 3-м же сложнее — результатом будет сумма «цены» суперприёма $3(y_{i+1} — y_{i-1})^2$ и «цены» прыжка назад $(y_{i} — y_{i+1})^2$.

Для понимания схемы можно рассмотреть в качестве примера второй тест.
Синим обозначен 3-ий тип. Красными цифрами — весь путь.

второй тест

Каждый из 3-х путей даст своё значение энергии, равное сумме «цены» прыжка на $i$-ю платформу и значения в той, из которой герой совершил прыжок. Наименьшей энергией для этой платформы будет минимум из этих трех значений.
На второй платформе $(i = 1)$ в случае суперприёма мы выходим за границы массива и получаем независимое значение, поэтому эффективнее будет в качестве «цены» выбирать максимум из двух других уже найденных значений. Аналогично на последней $(i = n — 1)$ и 3-м типе прыжка, максимум будет невыгодным и соответственно не будет выбран как минимум в $energy_{i}$.

Ссылки

Условие задачи на e-olymp
Код программы на ideone

Related Images:

Ragnarök — Power of Thor

12/10/2014 by Байков Дмитро

Четвертая по счету игра на сайте называется Ragnarök — Power of Thor, где нам посчастливилось быть Великим Воином Тором. Тору необходимо самым кратчайшим путем добраться до источника энергии, которая придаст ему еще больше сил и уверенности в дальнейших сражениях.

Пока еще не всемогущий Тор ждет указаний

Инициализация

В начале нам сообщают положение на карте источника и самого персонажа (их координаты по X и Y) (int LX, LY) (int TX, TY) соответственно.

Игровой цикл

Бесконечно (до конца игры) повторяемый игровой цикл состоит из любого количества кода, который читает входной поток и выводит команду в выходной поток.

Вход

В самом игровом цикле нам сообщают величину энергии Тора (int E), которая уменьшается на 1 с каждым последующим ходом.

Выход

В выходной поток необходимо вывести одну строку. Нам представлено всего 8 возможных вариантов дальнейшего передвижения Тора. Screenshot_2222

Движение возможно только как показано на картинке (т.е. по компасу). Например, если мы хотим, чтобы персонаж двигался вправо (на восток) мы выведем буквочку E и т.д.

Перевод строки на новую обязателен.

Тест 1

Запуская программу впервые, Тор будет сам не свой, двигаясь совсем не по направлению к источнику.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

/**
 * Auto-generated code below aims at helping you parse
 * the standard input according to the problem statement.
 **/
int main()
{
    int LX; // the X position of the light of power
    int LY; // the Y position of the light of power
    int TX; // Thor's starting X position
    int TY; // Thor's starting Y position
    cin >> LX >> LY >> TX >> TY; cin.ignore();

    // game loop
    while (1) {
        int E; // The level of Thor's remaining energy, representing the number of moves he can still make.
        cin >> E; cin.ignore();

        // Write an action using cout. DON'T FORGET THE "<< endl"
        // To debug: cerr << "Debug messages..." << endl;

        cout << "SE" << endl; // A single line providing the move to be made: N NE E SE S SW W or NW
    }
}

#include <iostream>

#include <string>

#include <vector>

#include <algorithm>

using namespace std;

/**

* Auto-generated code below aims at helping you parse

* the standard input according to the problem statement.

**/

int main()

{

int LX; // the X position of the light of power

int LY; // the Y position of the light of power

int TX; // Thor's starting X position

int TY; // Thor's starting Y position

cin >> LX >> LY >> TX >> TY; cin.ignore();

// game loop

while (1) {

int E; // The level of Thor's remaining energy, representing the number of moves he can still make.

cin >> E; cin.ignore();

// Write an action using cout. DON'T FORGET THE "<< endl"

// To debug: cerr << "Debug messages..." << endl;

cout << "SE" << endl; // A single line providing the move to be made: N NE E SE S SW W or NW

}

Пройти первый и второй тесты, кажется просто, якобы написать в какую сторону мальчику бежать и только наблюдать за процессом, но не тут то было. Третий тест показывает нам, что все-таки придется подумать об адекватном решении.

Адекватное решение

Немного подумав вспоминаем, что нам даны начальные координаты как источника так и энергии. Сразу же приходит в голову мысль, что их надо сравнивать.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <math.h>
using namespace std;

/**
 * Auto-generated code below aims at helping you parse
 * the standard input according to the problem statement.
 **/
int main()
{
    int LX; // the X position of the light of power
    int LY; // the Y position of the light of power
    int TX; // Thor's starting X position
    int TY; // Thor's starting Y position
    cin >> LX >> LY >> TX >> TY; cin.ignore();

    // game loop
    while (1) 
    {
        int E; // The level of Thor's remaining energy, representing the number of moves he can still make.
        cin >> E; cin.ignore();
        if (LX == TX) //Movement along the X axis.
        {
            if (( LY - TY ) < 0)
            {
            cout << "N" << endl;
            }
            else 
            {
            cout << "S" << endl;
            }
        }    
        if (TY == LY) //Movement along the Y axis.
        {
            if (( LX - TX ) < 0)
            {
            cout << "W" << endl;
            }
            else 
            {
                cout << "E" << endl;
            }
        }
    }
}

#include <iostream>

#include <string>

#include <vector>

#include <algorithm>

#include <math.h>

using namespace std;

/**

* Auto-generated code below aims at helping you parse

* the standard input according to the problem statement.

**/

int main()

{

int LX; // the X position of the light of power

int LY; // the Y position of the light of power

int TX; // Thor's starting X position

int TY; // Thor's starting Y position

cin >> LX >> LY >> TX >> TY; cin.ignore();

// game loop

while (1)

{

int E; // The level of Thor's remaining energy, representing the number of moves he can still make.

cin >> E; cin.ignore();

if (LX == TX) //Movement along the X axis.

{

if (( LY - TY ) < 0)

{

cout << "N" << endl;

}

else

{

cout << "S" << endl;

}

if (TY == LY) //Movement along the Y axis.

{

if (( LX - TX ) < 0)

{

cout << "W" << endl;

}

else

{

cout << "E" << endl;

}

Если равны координаты Тора и источника энергии по X, то тут мы находим разность координат источника и Тора по Y, если LY — TY > 0 (Источник находится выше Тора по оси Y), то идем на юг (вверх), в противном случае на север (вниз). Аналогично и с движением по Y, что дает нам силы пройти первые два теста.

Дважды заряженный энергией боец рвется подзарядиться и в третий раз, но вдруг остается стоять на месте. Обескураженный обстоятельствами Тор замечает, что источник уже находится не ровно по оси движения, а под каким-то определенным углом. Оставаясь на месте, Тор принимает обет молчания (не выводит ничего на экран) и погружается в свои мысли.

Цикл for идет на помощь

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

Код на C++:

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <math.h>
using namespace std;

/**
 * Auto-generated code below aims at helping you parse
 * the standard input according to the problem statement.
 **/
int main()
{
    int LX; // the X position of the light of power
    int LY; // the Y position of the light of power
    int TX; // Thor's starting X position
    int TY; // Thor's starting Y position
    cin >> LX >> LY >> TX >> TY; cin.ignore();

    // game loop
    while (1) 
    {
        int E; // The level of Thor's remaining energy, representing the number of moves he can still make.
        cin >> E; cin.ignore();
        if (LX == TX) //Movement along the X axis.
        {
            if (( LY - TY ) < 0)
            {
            cout << "N" << endl;
            }
            else 
            {
            cout << "S" << endl;
            }
        }    
        if (TY == LY) //Movement along the Y axis.
        {
            if (( LX - TX ) < 0)
            {
            cout << "W" << endl;
            }
            else 
            {
                cout << "E" << endl;
            }
        }
        if (( LX - TX ) > 0) //Movement to the left half of the map
        {
            
            if (( LY - TY ) < 0)
            {
               for(int i = 0;i < abs ( LY - TY );i++)
               {
                    cout << "NE" << endl;
               }
                for (int i = 0;i < abs ( LX - abs ( LY - TY ));i++)
                {
                    cout << "E" << endl;
                }
            }
            else 
            {
                if (( LY - TY ) > 0)
                 {
                    for(int i = 0;i < abs ( LY - TY );i++)
                    {
                        cout << "SE" << endl;
                    }
                   for (int i = 0;i < abs ( LX - abs ( LY - TY ));i++)
                    {
                        cout << "E" << endl;
                    }
                }
            }
        }
        if (( LX - TX ) < 0) //Movement to the right half of the map
        {
            
            if (( LY - TY ) < 0)
            {
                for(int i = 0;i < abs ( LY - TY );i++)
                {
                    cout << "NW" << endl;
                }
                for (int i=0;i < abs ( TX - ( LY - TY ));i++)
                {
                    cout << "W" << endl;
                }
            }
            else 
            {
                if (( LY - TY ) > 0)
                {
                   for (int i = 0;i < abs ( LY - TY );i++)
                   {
                        cout << "SW" << endl;
                   }
                    for (int i = 0;i< abs ( TX - ( LY - TY ));i++)
                    {
                        cout << "W" << endl;
                    }
                }
            }
        }
    }
}

100

101

102

103

104

105

106

#include <iostream>

#include <string>

#include <vector>

#include <algorithm>

#include <math.h>

using namespace std;

/**

* Auto-generated code below aims at helping you parse

* the standard input according to the problem statement.

**/

int main()

{

int LX; // the X position of the light of power

int LY; // the Y position of the light of power

int TX; // Thor's starting X position

int TY; // Thor's starting Y position

cin >> LX >> LY >> TX >> TY; cin.ignore();

// game loop

while (1)

{

int E; // The level of Thor's remaining energy, representing the number of moves he can still make.

cin >> E; cin.ignore();

if (LX == TX) //Movement along the X axis.

{

if (( LY - TY ) < 0)

{

cout << "N" << endl;

}

else

{

cout << "S" << endl;

}

if (TY == LY) //Movement along the Y axis.

{

if (( LX - TX ) < 0)

{

cout << "W" << endl;

}

else

{

cout << "E" << endl;

}

if (( LX - TX ) > 0) //Movement to the left half of the map

{

if (( LY - TY ) < 0)

{

for(int i = 0;i < abs ( LY - TY );i++)

{

cout << "NE" << endl;

}

for (int i = 0;i < abs ( LX - abs ( LY - TY ));i++)

{

cout << "E" << endl;

}

else

{

if (( LY - TY ) > 0)

{

for(int i = 0;i < abs ( LY - TY );i++)

{

cout << "SE" << endl;

}

for (int i = 0;i < abs ( LX - abs ( LY - TY ));i++)

{

cout << "E" << endl;

}

if (( LX - TX ) < 0) //Movement to the right half of the map

{

if (( LY - TY ) < 0)

{

for(int i = 0;i < abs ( LY - TY );i++)

{

cout << "NW" << endl;

}

for (int i=0;i < abs ( TX - ( LY - TY ));i++)

{

cout << "W" << endl;

}

else

{

if (( LY - TY ) > 0)

{

for (int i = 0;i < abs ( LY - TY );i++)

{

cout << "SW" << endl;

}

for (int i = 0;i< abs ( TX - ( LY - TY ));i++)

{

cout << "W" << endl;

}

Код на Java:

import java.util.*;
import java.io.*;
import java.math.*;

class Player 
{
    public static void main(String args[]) 
    {
    	Scanner in = new Scanner(System.in);
	    int lightX = in.nextInt(); // the X position of the light of power
	    int lightY = in.nextInt(); // the Y position of the light of power
	    int initialTX = in.nextInt(); // Thor's starting X position
	    int initialTY = in.nextInt(); // Thor's starting Y position
	
	    // game loop
	    while (true) 
	    {
	        int remainingTurns = in.nextInt();// The remaining amount of turns Thor can move. Do not remove this line.
	        if (lightX == initialTX) //Movement along the X axis.
	        {
	            if ((lightY - initialTY) < 0)
	            	System.out.println("N");
	            else 
	            	System.out.println("S");
	        }    
	        if (initialTY == lightY) //Movement along the Y axis.
	        {
	            if ((lightX - initialTX) < 0)
	            	System.out.println("W");
	            else 
	                System.out.println("E");
	        }
	        if ((lightX - initialTX) > 0) //Movement to the left half of the map
	        {
	            if ((lightY - initialTY) < 0)
	            {
	               for(int i = 0;i < Math.abs(lightY - initialTY);i++)
	                    System.out.println("NE");
	               for (int i = 0;i < Math.abs(lightX - Math.abs(lightY - initialTY));i++)
	                   System.out.println("E");
	            }
	            else 
	            {
	                if ((lightY - initialTY) > 0)
	                 {
	                    for(int i = 0;i < Math.abs(lightY - initialTY);i++)
	                    	System.out.println("SE");
	               		for (int i = 0;i < Math.abs(lightX - Math.abs(lightY - initialTY));i++)
	                		System.out.println("E");
	                }
	            }
	        }
	        if ((lightX - initialTX) < 0) //Movement to the right half of the map
	        {
	            
	            if ((lightY - initialTY) < 0)
	            {
	                for(int i = 0;i < Math.abs(lightY - initialTY);i++)
	            		System.out.println("NW");
	                for (int i=0;i < Math.abs(initialTX - (lightY - initialTY));i++)
	                	System.out.println("W");
	            }
	            else 
	            {
	                if ((lightY - initialTY) > 0)
	                {
	                   for(int i = 0;i < Math.abs(lightY - initialTY);i++)
	            		System.out.println("SW");
	                for (int i=0;i < Math.abs(initialTX - (lightY - initialTY));i++)
	                	System.out.println("W");
	                }
	            }
	        }
	    }
	}
}

import java.util.*;

import java.io.*;

import java.math.*;

class Player

{

public static void main(String args[])

{

Scanner in = new Scanner(System.in);

int lightX = in.nextInt(); // the X position of the light of power

int lightY = in.nextInt(); // the Y position of the light of power

int initialTX = in.nextInt(); // Thor's starting X position

int initialTY = in.nextInt(); // Thor's starting Y position

// game loop

while (true)

{

int remainingTurns = in.nextInt();// The remaining amount of turns Thor can move. Do not remove this line.

if (lightX == initialTX) //Movement along the X axis.

{

if ((lightY - initialTY) < 0)

System.out.println("N");

else

System.out.println("S");

}

if (initialTY == lightY) //Movement along the Y axis.

{

if ((lightX - initialTX) < 0)

System.out.println("W");

else

System.out.println("E");

}

if ((lightX - initialTX) > 0) //Movement to the left half of the map

{

if ((lightY - initialTY) < 0)

{

for(int i = 0;i < Math.abs(lightY - initialTY);i++)

System.out.println("NE");

for (int i = 0;i < Math.abs(lightX - Math.abs(lightY - initialTY));i++)

System.out.println("E");

}

else

{

if ((lightY - initialTY) > 0)

{

for(int i = 0;i < Math.abs(lightY - initialTY);i++)

System.out.println("SE");

for (int i = 0;i < Math.abs(lightX - Math.abs(lightY - initialTY));i++)

System.out.println("E");

}

if ((lightX - initialTX) < 0) //Movement to the right half of the map

{

if ((lightY - initialTY) < 0)

{

for(int i = 0;i < Math.abs(lightY - initialTY);i++)

System.out.println("NW");

for (int i=0;i < Math.abs(initialTX - (lightY - initialTY));i++)

System.out.println("W");

}

else

{

if ((lightY - initialTY) > 0)

{

for(int i = 0;i < Math.abs(lightY - initialTY);i++)

System.out.println("SW");

for (int i=0;i < Math.abs(initialTX - (lightY - initialTY));i++)

System.out.println("W");

}

Получается вот такой вот симпатичный код, описывающий все возможные ситуации по передвижению Тора (переносит Тора к источнику из любой точки карты). Разбивая на два возможных случая, движение в правой половине карты и в левой половине карты, получается, что программа охватывает любую ее точку. В самом цикле возьмем модуль между разностью (т.к. источник может находиться и ниже Тора). Сравниваем LX и TX, для того, чтобы узнать в какой половине карты находится источник. Если LX — TX > 0, то в цикле будем отнимать от LX, в противном случае — от TX, дабы не получить отрицательные значения. В конечном счете переменная E (энергия) там так и не понадобилось, так как воин и так находил кратчайшее расстояние.

Пройдя все тесты, наш довольный рыцарь полон сил и энергии. Пожелаем удачи ему в дальнейших приключениях.