Задача 6. Числа ≡

Условие

Аня любит, когда числа состоят из одинаковых цифр. Поэтому ей нравятся числа 777 или 5555, а вот число 1234 ей совсем не нравится.

Иногда у Ани бывает хорошее настроение, тогда ей по прежнему нравятся все числа, состоящие из одинаковых цифр, но также нравятся числа, в которых все цифры кроме одной одинаковые, как, например, в числе 77727.

У Ани есть число x. Аня хочет найти минимальное целое число y ≥ x, которое ей понравится.

Требуется написать программу, которая по заданному целому числу x и информации, хорошее ли настроение у Ани, находит минимальное целое число y ≥ x, которое нравится Ане.

Формат входных данных

Первая строка ввода содержит целое число x (обратите внимание, что число x не может быть сохранено в стандартном 32-битном типе данных, необходимо использовать 64-битный тип данных, например long long в C++, int64 в Паскале).

Вторая строка ввода содержит число k, равное 0 или 1. Значение k = 1 означает, что у Ани хорошее настроение, а значение k = 0 — что это не так.

Формат выходных данных

Следует вывести одно целое число y.

Должны выполняться следующие свойства:

• y ≥ x;
• если k = 0, то все цифры в десятичной записи числа y должны совпадать;
• если k = 1, то все цифры в десятичной записи числа y, кроме, может быть, одной, должны совпадать.

Ограничения

1 ≤ x ≤ 10¹⁷

Система оценки

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

Примеры тестов

700
0

777

700
1

700

Разбор

Подзадача 1

Заметим, что k = 0 означает, что число должно состоять из всех одинаковых цифр. В этой подзадаче можно просто увеличивать x, пока все цифры числа не будут одинаковы. Число 111 111 обладает этим свойством и не меньше всех возможных чисел во вводе, значит будет сделано не больше чем такое количество шагов.

Подзадача 2

В этой подзадаче увеличение шагами по одному уже не приводит к успеху. Для получения баллов за эту подзадачу нужно разобраться, как устроено минимальное число, большее заданного, состоящее из одинаковых цифр.

Первую цифру числа нельзя уменьшить, посмотрим, можно ли её оставить такой же. Пойдем по числу от старших цифр к младшим, пока они равны первой цифре числа f. Если в какой-то момент очередная цифра цифра отличается от первой, посмотрим меньше она или больше. Если она оказывается меньше первой цифры числа, то можно просто заменить все цифры на f, получив большее число из всех одинаковых цифр. Если же она оказывается больше, то придется увеличить первую цифру. Это можно сделать, если она не равна 9. В этом случае заполним число цифрами f + 1. Иначе надо взять число из всех единиц, имеющее на одну цифру в своей десятичной записи больше.

Подзадача 3

В этой задаче снова маленькое значение x, и можно увеличивать его, пока все его цифры, кроме, может быть, одной не станут равны. На этот раз верхним порогом выступает число 100 000. Единственная трудность этой подзадачи — техническая, проверить, что все цифры, кроме не более чем k, равны.

Подзадача 4

На самом деле полное решение задачи даже проще разбора частных случаев предыдущих подзадач. Заметим, что искомое число имеет не более 18 десятичных цифр. Значит всего подходящих чисел 18 ⋅ 9 для k = 0 и не больше 18 ⋅ 10 ⋅ 18 ⋅ 10 для k = 1 (во втором случае мы перебираем длину, основную цифру, позицию отличающейся и саму отличающуюся). Переберем все потенциальные ответы и из тех, которые не меньше x, выберем минимальный.

Код на C++, который строит число из цифр d длины len, на позиции pos ставится цифра d2:

long long num(int len, int d, int pos, int d2) {
    long long res = 0;
    for (int i = 0; i < len; i++) {
        if (i == pos) {
            res = res * 10 + d2;
        } else {
            res = res * 10 + d;
        }
    }
    return res;
}

Код на C++, который перебирает все подходящие числа для k = 1:

for (int i = 1; i <= 18; i++) {
    for (int d = 0; d < 10; d++) {
        for (int p = 0; p < i; p++) {
            for (int d2 = 0; d2 < 10; d2++) {
                long long y = num(i, d, p, d2);
                if (y >= x && (ans == -1 || y < ans)) {
                    ans = y;
                }
            }
        }
    }
}