Diagonal Numbers#382

Diagonal Numbers (Editorial)

Автор задачі:

Йосиф Ентін

Задачу підготував:

Павло Цікалишин

Розбір написав:

Костянтин Денисов

Оптимальний порядок перестановки кубиків можна описати наступним чином:

  1. Спочатку правильно складаємо останній стовпчик за n+2 операції:

    1. Перемістимо кубик з першого стовпчика на другий;

    2. Перемістимо кубик з останнього стовпчика на перший;

    3. Далі вже без перешкод за операцій можна буде скласти останній стовпчик, просто переміщаючи кубики , , ..., .

  2. Далі будемо продовжувати складати стовпчики починаючи з кінця, але тепер на складання стовпчика витратимо i+1 операцію, а не i+2, як для останнього стовпчика;

  3. Для складання стовпчика будемо діяти таким чином:

    1. Перемістимо єдиний кубик зі стовпчика на стовпчик i+1 (в попередньому випадку не було такого стовпчика);

    2. Далі за операцій можна буде скласти стовпчик, переміщаючи кубики , , ..., .

  4. Після правильного складання стовпчиків з по перший стовпчик автоматично буде складений, тому додаткові операції на нього не знадобляться.

Тоді сумарно витратимо (n+2)+n+(n-1)+\ldots+3=n+2+\frac{n \cdot (n+1)}{2} - 3=\frac{n^2+3 \cdot n - 2}{2} операцій.