Решение задачи Числовая последовательность с Acmp

Без пояснения   Просмотров: 38


Дима недавно поступил на работу в научно-исследовательский институт «Числовые Последовательности». Как следует из названия этого института, основным направлением его работы является проведение различных исследований в области числовых последовательностей.

Недавно руководитель отдела, где начал работать Дима, при решении одной из проблем столкнулся с весьма интересной последовательностью чисел a1, a2, …, an, …, которая определяется следующим образом: a1 = 0 и каждое последующее число ai (1 < i ≤ n) определяется как наименьшее большее натуральное число, десятичная запись которого не содержит цифр, представленных в десятичной записи ai-1.

Требуется написать программу, которая по значению числа n вычисляет величину an.

Код

#include <bits/stdc++.h>

using namespace std;


int main()
{
    int n, sz = 1;
    bool a0 = 0, a1 = 1;
    cin >> n;
    vector<string> s;

    for(int i = 0; i <= 9; ++i)
        s.push_back(to_string(i));

    while(s.size() < n){
        string t = s[s.size() - 1];
        if(t[0] == '9'){
            ++sz;
            if(t[t.size() - 1] != '1'){
                t.clear();
                t += '1';
                string next = "2";
                if(a0 == 0){
                    t.insert(t.size(), sz - 1, '0');
                    next.insert(next.size(), sz - 1, '2');
                }
                else{
                    t.insert(t.size(), sz - 1, '1');
                    next.insert(next.size(), sz - 1, '0');
                }
                s.push_back(t);
                s.push_back(next);
            }
            else{
                string next = "2";
                next.insert(next.size(), sz - 1, '0');
                s.push_back(next);
                a0 = !a0;
                a1 = !a1;
            }
        }
        else{
            string res = "";
            res+=t[0] + 1;
            if(a0 == 0){
                res.insert(res.size(), sz - 1, '0');
            }
            else{
                res.insert(res.size(), sz - 1, '1');
            }
            a0 = !a0;
            a1 = !a1;
            s.push_back(res);
        }
    }
    cout << s[n - 1];
    //1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 22, 30, 41, 50, 61, 70, 81, 90, 111, 200, 311, 400, 511, 600, 711, 800, 911, 1000, 2222, 3000,
    return 0;
}

         

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



Комментарии

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