Проверка делимости попарных сумм трех цифр на 3

Содержание

• Условие задачи
• Математический анализ (делимость на 3)
• Алгоритм решения
• Доказательство корректности
• Оценка сложности
• Реализация (Python)
• Примеры ввода‑вывода

Условие задачи

Вася любит математику и верит в собственные «приметы». Когда он видит номер машины,
квартиры или любой трехзначный номер, он берёт его цифры a, b и c
и вычисляет три попарные суммы:

• a + b
• b + c
• a + c

Если хотя бы одна из этих сумм делится на 3, то Вася загадывает желание.
Даны три целых числа a, b и c (каждое от 0 до 9). Нужно
определить, загадает ли Вася желание. Вывести слово «да», если условие выполнено,
и «нет» в противном случае.

Формат ввода

a b c

Формат вывода

да // если хотя бы одна из сумм делится на 3
нет // иначе

Математический анализ (делимость на 3)

Ключевой факт: число делится на 3 тогда и только тогда, когда сумма его цифр делится на 3.
Для попарных сумм это значит, что нам достаточно проверить остатки от деления
каждой суммы на 3.

Обозначим:

• s1 = (a + b) mod 3
• s2 = (b + c) mod 3
• s3 = (a + c) mod 3

Если s1 = 0 или s2 = 0 или s3 = 0, то ответ «да».
Иначе – «нет».

Поскольку a, b, c ≤ 9, вычисления выполняются за константное время.

Алгоритм решения

1. Прочитать три целых числа a, b, c.
2. Вычислить три попарные суммы: a+b, b+c, a+c.
3. Для каждой суммы проверить условие sum % 3 == 0.
4. Если условие истинно хотя бы для одной суммы – вывести «да», иначе – вывести «нет».

Доказательство корректности

Теорема. Алгоритм выводит «да» тогда и только тогда, когда хотя бы одна из
попарных сумм цифр делится на 3.

Доказательство.

• Если часть алгоритма выводит «да». Это происходит только в случае,
  когда найдено хотя бы одно из условий (a+b) % 3 == 0,
  (b+c) % 3 == 0 или (a+c) % 3 == 0. По определению делимости
  на 3 это эквивалентно тому, что соответствующая сумма делится на 3.
  Следовательно, условие задачи выполнено.
• Если условие задачи выполнено. По условию существует пара цифр,
  сумма которых кратна 3. Алгоритм проверяет все три возможные пары, поэтому
  он обязательно обнаружит эту пару и выведет «да».

Таким образом, алгоритм корректен.

Оценка сложности

Время выполнения: O(1) – фиксированное количество арифметических операций.

Память: O(1) – несколько целочисленных переменных.

Реализация (Python 3)

#!/usr/bin/env python3
import sys

def main -> None:
 data = sys.stdin.read.strip.split
 if len(data) != 3:
 return
 a, b, c = map(int, data)
 # проверяем три попарные суммы
 if (a + b) % 3 == 0 or (b + c) % 3 == 0 or (a + c) % 3 == 0:
 print("да")
 else:
 print("нет")

if __name__ == "__main__":
 main

Код полностью соответствует описанному алгоритму и проходит все тесты.

Примеры ввода‑вывода

1 2 3

да

4 7 2

да

5 1 4

да

2 2 2

нет

Задача иллюстрирует простую, но часто встречающуюся в конкурсных
программированиях технику работы с остатками от деления. Благодаря свойству
делимости на 3, достаточно лишь проверить три фиксированных суммы,
что позволяет решить задачу за константное время и память.

Если у вас возникли вопросы или вы хотите обсудить варианты оптимизации
(например, использовать только остатки от деления входных цифр), пишите
в комментариях – будем рады помочь!

Контактная информация

Если необходимо связаться с автором статьи, используйте форму обратной связи
на сайте или напишите на почту
support@example.com.