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

В данной статье мы подробно разберем интересную алгоритмическую задачу, которая сочетает в себе элементарную арифметику, теорию чисел (делимость) и базовую логику программирования. Задача представлена в формате «личный прием» — это значит, что она может быть частью собеседования, олимпиады или учебного курса по основам кодинга.

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

Представим себе персонажа по имени Вася. Он любит математику, но при этом верит в приметы — причем в те, которые придумывает сам.

Суть приметы: Когда Вася видит номер машины или квартиры, состоящий из трёх цифр, он выполняет следующий ритуал:

1. Обозначает цифры как a, b, c.
2. Складывает их попарно: a + b, b + c, a + c.
3. Проверяет полученные суммы: если хотя бы одна из них делится на 3 нацело, Вася загадывает желание.

Входные данные: Три целых числа (цифры от 0 до 9).
Выходные данные: Слово ДА (если желание загадывается) или НЕТ (в противном случае).

🧠 Математический анализ и логика решения

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

Свойство делимости суммы

Сумма двух чисел делится на 3 тогда и только тогда, когда сумма их остатков от деления на 3 делится на 3.

Пусть r_a = a % 3, r_b = b % 3, r_c = c % 3. Остатки могут быть только 0, 1 или 2.

Разбор случаев (по остаткам)

Нам нужно, чтобы хотя бы одна из пар (a,b), (b,c), (a,c) давала в сумме остаток 0.

• Случай 1: Есть хотя бы две цифры с одинаковым остатком 0. (Например, 0 и 3, 3 и 6, 0 и 6). Их сумма делится на 3. Ответ: ДА.
• Случай 2: Есть цифра с остатком 1 и цифра с остатком 2. Сумма 1 + 2 = 3 делится на 3. Ответ: ДА.
• Случай 3: Все три цифры имеют одинаковый остаток 1. (Например, 1, 4, 7). Любая пара дает сумму с остатком 2. Ответ: НЕТ.
• Случай 4: Все три цифры имеют одинаковый остаток 2. (Например, 2, 5, 8). Любая пара дает сумму с остатком 1 (4 % 3 = 1). Ответ: НЕТ.

1. Все три числа дают остаток 1 при делении на 3;
2. Все три числа дают остаток 2 при делении на 3.

Во всех остальных случаях ответ, ДА.

💻 Реализация на популярных языках программирования

Ниже приведены готовые решения. Мы покажем как «наивный» вариант (прямое выполнение условий), так и оптимизированный (через анализ остатков).

Python 3

Вариант 1: Прямой (читаемый, идеален для обучения)

def vasya_wish(a, b, c):
 # Вычисляем попарные суммы
 sum1 = a + b
 sum2 = b + c

 sum3 = a + c
 
 # Проверяем делимость на 3
 if sum1 % 3 == 0 or sum2 % 3 == 0 or sum3 % 3 == 0:
 return "ДА"
 else:
 return "НЕТ"

a, b, c = map(int, input.split)
print(vasya_wish(a, b, c))

Вариант 2: Оптимизированный (математический)

def vasya_wish_fast(a, b, c):
 # Считаем остатки от деления на 3
 r = [a % 3, b % 3, c % 3]
 
 # Если все остатки равны 1 или все равны 2 -> НЕТ
 if r == [1, 1, 1] or r == [2, 2, 2]:
 return "НЕТ"
 return "ДА"

def vasya_wish_set(a, b, c):
 remainders = {a % 3, b % 3, c % 3}
 # Если множество остатков равно {1} или {2} -> НЕТ
 if remainders == {1} or remainders == {2}:
 return "НЕТ"
 return "ДА"

a, b, c = map(int, input.split)
print(vasya_wish_fast(a, b, c))

C++ (GNU C++17)

#include <iostream>
using namespace std;

int main {
 ios_base::sync_with_stdio(false);
 cin.tie(NULL);
  int a, b, c;
 if (!(cin >> a >> b >> c)) return 0;
  // Наивный подход
 if ((a + b) % 3 == 0 || (b + c) % 3 == 0 || (a + c) % 3 == 0) {
 cout << "ДА" << endl;
 } else {
 cout << "НЕТ" << endl;
 } return 0;
}

JavaScript (Node.js / Browser)

const readline = require('readline');

const rl = readline.createInterface({
 input: process.stdin,
 output: process.stdout
});

rl.on('line', (line) => {
 const [a, b, c] = line.split(' ').map(Number);
 
 // Проверка через остатки (оптимально)
 const r1 = a % 3, r2 = b % 3, r3 = c % 3;
 
 // Условие "НЕТ": все остатки 1 ИЛИ все остатки 2
 const isNo = (r1 === 1 && r2 === 1 && r3 === 1) || (r1 === 2 && r2 === 2 && r3 === 2);
 
 console.log(isNo ? "НЕТ" : "ДА");
 rl.close;
});

Pascal (Free Pascal / PascalABC.NET)

program VasyaWish;
var a, b, c: integer;
begin
 readln(a, b, c);
 
 { Прямая проверка сумм }
 if ((a + b) mod 3 = 0) or ((b + c) mod 3 = 0) or ((a + c) mod 3 = 0) then
 writeln('ДА')
 else
 writeln('НЕТ');
end.

🧪 Тестовые примеры (Test Cases)

Для проверки корректности решения рекомендуется прогнать следующие наборы данных:

⚡ Сложность алгоритма

• Временная сложность: O(1) — выполняется фиксированное количество арифметических операций (3 сложения, 3 взятия остатка или 3 проверки сумм), не зависящее от входных данных.
• Пространственная сложность: O(1) — используется константное количество памяти для хранения 3-х чисел и нескольких переменных.

Оба подхода (наивный и математический) имеют одинаковую асимптотику, однако математический подход выполняет меньше операций (нет сложения больших чисел, только взятие остатка), что теоретически немного быстрее, хотя на практике для 3 чисел разница не измерима.

🎯 Типичные ошибки и подводные камни

1. Неправильный ввод: Чтение чисел как одной строки без разделения (например, 123 вместо 1 2 3). В условии сказано «Даны три числа», обычно это подразумевает разделение пробелом или переносом строки. Если ввод именно трехзначное число, его нужно разбить на цифры: a = n // 100, b = n // 10 % 10, c = n % 10.
2. Регистр вывода: Системы автоматической проверки (Codeforces, AtCoder, Яндекс.Контест, Stepik) чувствительны к регистру. Нужно выводить строго ДА и НЕТ (заглавными кириллическими буквами), без лишних пробелов, точек или кавычек.
3. Игнорирование нуля: Новички иногда забывают, что 0 делится на 3. Если в номере есть 0, это часто гарантирует ответ «ДА» (если есть еще одна цифра, делящаяся на 3, или пара 1 и 2).
4. Логическая ошибка в оптимизации: Написание условия «НЕТ» как if (r1 == r2 && r2 == r3) — это неверно, так как при остатках 0, 0, 0 ответ должен быть «ДА». Правильно: if ((r1 == 1 && r2 == 1 && r3 == 1) || (r1 == 2 && r2 == 2 && r3 == 2)).

📚 Обобщение задачи (для любопытных)

Как изменится задача, если:

• Цифр N штук (N > 3)? Нам нужно найти, есть ли хотя бы одна пара с суммой, делящейся на 3. Это решается подсчетом количества чисел с остатками 0, 1, 2. Ответ «ДА», если: count[0] >= 2 ИЛИ (count[1] >= 1 и count[2] >= 1). Иначе «НЕТ».
• Делитель не 3, а K? Аналогично: считаем остатки по модулю K. Ищем пары (r, K-r) или две штуки остатка 0 (и K/2 если K четное).
• Нужно найти количество таких пар? Тогда используем комбинаторику: C(count[0], 2) + count[1]*count[2] + (K%2==0 ? C(count[K/2], 2) : 0).

Задача «Приметы Васи» — это прекрасный пример того, как математическое мышление упрощает программирование. Прямое моделирование процесса (наивный алгоритм) полностью корректно и достаточно быстро для заданных ограничений (3 числа). Однако понимание теории чисел (свойств остатков) позволяет написать код, который:

1. Работает быстрее (меньше операций).
2. Легче обобщается на большие объемы данных (N чисел).
3. Демонстрирует глубокое понимание сути проблемы на собеседовании.

Главное правило: Всегда читайте условие внимательно (формат ввода/вывода, регистр букв) и тестируйте решение на граничных случаях (нули, одинаковые цифры, максимальные цифры 9).

Статья подготовлена в рамках рубрики «Разбор алгоритмических задач». Удачи в решении и загадывании желаний! ✨