Решение задачи Последовательность с цифрами с Codeforces

С пояснением   Просмотров: 47


Определим рекуррентную последовательность следующим образом:
an+1=an+minDigit(an)⋅maxDigit(an).
Здесь minDigit(x) и maxDigit(x) — минимальная и максимальная цифры в десятичной записи числа x без ведущих нулей соответственно. Для примеров обратитесь к примечаниям.

Ваша задача — по заданным a1 и K вычислить aK.

Код

#include <bits/stdc++.h>

using namespace std;
void solve()
{
    long long a1, k, mx = INT_MIN, mn = INT_MAX, res;
    cin >> a1 >> k;
    res = a1;
    vector<long long> a;
    while(a1){
        mx = max(a1 % 10, mx);
        mn = min(a1 % 10, mn);
        a1 /= 10;
    }
    while(k-- > 1){
        if(mn == 0)
            break;
        res += mn * mx;
        mx = INT_MIN;
        mn = INT_MAX;
        long long t = res;
        while(t){
            mx = max(t % 10, mx);
            mn = min(t % 10, mn);
            t /= 10;
        }
    }
    cout << res << endl;
}
int main()
{
    int t;
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

         

Администратор Photo Автор: Администратор


Попробуем вычислить последовательность при фиксированном a1=1: 1,2,6,42,50,50,50,…
Нам повезло, и минимальная цифра стала равной 0, после чего элемент перестал изменяться, так как мы прибавляем к нему 0.

На самом деле это не везение, и такое будет происходить всегда. Заметим, что мы каждый раз прибавляем не более 9⋅9=81, поэтому разность между двумя соседними числами в последовательности не превышает 81. Пусть мы никогда не получим минимальную цифру, равную 0. Тогда последовательность будет бесконечно возрастать. Рассмотрим X=1000(⌊a11000⌋+1). На отрезке [X;X+99] все числа имеют 0 в разряде сотен, поэтому никакой элемент этого отрезка не может быть членом нашей последовательности. Но в нашей последовательности есть числа больше X. Возьмем минимальное из них, оно не меньше X+100. Тогда предыдущее число в последовательности не меньше (X+100)−81=X+19. Оно больше X, но меньше минимального из таких чисел. Противоречие.

На самом деле мы показали, что в последовательности нет чисел больше X+100, а значит мы встретим число с нулевой цифрой среди первых 1001 элементов.

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

В реальности максимальный номер первого элемента с нулевой цифрой — 54, минимальное a1 для такой последовательности равно 28217.


Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться