Телекінез#354

Телекінез (Розбір)

Треба зрозуміти, на якому місці у вежі опиниться кубик з номером — саме це число і буде висотою вежі в момент його встановлення.

Спочатку Аліса ставить усі непарні кубики за зростанням: 1, 3, 5, \ldots, а потім Боб ставить усі парні: 2, 4, 6, \ldots

Розглянемо два випадки.

Якщо непарне, то воно потрапляє в першу частину. Перед ним стоять непарні числа 1, 3, \ldots, K-2, тобто \frac{K-1}{2} штук. Отже, висота дорівнює

\frac{K-1}{2} + 1.

Якщо парне, то перед ним стоїть уся перша частина плюс менші парні числа. Непарних чисел серед рівно , а парних, менших за , — рівно \frac{K}{2} - 1. Тому висота дорівнює

\left\lceil \frac{N}{2} \right\rceil + \frac{K}{2}.

Перевіримо на прикладі з умови: N = 10, K = 7 дає \frac{6}{2} + 1 = 4; N = 10, K = 6 дає 5 + 3 = 8. Обидва збігаються з відповіддю в умові.

Найлегше помилитися саме в : при непарному непарних кубиків на один більше, ніж парних.