Разбор задачи «Кристаллические наборы»

Краткая формулировка

Для каждого числа n нужно определить, можно ли представить его в виде суммы нескольких наборов размера 11 и 111.

Иначе говоря, требуется понять, существуют ли неотрицательные целые числа a и b, такие что:

n = 111 * a + 11 * b

где:

• a — количество наборов по 111,
• b — количество наборов по 11.

Наблюдение

Наивная идея — перебирать все возможные количества наборов по 111:

• взяли 0 таких наборов,
• взяли 1,
• взяли 2,
• и так далее.

После этого проверять, можно ли остаток добрать наборами по 11.

То есть проверять:

• для каждого a посчитать n - 111 * a;
• если остаток неотрицателен и делится на 11, то ответ YES.

Это уже почти решение.

Но возникает вопрос: сколько значений a нужно проверять?

Если проверять слишком много, решение будет медленным или просто некрасивым.

Главное упрощение

Заметим, что:

111 = 11 * 10 + 1

Значит,

111 ≡ 1 (mod 11)

Теперь посмотрим на равенство:

n = 111 * a + 11 * b

Перенесём вторую часть:

n - 111 * a = 11 * b

Правая часть делится на 11, значит и левая тоже должна делиться на 11.

То есть нужно, чтобы:

n - 111 * a ≡ 0 (mod 11)

Но так как 111 ≡ 1 (mod 11), получаем:

n - a ≡ 0 (mod 11)

или

a ≡ n (mod 11)

Это очень важный вывод.

Он означает, что поведение полностью определяется остатком a по модулю 11.

Следовательно, достаточно перебрать только:

a = 0, 1, 2, ..., 10

Если среди этих значений нашлось подходящее, ответ YES. Если нет — NO.

Почему этого действительно достаточно

Предположим, что существует какое-то большое подходящее значение a.

Тогда его остаток по модулю 11 равен одному из чисел от 0 до 10.

То есть:

a = 11 * k + r, где 0 <= r <= 10

Тогда:

111 * a = 111 * (11 * k + r)

111 * a = 1221 * k + 111 * r

Число 1221 делится на 11, значит часть 1221 * k можно компенсировать наборами по 11.

Поэтому достаточно проверить только остаток r, то есть одно из значений от 0 до 10.

Алгоритм

Для каждого теста:

1. Перебираем количество наборов по 111 от 0 до 10.
2. Считаем остаток: rest = n - 111 * a

3. Если:

   • rest >= 0, и
   • rest % 11 == 0, то выводим YES.
4. Если ни одно значение не подошло, выводим NO.

Разбор на примерах

Пример 1: n = 33

Пробуем a = 0:

rest = 33 - 111 * 0 = 33

33 % 11 == 0, значит:

33 = 11 + 11 + 11

Ответ: YES.

Пример 2: n = 144

Пробуем a = 1:

rest = 144 - 111 = 33

33 % 11 == 0, значит:

144 = 111 + 11 + 11 + 11

Ответ: YES.

Пример 3: n = 69

Проверяем a = 0..10. Ни в одном случае остаток не получается одновременно неотрицательным и кратным 11.

Ответ: NO.

Пример 4: n = 1001

Пробуем a = 8:

rest = 1001 - 888 = 113

113 не делится на 11.

Пробуем дальше. При a = 9:

rest = 1001 - 999 = 2

тоже не подходит.

Но при a = 0:

1001 % 11 == 0

потому что:

1001 = 11 * 91

Значит ответ: YES.

Почему не нужен полный перебор

Может показаться, что надо перебирать все a до n / 111.

Но n может быть большим, и это лишняя работа. Нам помогает арифметика по модулю:

• проверок всегда только 11;
• значит решение для каждого теста работает за константное время.

Это и делает решение очень быстрым.

Типичные ошибки

Ошибка 1. Перебирать слишком много значений

Некоторые решения делают цикл до n / 111.

Такой код тоже может пройти, потому что ограничения здесь не слишком жёсткие, но это менее аккуратное решение. Методически лучше показать идею с модулем 11.

Ошибка 2. Забыть проверить rest >= 0

Если просто писать:

if ((n - 111 * a) % 11 == 0)

то можно случайно принять отрицательный остаток как допустимый.

Нужно обязательно проверять, что остаток неотрицательный.

Ошибка 3. Пытаться искать сложную формулу

На самом деле задача решается очень коротко:

• небольшой перебор,
• проверка делимости.

Чем проще решение здесь, тем лучше.

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

Докажем, что алгоритм работает правильно.

Нужно определить, существуют ли неотрицательные целые a и b, такие что:

n = 111 * a + 11 * b

Алгоритм перебирает все a от 0 до 10 и проверяет, делится ли n - 111 * a на 11 и неотрицательно ли это значение.

1. Если алгоритм вывел YES, то представление существует

Если для некоторого a выполнено:

• rest = n - 111 * a >= 0,
• rest % 11 == 0,

то существует целое неотрицательное число

b = rest / 11.

Тогда:

n = 111 * a + 11 * b

Значит число действительно можно представить нужным образом.

2. Если представление существует, то алгоритм найдёт его

Пусть существуют неотрицательные a и b, такие что:

n = 111 * a + 11 * b

Рассмотрим a по модулю 11:

a = 11 * k + r, где 0 <= r <= 10

Тогда:

111 * a = 111 * (11 * k + r) = 1221 * k + 111 * r

Так как 1221 = 11 * 111, число 1221 * k делится на 11. Значит часть, соответствующую 1221 * k, можно перенести в количество наборов по 11.

Следовательно, если представление существует, то существует и представление с некоторым r от 0 до 10.

Именно эти значения алгоритм и перебирает.

Значит, если ответ существует, алгоритм обязательно найдёт подходящий вариант.

Из пунктов 1 и 2 следует, что алгоритм корректен.

Сложность

Для каждого теста выполняется не более 11 проверок.

Время

O(11), то есть O(1) на один тест.

Память

O(1).

Эталонная реализация на C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;

        bool ok = false;
        for (int a = 0; a <= 10; ++a) {
            int rest = n - 111 * a;
            if (rest >= 0 && rest % 11 == 0) {
                ok = true;
                break;
            }
        }

        cout << (ok ? "YES" : "NO") << '\n';
    }

    return 0;
}

Эталонная реализация на Python

t = int(input())

for _ in range(t):
    n = int(input())
    ok = False

    for a in range(11):
        rest = n - 111 * a
        if rest >= 0 and rest % 11 == 0:
            ok = True
            break

    if ok:
        print("YES")
    else:
        print("NO")

Ещё более короткая идея

Есть и популярное наблюдение:

• все числа n >= 1110 точно дают ответ YES,
• потому что можно подобрать нужное количество 111, а остальное добрать 11.

Но для обучения и методического разбора перебор a от 0 до 10 обычно лучше:

• он проще доказывается,
• проще программируется,
• понятнее новичкам.

Вывод

В этой задаче главное — заметить связь числа 111 с модулем 11:

111 ≡ 1 (mod 11)

После этого задача превращается в очень маленький перебор всего из 11 вариантов.

Это хороший пример того, как одно короткое арифметическое наблюдение полностью упр