Вася и желание

В данной статье мы подробно разберем популярную алгоритмическую задачу, в которой нужно определить, загадает ли Вася желание, основываясь на свойствах цифр трехзначного числа; Задача является классическим примером проверки условий делимости и работы с цифрами числа․

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

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

Входные данные: Три целых числа a, b, c (цифры от 0 до 9)․

Выходные данные: Слово «да», если Вася загадает желание, и «нет» в противном случае․

Примеры

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

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

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

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

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

Нам нужно проверить, существует ли пара, сумма остатков которой равна 0 или 3 (то есть 0 по модулю 3)․

Возможные выигрышные комбинации остатков:

• Два нуля (0, 0): 0 + 0 = 0 → делится на 3․
• Единица и двойка (1, 2): 1 + 2 = 3 → делится на 3․

Следовательно, Вася загадает желание («да») в двух случаях:

1. Среди цифр есть хотя бы две, которые делятся на 3 (остаток 0)․ Цифры: 0, 3, 6, 9․
2. Среди цифр есть хотя бы одна с остатком 1 (цифры: 1, 4, 7) И хотя бы одна с остатком 2 (цифры: 2, 5, 8)․

Во всех остальных случаях ответ — «нет»․

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

1. Считать три целых числа a, b, c․
2. Посчитать количество чисел, дающих остаток 0, 1 и 2 при делении на 3․
   • cnt0 — количество чисел с остатком 0․
   • cnt1 — количество чисел с остатком 1․
   • cnt2, количество чисел с остатком 2․
3. Проверить условие: (cnt0 >= 2) OR (cnt1 >= 1 AND cnt2 >= 1)․
4. Если условие истинно — вывести «да», иначе — «нет»․

Альтернативный (наивный) алгоритм, просто проверить три суммы напрямую․ Для трех чисел это абсолютно допустимо и работает за O(1)․

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

���� Примеры реализации на популярных языках

Python 3

def solve:
 # Считываем три числа из одной строки
 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 <iostream>
using namespace std;

int main {
 // Ускорение ввода/вывода
 ios_base::sync_with_stdio(false);
 cin․tie(NULL);
 
 int a, b, c;
 if (cin >> a >> b >> c) {
 // Проверка через остатки (оптимизированный вариант)
 int cnt[3] = {0, 0, 0};
 cnt[a % 3]++;
 cnt[b % 3]++;
 cnt[c % 3]++;
 
 if (cnt[0] >= 2 || (cnt[1] >= 1 && cnt[2] >= 1)) {
 cout << "да" << endl;
 } else {
 cout << "нет" << endl;
 }
 }
 return 0;
}

Java (Java 11+)

import java․util․Scanner;

public class Main {
 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', (line) => {
 const [a, b, c] = line․split(' ')․map(Number);
 
 if ((a + b) % 3 === 0 || (b + c) % 3 === 0 || (a + c) % 3 === 0) {
 console․log("да");
 } else {
 console․log("нет");
 }
 rl․close;
});

���� Тестирование граничных случаев

При сдаче задачи на автоматическую проверку (Codeforces, AtCoder, Acmp, Informatics и др․) важно проверить крайние значения:

• Все нули: 0 0 0 → да (0+0=0 делится на 3)․
• Максимальные цифры: 9 9 9 → да (9+9=18)․
• Смешанные остатки (1, 1, 1): 1 4 7 → нет (1+1=2, не делится на 3)․
• Смешанные остатки (2, 2, 2): 2 5 8 → нет (2+2=4, не делится на 3)․
• Классический «да» через 1 и 2: 1 2 0 → да (1+2=3)․
• Классический «да» через два нуля: 3 6 1 → да (3+6=9)․

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

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

Оба подхода (прямая проверка сумм и подсчет остатков) идеально укладываются в любые ограничения по времени (обычно 1-2 секунды) и памяти (256-512 МБ)․

���� Типичные ошибки и советы

1. Чтение ввода: Если числа даны в одной строке через пробел, используйте split (Python/JS) или последовательный cin >> a >> b >> c (C++)․ Если каждое число на новой строке, эти же методы сработают корректно․
2. Тип данных: Цифры от 0 до 9 идеально помещаются в int (32 бита)․ Переполнение невозможно․
3. Логическая ошибка: Проверка (a+b+c) % 3 == 0 — это другая задача (делится ли само число на 3)․ Нам нужно именно попарное сложение․

Задача «Вася любит математику и верит в приметы» — это отличная разминочная задача для начинающих программистов; Она тренирует:

• Базовый ввод/вывод․
• Работу с оператором остатка от деления (%)․
• Написание составных логических условий (||, &&)․
• Умение переводить словесное условие в формальный алгоритм․

Главный вывод: Для решения достаточно проверить три попарные суммы напрямую․ Это самый понятный, надежный и достаточно быстрый способ․ Анализ через остатки (подсчет cnt0, cnt1, cnt2) полезен для понимания математической структуры задачи и может пригодиться в более сложных вариациях (например, если цифр не 3, а N)․

Удачной отправки решения! ���