Задача Объединение последовательностей
Объединение последовательностей Даны две бесконечных возрастающих последовательности чисел 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;
}
Подскажите пожалуйста, что не так и помогите исправить.
Ответы (3 шт):
Возможные ошибки в коде:
Сначала, в 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;
}
}
}
Ваш код не корректно объединяет последовательности A и B. Вы используете две переменные i и j, которые указывают на текущий индекс элемента в последовательностях A и B соответственно. Вам нужно использовать только одну переменную, которая указывает на текущий индекс элемента в объединенной последовательности C. Вы также должны сравнивать элементы из последовательностей A и B, которые соответствуют текущему индексу, а не текущие значения a и b. И еще в вашем коде также используется переменная x, которая должна отображать текущий индекс элемента в объединенной последовательности C. И она используется как счетчик, который отслеживает, сколько элементов еще нужно найти в объединенной последовательности C. По моему мнению это неверно, так как в задаче требуется найти Cx, а не первые x элементов объединенной последовательности C. Я бы сделал так:
- Определил одну переменную, которая будет указывать на текущий индекс элемента в объединенной последовательности C.
- Использовать эту переменную для сравнения элементов из последовательностей A и B, которые соответствуют текущему индексу.
- Использовать входное значение x для нахождения Cx, а не как счетчик.
#include <iostream>
using namespace std;
int main() {
uint64_t x;
cin >> x;
uint64_t a=1, b=1;
int i = 1;
while (x) {
if (i*i <= i*i*i) {
if (x == i) {
cout << i*i;
return 0;
}
i++;
} else {
if (x == i) {
cout << i*i*i;
return 0;
}
i++;
}
x--;
}
cout << "Cx not found";
return 0;
}
Тут использовал одну переменную i, который указывает на текущий индекс элемента в объединенной последовательности C. Сравнение i^2 и i^3 и выводит нужное значение Cx, используя входное значение x как индекс. Если x больше чем количество элементов в объединенной последовательности, то выводится сообщение "Cx not found".
Поскольку вся последовательность не нужна, то искать 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