Разбор задачи «Год без повторов»

Идея задачи

Дан год y. Нужно найти первый год, строго больший y, у которого все цифры различны.

Например:

• после 1987 ответ — 2013;
• после 2013 ответ — 2014.

Задача очень хорошо решается простым перебором.

Главное наблюдение

Мы ищем ближайший следующий подходящий год.

Значит, можно:

1. взять y + 1;
2. проверить, все ли цифры в нём различны;
3. если нет — перейти к следующему году;
4. как только нашли подходящий — вывести его.

Почему этого достаточно? Потому что мы идём по годам по порядку, и первый найденный подходящий год автоматически будет ближайшим.

Как проверять год

Нужно понять, все ли цифры года попарно различны.

Есть несколько способов:

• перевести число в строку и сравнить символы;
• разложить число на цифры арифметически;
• использовать множество (set).

Для обучения удобно показать два основных подхода:

• в C++ — разложение на цифры;
• в Python — проверку через строку.

Проверка на примере

Пусть дан год:

1987

Пробуем следующий год:

• 1988 → цифра 8 повторяется, не подходит;
• 1989 → цифра 9 повторяется? Нет, но 1, 9, 8, 9 — две девятки, не подходит;
• ...
• 2013 → цифры 2, 0, 1, 3, все различны.

Ответ: 2013.

Алгоритм

1. Считать y.
2. Увеличить его на 1.

3. Пока цифры года не являются попарно различными:

   • увеличить y на 1.
4. Вывести y.

Почему алгоритм корректен

Докажем это строго.

Мы последовательно перебираем все годы:

y + 1, y + 2, y + 3, ...

Для каждого года проверяем, удовлетворяет ли он условию: все цифры различны.

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

Так как перебор идёт в порядке возрастания, то:

• все годы меньше найденного уже были проверены;
• среди них не было подходящих;
• значит, найденный год — первый подходящий год после y.

Следовательно, алгоритм действительно находит ближайший следующий год с различными цифрами.

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

Для каждого проверяемого года мы выполняем проверку его 4 цифр. Это занимает константное время.

Время

В худшем случае:

O(k)

где k — количество проверенных лет.

Но так как числа четырёхзначные, а диапазон маленький, на практике это очень быстро.

Память

O(1)

Дополнительной памяти почти не требуется.

Реализация на C++

В этой версии мы разложим число на цифры арифметически.

#include <iostream>
using namespace std;

bool beautiful(int year) {
    int d1 = year % 10;
    year /= 10;
    int d2 = year % 10;
    year /= 10;
    int d3 = year % 10;
    year /= 10;
    int d4 = year % 10;

    return d1 != d2 && d1 != d3 && d1 != d4 &&
           d2 != d3 && d2 != d4 &&
           d3 != d4;
}

int main() {
    int y;
    cin >> y;

    y++;
    while (!beautiful(y)) {
        y++;
    }

    cout << y << '\n';
    return 0;
}

Что делает функция beautiful

Она получает год и достаёт его цифры:

• последнюю цифру через year % 10;
• затем убирает её через year /= 10;
• и так несколько раз.

После этого просто проверяется, что никакие две цифры не совпадают.

Реализация на Python

Здесь удобно использовать строку.

def beautiful(year):
    s = str(year)
    return s[0] != s[1] and s[0] != s[2] and s[0] != s[3] and \
           s[1] != s[2] and s[1] != s[3] and \
           s[2] != s[3]


y = int(input())
y += 1

while not beautiful(y):
    y += 1

print(y)

Более короткая версия на Python

Можно записать ещё компактнее через множество:

y = int(input())
y += 1

while len(set(str(y))) != 4:
    y += 1

print(y)

Почему это работает

• str(y) превращает год в строку;
• set(str(y)) оставляет только уникальные цифры;
• если длина множества равна 4, значит все цифры различны.

Это очень удобная и популярная техника для Python.

Частые ошибки

1. Начинать проверку с самого y

Нужно искать год, строго больший данного. Поэтому начинать надо именно с:

y + 1

А не с y.

2. Неправильно проверять уникальность цифр

Иногда сравнивают не все пары цифр. Например, проверяют только соседние, а этого недостаточно.

Для числа 1213 соседние цифры не всегда равны, но цифра 1 повторяется. Значит, сравнивать нужно полноценно.

3. Слишком усложнять задачу

Здесь не нужны:

• динамическое программирование;
• сложные структуры данных;
• генерация всех красивых лет заранее.

Обычный перебор полностью достаточен.

Методический комментарий

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

• перебор кандидатов;
• проверку свойства числа;
• работу с цифрами;
• аккуратную остановку в нужный момент.

Кроме того, здесь хорошо видно важное правило:

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

Такой приём встречается во множестве задач.

Итог

Решение очень простое:

• берём y + 1;
• пока у года есть повторяющиеся цифры, увеличиваем его;
• выводим первый подходящий.

Это даёт корректный и эффективный алгоритм, который легко реализуется и на C++, и на Python.