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

[leon_ard]

Здравствуйте! Во время решения задачи (на python) столкнулся с проблемой.
Дан отсортированный по возрастанию список чисел. Необходимо найти максимальное возможное количество пар чисел $(a, b)$, для которых верно неравенство $b =< 2a$
Например, для списка [1, 3, 4] максимальным количеством таких пар будет 1.
Попытки решения:
1. Прикинул полный перебор. Не подойдёт, максимальная возможная длина списка равна 50000.
2. Пробовал разбить на пары при помощи itertools.combinations(), но думаю, это не имеет смысла, ведь пары тоже придётся комбинировать.
Пожалуйста, помогите. Заранее благодарен.
P. S. Обращение к модераторам: надо ли список оформить тегом code? Если надо, я могу оформить.

[Pphantom]

leon_ard в сообщении #1351490 писал(а):

P. S. Обращение к модераторам: надо ли список оформить тегом code? Если надо, я могу оформить.

Не обязательно. Но далее лучше для такого рода вставок использовать моноширинный шрифт (см. тэг "tt"), получится так: [1, 3, 4]

[arseniiv]

leon_ard
Зафиксируйте первый или второй элемент пары — каким может быть оставшийся? Теперь увеличьте или уменьшите его немного — каких изменений можно ожидать от множества допустимых значений оставшегося? Это должно навести на мысль о линейном алгоритме.

[rockclimber]

leon_ard в сообщении #1351490 писал(а):

Необходимо найти максимальное возможное количество пар чисел $(a, b)$, для которых верно неравенство $b =< 2a$

Я так понимаю, числа $a$ и $b$ - не обязательно стоят рядом, так? Лучше это условие в явном виде указывать.

[Pphantom]

leon_ard в сообщении #1351490 писал(а):

Дан отсортированный по возрастанию список чисел. Необходимо найти максимальное возможное количество пар чисел $(a, b)$, для которых верно неравенство $b =< 2a$
Например, для списка [1, 3, 4] максимальным количеством таких пар будет 1.

Кстати, в условии явно что-то не оговорено или неправильно сформулировано. Для такого списка пар, удовлетворяющих условию, больше: (3,1), (4,1), (4,3), (3,4). Или дополнительно неявно предполагается, что $a \le b$?

[kotenok gav]

rockclimber в сообщении #1351500 писал(а):

Я так понимаю, числа $a$ и $b$ - не обязательно стоят рядом, так?

В переписке выяснилось, что обязательно Индекс b на один больше индекса a.

leon_ard в сообщении #1351490 писал(а):

1. Прикинул полный перебор. Не подойдёт, максимальная возможная длина списка равна 50000.

Ну и почему не подойдёт? Сложность перебора - O(n). $n=50000$ сойдет. Вот если было бы 10 миллиардов...

[Pphantom]

kotenok gav в сообщении #1351545 писал(а):

В переписке выяснилось, что обязательно Индекс b на один больше индекса a.

Тогда это очевидный линейный перебор. Меньше - невозможно, больше - не нужно.

[leon_ard]

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

leon_ard в сообщении #1351490 писал(а):

P. S. Обращение к модераторам: надо ли список оформить тегом code? Если надо, я могу оформить.

Не обязательно. Но далее лучше для такого рода вставок использовать моноширинный шрифт (см. тэг "tt"), получится так: [1, 3, 4]

Хорошо

rockclimber в сообщении #1351500 писал(а):

leon_ard в сообщении #1351490 писал(а):

Необходимо найти максимальное возможное количество пар чисел $(a, b)$, для которых верно неравенство $b =< 2a$

Я так понимаю, числа $a$ и $b$ - не обязательно стоят рядом, так? Лучше это условие в явном виде указывать.

Приношу извинения, действительно забыл обговорить это условие. Числа $a$ и $b$ рассматриваются так, что $b > a$ (но их индексы могут отличаться на любое число). Поэтому варианты (3, 1), (4, 1) и (4, 3) не подойдут.

kotenok gav в сообщении #1351545 писал(а):

leon_ard в сообщении #1351490 писал(а):

1. Прикинул полный перебор. Не подойдёт, максимальная возможная длина списка равна 50000.

Ну и почему не подойдёт? Сложность перебора - O(n). $n=50000$ сойдет. Вот если было бы 10 миллиардов...

Не совсем так. Индекс $b$ может быть больше индекса $a$ на любое число, поэтому сложность перебора считаем по формуле $N = n_1n_2...n_n$, что намного больше 10 миллиардов

[kotenok gav]

Но в переписке вы говорили, что они стоят рядом.

[leon_ard]

Наверное, я тогда написал не очень понятно. Я подразумевал, что индекс $b$ строго больше индекса $a$

[kotenok gav]

Тогда надо брать цент. пару и уменьшать a с увелечением b, пока не нарушится неравенство.

[leon_ard]

Что считать центральной парой в этом списке [1, 3, 4]?
А в этом [3, 4, 10]?

[rockclimber]

kotenok gav в сообщении #1351565 писал(а):

огда надо брать цент. пару и уменьшать a с увелечением b, пока не нарушится неравенство.

Надо перебрать все возможные $a$ и все возможные $b$. arseniiv выше написал, как.

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

Это должно навести на мысль о линейном алгоритме.

Что вы имеете в виду под линейным алгоритмом? Перебор за линейное время?

[arseniiv]

Зачем брать центральную пару? Ну можно же заметить, что если $a'>a$, то $b\leqslant 2a\Rightarrow b\leqslant 2a'$. Что это говорит о возможности считать пары?

rockclimber в сообщении #1351586 писал(а):

Что вы имеете в виду под линейным алгоритмом? Перебор за линейное время?

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

P. S. Хм, хотя «найти максимальное возможное количество пар» можно понимать и как перебор… Тогда не линейный, конечно.

[Pphantom]

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