Задача

Прямоугольную комнату размерами [latex]m[/latex] на [latex]n[/latex] (сначала по горизонтали, а потом по вертикали) замостили треугольными плитками и их пронумеровали, как показано на рисунке.

За один шаг можно переместиться с одной паркетины на другую только через общую сторону. Найти наименьшее количество шагов, нужных для перемещения с паркетины [latex]a[/latex] на паркетину [latex]b[/latex].

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

Во входном файле в первой строке через пробел заданы значения [latex]n[/latex], [latex]m[/latex] [latex](1 ≤ n, m ≤ 100)[/latex], а во второй — [latex]a[/latex], [latex]b[/latex].

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

Искомое количество шагов.

Тесты

#	Входные данные	Выходные данные
1	5 4 25 38	5
2	5 4 6 22	4
3	5 4 15 22	3
4	3 2 1 12	7
5	3 2 6 12	2

Код 1

#include <iostream>
using namespace std;

int main()
{
    int vertSize;
    int horSize;
    int firstNumber;
    int lastNumber;
    cin >> horSize >> vertSize >> firstNumber >> lastNumber;
    //создание динамического массива
    int*** arr;
    arr = new int**[vertSize];
    int count = 1;
    int z = 2;
    int apos[3];
    int bpos[3];
    for (int i = 0; i < vertSize; i++)
    {
        arr[i] = new int*[horSize];
        for (int j = 0; j < horSize; j++)
        {
            arr[i][j] = new int[z];
            for (int k = 0; k < 2; k++)
            {
                arr[i][j][k] = count;
                count++;
                // определяем позицию наших элементов в массиве
                if (arr[i][j][k] == firstNumber)
                {
                    apos[0] = i;
                    apos[1] = j;
                    apos[2] = k;
                }
                if (arr[i][j][k] == lastNumber)
                {
                    bpos[0] = i;
                    bpos[1] = j;
                    bpos[2] = k;
                }
            }
        }
    }
    int hor;
    int vert;
    // направление движения по вертикали
    vert = apos[0] < bpos[0] ? 1 : (apos[0] == bpos[0] ? 0 : -1);
    // направление движения по горизонтали
    hor = apos[1] < bpos[1] ? 1 : (apos[1] == bpos[1] ? 0 : -1);
    int stepCount = 0;
    int curCell[3];
    for (int i = 0; i < 3; i++)
        curCell[i] = apos[i];

    bool dir;
    if (apos[1] < bpos[1] && firstNumber % 2 == 0 || apos[1] > bpos[1] && firstNumber % 2 != 0)
        dir = false;
    else
        dir = true;
    while (1)
    {
        if (dir && vert != 0)
        {
            if (vert == -1)
            {
                if (curCell[2] == 0)
                    curCell[0]--;
                curCell[2] = !((bool)curCell[2]);
                stepCount++;
            }
            else
            {
                if (curCell[2] == 1)
                    curCell[0]++;
                curCell[2] = !((bool)curCell[2]);
                stepCount++;
            }
        }
        else if (!dir && hor != 0)
        {
            if (hor == -1)
            {
                if (curCell[2] == 0)
                    curCell[1]--;
                curCell[2] = !((bool)curCell[2]);
                stepCount++;
            }
            else
            {
                if (curCell[2] == 1)
                    curCell[1]++;
                curCell[2] = !((bool)curCell[2]);
                stepCount++;
            }
        }
        dir = !dir;

        if (curCell[0] == bpos[0])
            vert = 0;
        if (curCell[1] == bpos[1])
            hor = 0;

        if (curCell[0] == bpos[0] && curCell[1] == bpos[1] && curCell[2] != bpos[2])
        {
            curCell[2] = !((bool)curCell[2]);
            stepCount++;
        }

        bool end;
        for (int i = 0; i < 3; i++)
        {
            if (curCell[i] != bpos[i])
            {
                end = false;
                break;
            }
            end = true;
        }
        if (end)
            break;
    }
    cout << stepCount << endl;
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

#include <iostream>

using namespace std;

int main()

{

int vertSize;

int horSize;

int firstNumber;

int lastNumber;

cin >> horSize >> vertSize >> firstNumber >> lastNumber;

//создание динамического массива

int*** arr;

arr = new int**[vertSize];

int count = 1;

int z = 2;

int apos[3];

int bpos[3];

for (int i = 0; i < vertSize; i++)

{

arr[i] = new int*[horSize];

for (int j = 0; j < horSize; j++)

{

arr[i][j] = new int[z];

for (int k = 0; k < 2; k++)

{

arr[i][j][k] = count;

count++;

// определяем позицию наших элементов в массиве

if (arr[i][j][k] == firstNumber)

{

apos[0] = i;

apos[1] = j;

apos[2] = k;

}

if (arr[i][j][k] == lastNumber)

{

bpos[0] = i;

bpos[1] = j;

bpos[2] = k;

}

int hor;

int vert;

// направление движения по вертикали

vert = apos[0] < bpos[0] ? 1 : (apos[0] == bpos[0] ? 0 : -1);

// направление движения по горизонтали

hor = apos[1] < bpos[1] ? 1 : (apos[1] == bpos[1] ? 0 : -1);

int stepCount = 0;

int curCell[3];

for (int i = 0; i < 3; i++)

curCell[i] = apos[i];

bool dir;

if (apos[1] < bpos[1] && firstNumber % 2 == 0 || apos[1] > bpos[1] && firstNumber % 2 != 0)

dir = false;

else

dir = true;

while (1)

{

if (dir && vert != 0)

{

if (vert == -1)

{

if (curCell[2] == 0)

curCell[0]--;

curCell[2] = !((bool)curCell[2]);

stepCount++;

}

else

{

if (curCell[2] == 1)

curCell[0]++;

curCell[2] = !((bool)curCell[2]);

stepCount++;

}

else if (!dir && hor != 0)

{

if (hor == -1)

{

if (curCell[2] == 0)

curCell[1]--;

curCell[2] = !((bool)curCell[2]);

stepCount++;

}

else

{

if (curCell[2] == 1)

curCell[1]++;

curCell[2] = !((bool)curCell[2]);

stepCount++;

}

dir = !dir;

if (curCell[0] == bpos[0])

vert = 0;

if (curCell[1] == bpos[1])

hor = 0;

if (curCell[0] == bpos[0] && curCell[1] == bpos[1] && curCell[2] != bpos[2])

{

curCell[2] = !((bool)curCell[2]);

stepCount++;

}

bool end;

for (int i = 0; i < 3; i++)

{

if (curCell[i] != bpos[i])

{

end = false;

break;

}

end = true;

}

if (end)

break;

}

cout << stepCount << endl;

return 0;

}

Код 2

#include <iostream>
using namespace std;
int main() {
    int vertSize;
    int horSize;
    int firstNumber;
    int lastNumber;
    cin >> horSize >> vertSize >> firstNumber >> lastNumber;
    if (firstNumber > lastNumber){
        swap(firstNumber, lastNumber);  
    } 
    //вычисление координат
    int firstNumberx = (firstNumber - 1) % (2 * horSize) + 1;
    int firstNumbery = (firstNumber - 1) / (2 * horSize) + 1;
    int lastNumberx = (lastNumber - 1) % (2 * horSize) + 1;
    int lastNumbery = (lastNumber - 1) / (2 * horSize) + 1;
    //создание и задание размера для статического массива
    int Search[2 * horSize];
    Search[firstNumberx - 1] = 0;
    int step = 1;
    for (int i = firstNumberx - 2; i >= 0; i--){
        Search[i] = step++;
        
    }
    step = 1;
    for (int i = firstNumberx; i < 2 * horSize; i++){
        Search[i] = step++;
    }
    //сравнение по у
    for (int j = firstNumbery; j < lastNumbery; j++) {
        for (int i = 1; i < 2 * horSize; i += 2) {
            Search[i - 1] = Search[i] + 1;
            Search[i] += 2;
            //определние значения на предпоследнем элементе
            if (((i - 2) >= 0) && (Search[i]<Search[i - 2])){
                Search[i - 2] = Search[i];
            }
        }
    }
    cout << Search[lastNumberx - 1] << endl;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int vertSize;

int horSize;

int firstNumber;

int lastNumber;

cin >> horSize >> vertSize >> firstNumber >> lastNumber;

if (firstNumber > lastNumber){

swap(firstNumber, lastNumber);

}

//вычисление координат

int firstNumberx = (firstNumber - 1) % (2 * horSize) + 1;

int firstNumbery = (firstNumber - 1) / (2 * horSize) + 1;

int lastNumberx = (lastNumber - 1) % (2 * horSize) + 1;

int lastNumbery = (lastNumber - 1) / (2 * horSize) + 1;

//создание и задание размера для статического массива

int Search[2 * horSize];

Search[firstNumberx - 1] = 0;

int step = 1;

for (int i = firstNumberx - 2; i >= 0; i--){

Search[i] = step++;

}

step = 1;

for (int i = firstNumberx; i < 2 * horSize; i++){

Search[i] = step++;

}

//сравнение по у

for (int j = firstNumbery; j < lastNumbery; j++) {

for (int i = 1; i < 2 * horSize; i += 2) {

Search[i - 1] = Search[i] + 1;

Search[i] += 2;

//определние значения на предпоследнем элементе

if (((i - 2) >= 0) && (Search[i]<Search[i - 2])){

Search[i - 2] = Search[i];

}

cout << Search[lastNumberx - 1] << endl;

return 0;

}

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

Способ 1

Каждый элемент имеет три параметра:

Положение в строке
Положение в столбце
Четность

Для хранения этих значений создадим трёхмерный массив. Существует несколько вариантов расположения элементов в нем:

Оба элемента расположены в одной строке строке
Оба элемента расположены в одном столбце
Оба элемента расположены на одной диагонали
Произвольное расположение

Для удобства мы завели счетчик шагов.
Рассмотрим случай когда первый элемент меньше, чем последний, допустим, что

firstNumber = 7;
lastNumber = 14;

1 2	firstNumber = 7; lastNumber = 14;

Позиция [latex]7[/latex] [latex]\left[ 0 , 3 , 0 \right] [/latex].
Позиция [latex]14[/latex] [latex]\left[ 1 , 2 , 1 \right] [/latex].
Для случая [latex] 5*4 [/latex] эти элементы расположены на одной диагонали. Далее идет создание вспомогательного 3-х мерного массива, в который мы положим координаты [latex]7[/latex]. Идея состоит в том, чтобы временный массив и массив с координатам [latex]14[/latex] совпали. Т.к [latex]7[/latex] нечетное, а [latex]14[/latex] четное, то первый «шаг» будет сделан по горизонтали, тем самым мы уровняем координату, отвечающую за четность. Далее идет сравнение по «строчной» координате, т.к. они не совпадают, то делается «шаг» вниз. Далее остается сделать «шаг» влево, чтобы совпали координаты по столбцам.
Аналогичные проверки делаются для остальных случаев.
Важно отметить, что лучше всего для проверки подходят переменные типа bool. Поэтому в некоторых местах были использованы преобразование из типа int в тип bool. Делалось это при помощи следующей строки кода

(bool)curCell[2]

1	(bool)curCell[2]

Для более оптимальной работы были использованы тернарные операции. Они скрывают под собой условие, выполнение которого состоит из одной строки кода.

Способ 2

Для того, чтобы наш код был универсален для случая [latex]firstNumber > lastNumber[/latex] и [latex]firstNumber < lastNumber[/latex] мы меняем местами [latex]firstNumber[/latex] и [latex]lastNumber[/latex].
Следующим шагом будет определение позиции [latex]firstNumber[/latex] и [latex]lastNumber[/latex]. Положим, что [latex] x [/latex] — это позиция в строке, а [latex] y [/latex] — столбце. Удобнее всего хранить значения в массиве, поэтому мы создаем

int V[2 * horSize];

1	int V[2 * horSize];

массив, переменные в котором будет иметь тип [latex] int [/latex], а размер будет фиксированный. Для определения количества шагов заведем переменную с типом [latex] int [/latex].
Важно отметить, что идея решения данного способа состоит в том, чтобы на позиции

Search[firstNumberx - 1];

1	Search[firstNumberx - 1];

стояло количество шагов, совершенных в ходе решения.

Ссылки

Задача на e-olymp

Код задачи на ideone ( способ 1 )

Код задачи на ideone ( способ 2 )

Related Images:

Задача

Герон Александрийский

Задано стороны [latex]a, b, c, d[/latex] и диагональ [latex]f[/latex] выпуклого четырехугольника. Определить площадь четырехугольника, используя вспомогательную функцию вычисления площади треугольника по формуле Герона.

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

В одной строке задано 5 действительных чисел [latex] a, b, с, d, f[/latex] [latex](0 < a, b, c, d, f ≤ 100)[/latex], как показано на рисунке.

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

Вывести площадь четырехугольника с точностью 4 знака после десятичной точки.

Тесты

#	Входные данные	Выходные данные
1	2 2 2 2 2	3.4641
2	7 7 5 6 2	11.6120
3	9 5 3 2 4	2.9047
4	5 7 2 3 4	12.7027
5	7 8 6 2 5	22.0043

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

#include <iostream>
#include <cmath>//данную библиотеку подключаем  для того, чтобы была возможность извлечь корень
#include <iomanip>//данную библиотеку подключаем для того, чтобы установить кол-во знаков после запятой
using namespace std;

int main() {
    double a,b,c,d,f;//длины сторон треугольника
    double S1,S2,SO;//площади треугольников и общая площадь соответственно
    double P1,P2,p1,p2;//периметр и полупериметр соотвественно
    double G1,G2;//выражение под корнем
    cin>>a>>b>>c>>d>>f;
    P1= a+b+f;//периметр первого треугольника
    p1= P1/2;//полупериметр первого треугольника
    P2= d+c+f;//периметр второго треугольника
    p2= P2/2;//полупериметр второго  треугольника
    G1=p1*(p1-a)*(p1-b)*(p1-f);//выражение под корнем 
    S1=sqrt(G1);//пользуясь формулой Герона извлекаем корень
    //аналогично для второго треугольника
    G2=p2*(p2-d)*(p2-c)*(p2-f);
    S2=sqrt(G2);
    SO=S1+S2;//находим общую площадь фигуры состоящую из двух треугольников
    cout<<fixed<<setprecision(4)<<SO;
    return 0;
}

#include <iostream>

#include <cmath>//данную библиотеку подключаем для того, чтобы была возможность извлечь корень

#include <iomanip>//данную библиотеку подключаем для того, чтобы установить кол-во знаков после запятой

using namespace std;

int main() {

double a,b,c,d,f;//длины сторон треугольника

double S1,S2,SO;//площади треугольников и общая площадь соответственно

double P1,P2,p1,p2;//периметр и полупериметр соотвественно

double G1,G2;//выражение под корнем

cin>>a>>b>>c>>d>>f;

P1= a+b+f;//периметр первого треугольника

p1= P1/2;//полупериметр первого треугольника

P2= d+c+f;//периметр второго треугольника

p2= P2/2;//полупериметр второго треугольника

G1=p1*(p1-a)*(p1-b)*(p1-f);//выражение под корнем

S1=sqrt(G1);//пользуясь формулой Герона извлекаем корень

//аналогично для второго треугольника

G2=p2*(p2-d)*(p2-c)*(p2-f);

S2=sqrt(G2);

SO=S1+S2;//находим общую площадь фигуры состоящую из двух треугольников

cout<<fixed<<setprecision(4)<<SO;

return 0;

}

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

Дано

Фигура, состоящая из двух треугольников;

Цель

Посчитать площадь данной фигуры;

Идея

Разбить фигуру на два треугольника и посчитать площадь каждого в отдельности, а потом сложить.

Способ решения

Вспомним формулу Герона [latex] S = \sqrt{p \cdot(p-a) \cdot(p-b) \cdot(p-c)}[/latex].
Поймем, что нам не хватает некоторых данных, а именно [latex]p[/latex].
Понимаем, что [latex]p[/latex] — это полупериметр, который находится по формуле [latex]p=\frac{P}{2}[/latex].
Возникает вопрос, что такое [latex]P[/latex] ? Приходим к выводу, что это периметр.
Находим формулу периметра, который равен [latex]P=a+b+c[/latex]. Данная формула была подведена под условие нашей задачи.
После того как мы вывели формулы, можем приступать к решению задачи.
Подставляя исходные данные в формулы, которые были представлены выше, получаем результат.
Более подробное описание каждого действия представлено выше в коде. Это сделано для того, чтобы пользователь получал ответы на интересующие его вопросы непосредственно в момент их возникновения.