Стежитимемо не за самими позиціями, а за відстанню між Алісою та Бобом. Спочатку вона дорівнює d = N - 1.
Щосекунди Аліса зсувається на або бокси назустріч Бобу, а Боб — на або бокси назустріч Алісі. Отже, за одну секунду відстань зменшується на
— тобто на будь-яке число від до включно.
Роботи опиняться в одному боксі, коли відстань стане рівно нулем. Якщо на це витрачено секунд, то сумарне зменшення дорівнює , причому кожен доданок лежить між і . Тому
Ця умова не лише необхідна, а й достатня: будь-яке значення від до можна набрати, бо доданки змінюються з кроком одиниця (наприклад, узявши кілька п'ятірок, потім за потреби одну четвірку, а решту — трійками).
Ми шукаємо мінімальне , тому беремо найменше , для якого d \le 5t, тобто
і перевіряємо другу нерівність 3t \le d. Якщо вона виконується — це відповідь; якщо ні, то не підійде і жодне більше (зі зростанням ліва межа лише віддаляється від ), тому виводимо .
Розв'язок працює за , що важливо при N \le 10^9. Перевірте себе на N = 2: тут d = 1, t = 1, але 3 > 1, отже відповідь .