Превышено время выполнения в задаче “Забавная последовательность”

27 апреля 2021, 03:10

На acmp.ru я столкнулся с этой задачей:

(Время: 1 сек. Память: 16 Мб)

Определим последовательность ai следующим образом: a1 = 1, an = an - 1 + 3, если число n уже встречалось в последовательности a, и an = an - 1 + 2, иначе. Нетрудно видеть, что первые 8 членов этой последовательности таковы: 1, 3, 6, 8, 10, 13, 15, 18.

Ваша задача вычислить an.

Входные данные: Входной файл INPUT.TXT содержит целое число n (1 ≤ n ≤ 105).

Выходные данные: В выходной файл OUTPUT.TXT выведите an.

Мой алгоритм был следующий:

Создаём массив int a[100001] - наша последовательность.
Создаём массив bool w[100001] - место, где мы храним информацию о том, было ли число i в последовательности.
a[1] = 1; w[1] = true;
i От 2 до N {
    если w[i] == true то a[i] = a[i - 1] + 3;
    иначе a[i] = a[i - 1] + 2;
    w[a[i]] = true;
}
Вывод a[n].

Вот код, написанный по этому алгоритму:

#include <iostream>
int w[100002], a[100002], n;
int main()
{
    w[1] = true;
    a[1] = 1;
    std::cin >> n;
    for(int i = 2; i <= n; i++){
        if(w[i] == true){
            a[i] = a[i - 1] + 3;
        }
        else a[i] = a[i - 1] + 2;
        w[a[i]] = true;
    }
    std::cout << a[n];
}

Проблема в том, что у меня ошибка Time limit exceeded(выполнение программы около 1,4 секунд). Пока что я не могу придумать алгоритм быстрее.

Как я могу оптимзировать программу? Есть ли какие-то формулы или алгоритмы для этого?

Answer 1

Случаи, они всякие бывают...

#include <iostream>
using namespace std;
int main()
{
    int w[100002] = {0,1}, a = 1, n;
    cin >> n;
    for(int i = 2; i <= n; i++)
    {
        a += 2;
        if(w[i]) a ++;
        if (a <= 100000) w[a] = 1;
    }
    cout << a << endl;
}

На размер:

#include <iostream>
int main()
{
    int w[100002] = {0,1}, a = 1, n, i = 1;
    std::cin >> n;
    while(i < n)
        w[(a += w[++i]?3:2) < 100001 ? a : 0] = 1;
    std::cout << a;
}

Answer 2