Задача Васи и делимость сумм цифр на три

В данной статье мы подробно разберем популярную задачу по программированию, которая часто встречается на олимпиадах для начинающих (например, на Codeforces, Acmp.ru, Timus или в курсах по алгоритмам). Задача кажется простой, но отлично проверяет понимание базовых операций с числами, работы с условиями и модулярной арифметики.

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

Легенда: Вася любит математику и верит в приметы, которые сам же и придумывает. Когда он видит номер машины или квартиры из трёх цифр, он складывает цифры попарно (a+b, b+c, a+c). Если хотя бы одна сумма делится на три, Вася загадывает желание.

Входные данные: Даны три числа (цифры номера).

Выходные данные: Загадает ли Вася желание? Выведите да или нет.

Примеры

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

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

Прямой подход (Brute Force)

Так как цифр всего три (a, b, c), а пар всего три (a+b, b+c, a+c), можно просто вычислить их и проверить:

1. Считаем sum1 = a + b.
2. Считаем sum2 = b + c.
3. Считаем sum3 = a + c.
4. Если sum1 % 3 == 0 ИЛИ sum2 % 3 == 0 ИЛИ sum3 % 3 == 0, выводим «да», иначе «нет».

Сложность: O(1) по времени и памяти. Это абсолютно приемлемо и быстро.

Оптимизация через остатки (Математический подход)

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

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

Нам нужно, чтобы выполнялось хотя бы одно из условий:

• (ra + rb) % 3 == 0
• (rb + rc) % 3 == 0
• (ra + rc) % 3 == 0

Рассмотрим возможные пары остатков, дающие в сумме 0 или 3:

• 0 + 0 = 0 (делится на 3)
• 1 + 2 = 3 (делится на 3)
• 2 + 1 = 3 (делится на 3)

1. Хотя бы две цифры, дающие остаток 0 при делении на 3 (например, 3 и 6, или 0 и 9).
2. Хотя бы одна цифра с остатком 1 И хотя бы одна цифра с остатком 2 (например, 1 и 2, или 4 и 5, или 7 и 8).

Этот подход позволяет не считать суммы явно, а просто посчитать количество остатков 0, 1 и 2.

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

Python 3

def solve:
 # Читаем три целых числа из стандартного ввода
 # input.split разбивает строку по пробелам
 # map(int, ...) преобразует каждую часть в число
 a, b, c = map(int, input.split)
 
 # Прямая проверка трех пар
 if (a + b) % 3 == 0 or (b + c) % 3 == 0 or (a + c) % 3 == 0:
 print("да")
 else:
 print("нет")

if __name__ == "__main__":
 solve

C++ (GNU C++17)

#include 
using namespace std;

int main {
 // Ускорение ввода/вывода
 ios_base::sync_with_stdio(false);
 cin.tie(NULL);
  int a, b, c;
 if (cin >> a >> b >> c) {
 // Проверка условий
 if ((a + b) % 3 == 0 || (b + c) % 3 == 0 || (a + c) % 3 == 0) {
 cout << "да" << endl;
 } else {
 cout << "нет" << endl;
 }
 }
 return 0;
}

Java

import java.util.Scanner;
public class VasyaSigns {
 public static void main(String[] args) {
 Scanner scanner = new Scanner(System.in);
 
 int a = scanner.nextInt;
 int b = scanner.nextInt;
 int c = scanner.nextInt;
 
 if ((a + b) % 3 == 0 || (b + c) % 3 == 0 || (a + c) % 3 == 0) {
 System.out.println("да");
 } else {
 System.out.println("нет");
 }
 
 scanner.close;
 }
}

JavaScript (Node.js)

const readline = require('readline');

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

rl.on('line', (input) => {
 const [a, b, c] = input.split(' ').map(Number);
 
 if ((a + b) % 3 === 0 || (b + c) % 3 === 0 || (a + c) % 3 === 0) {
 console;log("да");
 } else {
 console.log("нет");
 }
 
 rl.close;
});

Расширенная версия: оптимизация через подсчет остатков

Хотя для трех чисел это избыточно, такой подход полезен, если обобщить задачу на N чисел (найти пару, сумма которой делится на 3).

# Python версия с подсчетом остатков
def solve_optimized:
 a, b, c = map(int, input.split)
 
 # Считаем остатки
 rem = [0, 0, 0] # индексы 0, 1, 2
 for x in (a, b, c):
 rem[x % 3] += 1
 
 # Условие 1: есть как минимум два числа с остатком 0
 # Условие 2: есть хотя бы одно с остатком 1 и хотя бы одно с остатком 2
 if rem[0] >= 2 or (rem[1] >= 1 and rem[2] >= 1):
 print("да")
 else:
 print("нет")

Типичные ошибки и граничные случаи (Edge Cases)

• Ввод чисел через пробел vs построчно. Обычно в таких задачах числа даны в одной строке через пробел. Использование input.split (Python) или cin >> a >> b >> c (C++) корректно обрабатывает и пробелы, и переносы строк.
• Отрицательные числа. В условии сказано «цифры номера», значит числа от 0 до 9. Но если на вход подадут отрицательные (например, -1 -2 -3), в Python -1 % 3 == 2, в C++ -1 % 3 == -1. Прямая проверка сумм (a+b)%3==0 работает корректно везде, так как делимость суммы не зависит от знака остатков в конкретном языке. Рекомендация: используйте проверку сумм, а не остатков отдельно, чтобы избежать подводных камней со знаками.
• Регистр вывода. В условии указано «выведи да или нет». Строго следуйте регистру: маленькие буквы, без точек и кавычек.
• Числа больше 9. Если в тестах придут числа > 9 (например, 12, 15, 30), логика «сумма цифр» не сработает, но условие задачи говорит о «номере из трёх цифр». Решаем задачу именно для трех целых чисел.

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

Как протестировать решение локально

Перед отправкой на автоматическую проверку (например, на Codeforces или в контесте) рекомендуется прогнать следующие тесты:

1. Базовый позитивный: 1 2 3 → да
2. Базовый негативный: 1 1 1 → нет
3. Нули: 0 0 0 → да (0 делиться на 3)
4. Пара с остатком 0: 3 6 1 → да (3+6=9)
5. Пара 1 и 2: 4 5 7 → да (4+5=9)
6. Граничные цифры: 9 9 9 → да (9+9=18)
7. Смешанный: 2 2 2 → нет (2+2=4 не делится на 3)

Обобщение задачи (для интересующихся)

Данная задача, частный случай более общей проблемы: «Дан массив из N чисел, найти пару, сумма которой делится на K».

Для K=3 и N=3 мы решили её за O(1). Для общего случая алгоритм:

1. Создаем массив счетчиков остатков cnt[0...K-1].
2. Для каждого числа увеличиваем cnt[x % K].
3. Проверяем пары остатков (i, K-i) для i=1..K/2 и специальный случай i=0 (нужно cnt[0] >= 2) и, если K четное, i=K/2 (нужно cnt[K/2] >= 2).

Сложность общего решения: O(N + K).

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

Для данной конкретной задачи (всего 3 числа) самый простой, читаемый и надежный код — это прямая проверка трех сумм (a+b)%3 == 0 || (b+c)%3 == 0 || (a+c)%3 == 0. Он работает за константное время, не требует дополнительной памяти и минимально подвержен ошибкам реализации.

Контакты и обратная связь

Если у вас остались вопросы по решению, вы нашли ошибку в коде или хотите предложить свою тему для разбора — вы можете связаться со мной следующими способами:

• Email: support@algorithms-guide.example (пример адреса)
• GitHub: github;com/example-user, репозитории с решениями задач.
• Telegram: @algo_help_channel — канал с разборами олимпиадных задач.
• Форма обратной связи: На нашем сайте в разделе «Контакты» доступна форма для отправки сообщения напрямую автору статьи.

Примечание: Контактные данные выше приведены как пример оформления раздела «Как связаться» в статье. Реальные контакты автора данного текста (ИИ) не предусмотрены.