Баланс кода в игровом терминале
Условие
В аркадной игре стоит старый терминал: чтобы открыть дверь в следующий уровень, он считает баланс кода.
Терминал смотрит на цифры кода справа налево (с последней цифры), нумерует их позициями 1, 2, 3, ...
- цифры на нечётных позициях он прибавляет,
- цифры на чётных позициях он вычитает.
Получившееся число и есть баланс.
Важно: код может быть очень большим (как на олимпиадах): до 10^18, то есть не помещаться в 32-битный тип.
Формат ввода
Одно целое число X.
Формат вывода
Выведите одно целое число — баланс кода.
Ограничения
0 ≤ X ≤ 10^18.
Пример
Ввод:
50724
Вывод:
14
Пояснение: справа налево цифры 4, 2, 7, 0, 5 → 4 − 2 + 7 − 0 + 5 = 14.
Как решать — идея подхода
Приём: Обход цифр справа налево (mod/div) + чередующийся знак
Ключевое наблюдение: терминал нумерует позиции от последней цифры, значит удобнее разбирать число справа налево. Тогда каждая следующая взятая цифра просто меняет знак: + - + - ....
Почему работает приём с x % 10 и x //= 10: это стандартный способ «снять» последнюю цифру и убрать её из числа, не храня число как массив. Ограничение до 10^18 легко помещается в 64-бит, а в Python вообще нет проблем.
План решения:
- Прочитай
X. - Заведи
balance = 0и номер позицииpos = 1(это позиция последней цифры). - Пока
X > 0: d = X % 10— последняя цифра.- если
posнечётная, добавьd, иначе вычтиd. X //= 10,pos += 1.- Отдельно учти случай
X == 0: у него одна цифра 0 на позиции 1, баланс равен 0.
Мини-сниппет для знака:
balance += d if pos % 2 == 1 else -d
Сложность: O(k), где k — число цифр (для 10^18 максимум 19), память O(1).
Частая ошибка: нумеровать позиции слева направо (по строке) — тогда знаки будут перепутаны, потому что терминал считает от конца.
Разберись руками
Терминал берёт код 50724 и смотрит на цифры справа налево. Первую справа он прибавляет, вторую вычитает, третью снова прибавляет и так далее. Давай руками разложим цифры на «плюс» и «минус» и получим баланс 14.
- Возьми строку "50724". Отсчитывай позиции СПРАВА налево: последняя цифра — позиция 1, предыдущая — позиция 2, и т.д. Отметь индексы (с 0) тех цифр, которые окажутся на НЕЧЁТНЫХ позициях (их будем прибавлять).
- Теперь сложи цифры, которые мы прибавляем: это 5, 7 и 4. Чему равна их сумма?
- Сложи цифры, которые вычитаем (чётные позиции справа налево): это 0 и 2. Чему равна их сумма?
- Финальный баланс для примера: из «плюсовой» суммы 16 вычти «минусовую» сумму 2. Сколько получится?
Идея: Идём по цифрам справа налево, считая позиции 1, 2, 3… Цифры на нечётных позициях складываем в одну сумму, на чётных — в другую, а потом из первой вычитаем вторую: так и получается баланс.
Решить задачу с автопроверкой на Python →
Куда дальше
- С нуля до олимпиады: маршрут — сколько занимает язык, какие приёмы нужны и к какому этапу это ведёт
- Родителям: подготовка бесплатно — сколько стоит репетитор, что даёт бесплатный маршрут и как понять, что ребёнок занимается
- Школьный этап ВсОШ по информатике — как устроен первый этап и план подготовки за четыре недели