Нахождение максимального количества пар в списке

[rockclimber]

arseniiv в сообщении #1351589 писал(а):

Угу. Если вы намекаете на кое-что, что мы тут не будем упоминать явно, чтобы не заспойлить решение целиком, то раз здесь нужно лишь посчитать число удовлетворяющих пар, а не перебирать их, квадратичность превращается в линейность.

Нет, я намекал на то, что время будет не линейное.
И я как-то не очень представляю, как посчитать количество пар, не перебирая их.

[arseniiv]

Написал ЛС, перепроверьте идею.

[realeugene]

Самое главное не учесть одну ти ту же пару несколько раз. В общем, проход по списку двумя индексами (в Питоне список это массив), для каждого элемента $a$ во внешнем цикле находим граничный элемент $b$ (максимальный, такой, что $b \le 2 a$) во внутреннем цикле и прибавляем его номер (индекс плюс 1) к счётчику. Индекс $b$ сохраняем между внутренними итерациями. Правильную обработку отрицательных чисел и повторов оставляю ТС.

[leon_ard]

Всех благодарю за ответы! Постараюсь на днях разобраться и самостоятельно решить.

[leon_ard]

Pphantom в сообщении #1351591 писал(а):

Остался, пожалуй, только один вопрос, ответ на который влияет на реализацию: под словом "список" в исходном условии понимался именно соответствующий тип данных или массив тоже сойдет?

Извиняюсь, не заметил вопрос. Да, имеется ввиду тип данных.