Коллеги, не могу решить задачу( Кто-нибудь может помочь?) Есть список кортежей

Question

Коллеги, не могу решить задачу( Кто-нибудь может помочь?) Есть список кортежей

чисел длинною N (N <= 2000). пример: (4, 10), (1, 5), (3, 7), (3, 10), (3, 4). Нужно найти все цепочки чисел, которые будут начинаться и заканчиваться одним и тем же числом. Неважно на каком месте стоит число, главное чтобы оно было в паре. Пример: (4, 10), (3, 10), (3, 4).
Ввод:
1) (5, 3), (8, 11), (6, 8), (4, 9), (6, 11), (10, 5),
2) (4, 8), (1, 2), (6, 3), (8, 1), (3, 4), (4, 1), (2, 0), (1, 10)
Вывод:
1) (8, 11), (6, 8), (6, 11)
2) (4, 8), (8, 1), (4, 1)
Время выполнения не должно превышать 0.5 секунды

#backend #programming #python #russian

0

31.07.2022

8 ответов

10 просмотров

Дмитрий Кедров Автор вопроса

Есть список кортежей чисел длинною N (N <= 2000). пример: (4, 10), (1, 5), (3, 7), (3, 10), (3, 4). Нужно найти все цепочки чисел длинною 3, которые будут начинаться и заканчиваться одним и тем же числом. Число из предыдущей пары должно стоять на любом месте в следующей паре. Пример ответа: (4, 10), (3, 10), (3, 4).

0

31.07.2022

Ilya Lyapin (Nestyreff)

тут самое сложное, это попасть во время выполнения 0,5 секунд. Как я уже сказал, очень похоже на алгоритм решения судоку, там тоже нужно собирать подходящие решения и, задерживая один из вариантов, решать остальные, тем самым выстраивая цепочки "возможных решений". Но самый быстрый алгоритм решения судоку, который я видел на python, выполняется 2,77 секунд. Может быть здесь проще, но хз.

0

31.07.2022

Дмитрий Кедров Автор вопроса

Ilya Lyapin (Nestyreff)
тут самое сложное, это попасть во время выполнения...

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

0

31.07.2022

Tishka17

Дмитрий Кедров
Есть список кортежей чисел длинною N (N <= 2000). ...

В голову лезет сделать словарик вида {число: список пар с ним}

0

31.07.2022

rasput

Tishka17
В голову лезет сделать словарик вида {число: списо...

вот мне тоже такое пришло

0

31.07.2022

Ilya Lyapin (Nestyreff)

а есть какое-то ограничение у самих чисел? или они абсолютно рандом?

0

31.07.2022

Дмитрий Кедров Автор вопроса

Ilya Lyapin (Nestyreff)
а есть какое-то ограничение у самих чисел? или они...

рандом

0

31.07.2022

assert · Accepted Answer

assert

Начнём с того что мы с вами не коллеги, дальше решать в место вас никто просто так не будет, приведите минимально воспроизводимый код, что вы сделали и что не получилось и как вы пробовали это исправить

0

31.07.2022

170 похожих чатов

Коллеги, не могу решить задачу( Кто-нибудь может помочь?) Есть список кортежей

8 ответов

Похожие вопросы