Всем привет, есть последовательность aaaa...aabbb...bbccc...cc..., причем a n штук, b

(n-1) штука, c (n-2) штуки и т.д. до 0.
Как по номеру элемента получить в каком сегменте (а, b, c и т д) он находится? Без цикла.

Бинпоиск

Не получится сегменты - абстрактны, а так это просто массив каких то чисел. Исправил вопрос)

Бинпоиск по ответу, я имел в виду. Если элемент находится левее, чем k последних сегментов, то его позиция <= n(n + 1)/2 - k(k + 1)/2

Аа, но это все равно цикл, я думал может формула есть какая...

Ну можно попробовать поаппроксимировать и перебрать значения n - sqrt((n(n+1)/2 - x)/2) +- 3

k*(n + n - k) / 2 < i, найти наибольшее такое k

<=

Мне кажется, что все-таки (x+1)*(n + n - x) / 2 <= i+1

Это не работает(

Это даже для 1 не работает, если взять n = 5, I = 1, то x должен быть -1)

А ноль?

При x=0, слева будет 5

В другую сторону неравенство. x=0, как раз при n=5, i=0,1,2,3,4

Да, похоже сработало, генерируется верная последовательность, спасибо большое)

Если я правильно понял условие, то мы имеем треугольную матрицу вида aaaaaaaaaaa bbbbbbbbbb cccccccccc dddddddd ...... которая записана в одномерный массив. n - количество строк такой матрицы Размер такого массива - сумма первых n членов арифмет прогрессии с шагом 1. S = (n + 1) * n / 2 если нам надо найти некое число в сегменте под номером k, мы знаем, что все подходящие числа находятся в сегменте длины k, и перед ними сегмент k+1, а после k-1 (если k > 1 && k < n) Таким образом мы можем найти начало сегмента начиная с конца массива. Sk1 = k * (k - 1) / 2 соответственно конец Sk2 = Sk1 + k итого наше число находится в отрезке [n - Sk2, n - Sk1) Если нам известен индекс, то надо сделать обратную операцию: g = n - k -1 - находим индекс с конца. пользуясь тем, что мы знаем формулу начала сегмента получаем неравенство: (z+1) * z /2 <= g < (z+2) * (z+1) / 2 g мы знаем z - номер искомого отрезока Если поиграть с этим неравенством думаю можно вывести короткий алгоритм поиска, не привязанный к перебору размеров явно. Ну и поскольку z это номер "с конца" не забыть ревертнуть его в изначальный. (может где-то напутал со знаками, но вроде ок)

Да, так и есть, но пока у меня идея найти корни из предложенного выше уравнения и с помощью округления уже найти сам номер сегмента.

в моём случае у тебя 2 параболы (полу, только то что правее у) и прямая параллельная х надо найти точки пересечения и на получившемся отрезке должно лежать ровно одно целое значение (по х), которое и будет ответом.

Спасибо, с корнем уже все получилось)