e-olymp 47. Паркет из треугольников

Задача

Прямоугольную комнату размерами [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

Код 2

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

Способ 1

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

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

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

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

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

Позиция [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. Делалось это при помощи следующей строки кода

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

Способ 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] — столбце. Удобнее всего хранить значения в массиве, поэтому мы создаем

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

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

Ссылки

Задача на e-olymp

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

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

4 thoughts on “e-olymp 47. Паркет из треугольников

  1. Хорошо.
    А можете прокомментировать такое решение?

    Дело не в том, что он короче. Он намекает, как можно было решать вообще без массивов.

  2. #include
    #include

    using namespace std;

    int main()
    {
    long long b,m,a,n,z,o,dm,dn,k;
    cin >> m >> n ;
    cin>> a >>b;
    dm=((a+1)/2-1)%m-((b+1)/2-1)%m;
    dn=(a-1)/(m2)-(b-1)/(m2);
    o=dmdn<0?min(abs(dm),abs(dn)):0;
    k=dm>0?1:-1;
    a=a+(m-1)
    2ko;
    z=(a+b)%2==0?0:max(a,b)%2==0?1:-1;
    z=z+abs(dm)2+abs(dn)2-o*2;
    cout<<z;
    }

    даже без масивов

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