В споре рождается истина

А теперь я заберу у вас кайф, потому что если вы продолжите читать дальше, то уже не сможете решить эту задачу сами, потому что я сам расскажу вам, как это сделать. Если что, лучше попробуйте сами, а потом читайте этот пост до конца.
Задача
Кому не нравится английский, там же есть и русская версия (слева сверху “RU”).

А теперь решение.
Для начала, нарисуем граф, в котором вершины будут хранить натуральные числа и между двумя вершинами будет ребро, если в исходной пирамидке эти два числа были разделены 1 ребром треугольника. Более того, расположим этот граф определенным образом на плоскости, так, чтобы каждая вершина имела вполне определенные координаты по x и по y.
Получится что-то вроде такого:

Посоветуйте плиз нормальный графический редактор, а то много сил уходит на рисование в paint.

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

Допустим, vert_moves = | row_m – row_n | – это модуль разности номеров строк этих чисел, а hor_moves = | col_m – col_n | – аналогично для столбцов.

Очевидно, что для попадания из вершины с 1-ым числом в вершину со 2-м числом надо сделать как минимум vert_moves ходов. Но этого может оказаться недостаточно. Например, для чисел 27 и 9 – за 5 ходов мы можем попасть из 27 в 5 и надо еще 4 хода, чтобы попасть из 5 в 9.

Некоторые вертикальные ходы будут совмещаться с горизонтальными (в силу структуры графа), например, ходы из 10 в 11, из 17 в 18, из 21 в 22, из 34 в 33 и так далее.

По количеству вертикальных ходов мы можем определить, сколько из них могут быть одновременно и горизонтальными. Если мы идем из вершины с нечетного ряда и в вершину нечетного ряда, то по пути мы сделаем vert_moves/2 горизонтальных ходов (пока не важно, в каком горизонтальном направлении будет каждый из этих шагов).

Такая же ситуация, если идем из вершины четного ряда в вершину четного ряда.

Если путь из вершины нечетного ряда в вершину четного, то количество горизонтальных шагов будет таким же, как в пути из вершины следующего после нечетного ряда (таким образом, четного) в четный. Например, ищем путь из вершины 6 в вершину 17. 6 находится во 3-м ряду, а 17 – в 8-ом.
Тогда кол-во горизонтальных шагов в этом пути такое же, как и из 2 ряда в 8. А это мы уже умеем считать – (8-2)/2 =3 хода.

И, наконец, если путь из вершины четного ряда в вершину нечетного (скажем, из вершины 11 в вершину 23). Тогда кол-во горизонтальных шагов равно пути из предыдущего нечетного ряда в вершину четного. Для вершин 11 и 23 это значит, что кол-во горизонтальных ходов не изменится, если вместо вершины 11 взять вершину 5, 7 или 9.

Итак, теперь мы знаем количество горизонтальных и вертикальных шагов, которые мы должны сделать и так же количество горизонтальных ходов, которые можем сделать, пока будем делать вертикальные ходы. Пусть это будет may_hor.
Если may_hor<hor_moves, то придется сделать дополнительно hor_moves-may_hor ходов, а ответ будет vert_moves + hor_moves – may_hor.

Теперь о том, как вычислить координаты числа x.
Нетрудно заметить, что если число является полным квадратом, то его координата x – это sqrt(x)-1 (номер столбца), а координата y – это (sqrt(x)+2)/2 (номер строки).
Если число не является полным квадратом, то найдем для него ближайшее большее число, которое является полным квадратом, пусть это будет sq. Если четности числа и sq совпадают, то они находятся в одной строке. Если не совпадают, то строка для числа на 1 меньше, чем строка для sq.
Столбец для числа считается просто – это столбец для sq минус разницу между числом и квадратом.
Т.е. col_number = col_sq – (sq – number).

Вот, в принципе и все. Но есть одно НО. Я получил.. нет, не Wrong Answer и не TLE, а Compilation Error! o_O
У меня, правда, все компилировалось (gnu gcc compiler). Ошибка была связана вот с чем:

long x;
double t = (long)sqrt(x);

Компилятор не знал, какую из sqrt выбрать – sqrt(float), sqrt(double) или sqrt(long double).

Ну и напоследок программа, которая получает Accepted:

//file main.cpp, task 1302
#include <iostream>
#include <math.h>
void find_coords(long x, long &x_col, long &x_row)
{
    // ищем наименьшее число, большее либо равное x, являющееся полным квадратом
    double t = (long)sqrt((double)x);
    long sq = t*t;
    long sq_less = (t-1)*(t-1);
    if (sq < x)
    {
        t++;
        sq = t*t;
        sq_less = (t-1)*(t-1);
    }
    // ищем номер строки, в которой будет находиться x
    x_row = (t-1)*2;
    if (x%2 != sq%2)
        x_row--;
    long sq_col = t-1; // столбец, в котором будет находиться sq
    x_col = sq_col + x - sq; // столбец, в котором будет находиться x
}

// сколько ходов в сторону можем сделать, добираясь со строки row1 в row2
long may_hor_moves(long row1, long row2)
{
    if (row2<row1) return may_hor_moves(row2, row1);
    if (row1%2 == row2%2)
        return (row2-row1)/2;
    if (row1%2==1)
        return (row2-row1+1)/2;
    return (row2-row1-1)/2;
}

int main()
{
    long N, M, col_m, row_m, col_n, row_n;

    std::cin >> N >> M;

    if (N>M)
    {
        long t = N;
        N = M;
        M = t;
    }

    find_coords(N,col_n,row_n);
    find_coords(M,col_m,row_m);

    long vert_moves = abs(row_n - row_m);
    long hor_moves  = abs(col_n - col_m);
    long add_moves = may_hor_moves(row_n, row_m);

    long ans = vert_moves;
    if (hor_moves > add_moves)
        ans += (hor_moves - add_moves);

    std::cout << ans << std::endl;
    return 0;
}

Accepted, время работы 0.015, используемая память 217 КБ.