Bad Checker Detected#12823

Bad Checker Detected (Editorial)

Софія Мельник

Для розв'язання задачі варто перебрати усі і перевірити для цього чи відстань до найближчого щасливого числа ліворуч рівна відстані до найближчого щасливого числа праворуч.

При цьому, для швидкого знаходження щасливих чисел ліворуч та праворуч, будемо підтримувати ці два числа в змінних та . При збільшенні на будемо змінювати та . Якщо число – щасливе, тоді в потрібно записати , оскільки на цей момент це буде найближче щасливе число ліворуч. Також якщо – щасливе, то при переході до X+1 потрібно знайти нове найближче щасливе число праворуч. Для цього можна здвигати поки воно не стане щасливим. Оскільки буде тільки збільшуватись, отримаємо лінійне рішення.

Для того, аби швидко перевірити чи число є щасливим, можна використати математичні формули для знаходження кожної цифри в числі, а потім взяти суму перших трьох та останніх трьох і зрівняти їх.