Вася и попарные суммы — проверка делимости на 3

В задаче из Яндекс‑учебника описывается интересная привычка вымышленного персонажа Васи․ Он смотрит на трёхзначный номер (например, номер машины или квартиры), разбивает его на цифры a, b, c и считает три попарные суммы:

• S₁ = a + b
• S₂ = b + c
• S₃ = a + c

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

Почему достаточно проверять только попарные суммы?

Делимость на 3 имеет хорошо известное свойство: число делится на 3 тогда и только тогда, когда сумма его цифр делится на 3․ В нашем случае мы не проверяем само трёхзначное число, а рассматриваем суммы пар цифр․ Если любая из этих сумм кратна 3, то условие задачи выполнено․

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

1. Считаем три числа a, b, c․
2. Вычисляем три суммы: a+b, b+c, a+c․
3. Проверяем, делится ли хотя бы одна из них на 3 (остаток от деления равен 0)․
4. Если да – выводим «да», иначе – «нет»․

Время работы алгоритма – O(1), так как выполняется фиксированное количество арифметических операций․ Память также постоянна․

Примеры

Личный приём: как быстро решить в уме

Если вы решаете задачу без бумаги, полезно запомнить следующее наблюдение:

• Сумма двух цифр делится на 3, если остатки этих цифр при делении на 3 в сумме дают 0 или 3․
• Остатки цифр от деления на 3 могут быть только 0, 1 или 2․
• Поэтому достаточно посмотреть на остатки a%3, b%3, c%3 и проверить, есть ли среди пар (a%3 + b%3), (b%3 + c%3), (a%3 + c%3) сумма, равная 0 или 3․

Это избавляет от лишних сложений и позволяет решить задачу за пару секунд․

Реализация на популярных языках (псевдокод)

Ниже представлен простой псевдокод, который легко перевести на любой язык программирования․

function vasyaWish(a, b, c):
 if ( (a+b) % 3 == 0 ) or ( (b+c) % 3 == 0 ) or ( (a+c) % 3 == 0 ):
 return "да"
 else:
 return "нет"

На Python:

def vasya_wish(a, b, c):
 if (a+b) % 3 == 0 or (b+c) % 3 == 0 or (a+c) % 3 == 0:
 return "да"
 return "нет"

print(vasya_wish(2,2,2)) # нет
print(vasya_wish(1,2,3)) # да

На C++:

#include <iostream>
using namespace std;

string vasyaWish(int a, int b, int c) {
 if ((a+b)%3==0 || (b+c)%3==0 || (a+c)%3==0)
 return "да";
 return "нет";
}

int main {
 int a,b,c; cin >> a >> b >> c;
 cout << vasyaWish(a,b,c) << endl;
 return 0;
}

Задача про Васю – отличный пример того, как простое свойство делимости на 3 позволяет быстро решить, понадобится ли загадывать желание․ Достаточно вычислить три попарные суммы и проверить их на кратность трём․ Алгоритм работает за постоянное время и не требует сложных структур данных․

Теперь вы можете смело отвечать на подобные вопросы в тестах, собеседованиях или просто впечатлять друзей своей быстрой сообразительностью!