Задача Объединение последовательностей

Question

Задача Объединение последовательностей

Рейтинг: 0Ответов: 2Опубликовано: 24.01.2023

Объединение последовательностей Даны две бесконечных возрастающих последовательности чисел A и B. i-ый член последовательности A равен i^2. i-ый член последовательности B равен i^3.

Требуется найти Cx, где C — возрастающая последовательность, полученная при объединении последовательностей A и B. Если существует некоторое число, которое встречается и в последовательности A, и в последовательности B, то в последовательность C это число попадает в единственном экземпляре.

Входные данные

В единственной строке входных данных дано натуральное число x(1≤x≤107).

Выходные данные

Выведите Cx.

Ввод:
4
Вывод:
9

Ввод:
1
Вывод:
1

Ввод:
2
Вывод:
4

#include <iostream>

using namespace std;

int main() {
    uint64_t x;
    cin >> x;

    int i=1, j=1, a=1, b=1;
    int result = 0;
    while (x) {
        if (a <= b) {
            x += a == b;
            result = a;
            i += 1;
            a = i * i;
        } else {
            result = b;
            j += 1;
            b = j*j*j;
        }
        x -= 1;
    }
    cout << result;
}

Подскажите пожалуйста, что не так и помогите исправить.

c#

Источник: Stack Overflow на русском

Answer 1

▲ 2

Поскольку вся последовательность не нужна, то искать k-тый член за линейное время как-то не фонтан.

Применим бинарный поиск, и найдём решение за логарифмическое число шагов

(точность вычисления целочисленных корней особо не проверял)

#include <iostream>
#include <cmath>
using namespace std;
uint64_t kth(uint64_t k) {
    uint64_t m, a2, a3, a6, cnt;
    uint64_t lo = 1;
    uint64_t hi = k*k;
    while (hi > lo) {
        m = (lo + hi) >> 1;
        a2 = (uint64_t) pow((m+1.0e-6), 1.0/2);
        a3 = (uint64_t) pow((m+1.0e-6), 1.0/3);
        a6 = (uint64_t) pow((m+1.0e-6), 1.0/6);
        cnt = a2 + a3 - a6;
        if (cnt < k)
            lo = m + 1;
        else
            hi = m;
    }
    return lo;
}


int main()
{
    uint64_t k;
    cin >> k;
    cout << kth(k);
    return 0;
}

>>
 10  64
 11  81 
 77  4225

Answer 2

▲ 0

Возможные ошибки в коде:

Сначала, в x задается индекс C, который нужно найти, но затем в цикле x используется для отслеживания кол-ва оставшихся элементов C, которые нужно найти.

Далее в строке x += a == b; инкрементируется x когда a равно b, это неверно так как элемент должен быть в последовательности только один раз.

Ещё в строке result = a; и result = b; сохр. рез-т в переменной result, но в конце цикла нигде не используется и выводится посл. значение a или b, а не Cx.

И в конце цикла должно выводиться Cx, а не последний элемент A или B.

#include <iostream>

using namespace std;

int main() {
    uint64_t x;
    cin >> x;

    int i=1, j=1, a=1, b=1;
    while (x) {
        if (a <= b) {
            if(x==1) Cx=a;
            i += 1;
            a = i * i;
        } else {
            if(x==1) Cx=b;
            j += 1;
            b = j*j*j;
        }
        x -= 1;
    }
    cout << Cx;
}

Вот ещё решение:

#include <iostream>

using namespace std;

int main() {
    uint64_t x;
    cin >> x;

    int i=1, a=1;
    while (a <= x*x) {
        i++;
        a = i*i;
    }

    int j=1, b=1;
    while (b <= x*x*x) {
        j++;
        b = j*j*j;
    }

    if(a<=b) cout << a;
    else cout << b;
}

или даже так:

#include <iostream>

using namespace std;

int main() {
    uint64_t x;
    cin >> x;

    int i=1, a=1;
    int j=1, b=1;

    for (int k = 1; k <= x; k++) {
        if (a <= b) {
            if (k == x) cout << a;
            i++;
            a = i*i;
        } else {
            if (k == x) cout << b;
            j++;
            b = j*j*j;
        }
    }
}

Здесь я использую цикл while для перебора последовательности C и проверки текущего элемента на каждой итерации:

#include <iostream>

using namespace std;

int main() {
    uint64_t x;
    cin >> x;

    int i=1, a=1;
    int j=1, b=1;
    int k = 0; // current index of C
    int last_a = 0, last_b = 0; // last element of A and B that was added to C

    while (k < x) {
        if (a <= b) {
            if (a != last_a) {
                k++;
                last_a = a;
                if (k == x) cout << a;
            }
            i++;
            a = i*i;
        } else {
            if (b != last_b) {
                k++;
                last_b = b;
                if (k == x) cout << b;
            }
            j++;
            b = j*j*j;
        }
    }
}

Задача Объединение последовательностей

Ответы