Найти элемент в практически бесконечном списке - PullRequest
Новая
       19

Найти элемент в практически бесконечном списке

1 голос
/ 24 июня 2019

Я пытаюсь решить эту проблему:

Список инициализируется как ["Sheldon", "Leonard", "Penny", "Rajesh", "Howard"], а затем подвергается серии операций. В каждой операции первый элемент списка перемещается в конец списка и дублируется. Например, в первой операции список становится ["Leonard", "Penny", "Rajesh", "Howard", "Sheldon", "Sheldon"] (с перемещением и дублированием "Sheldon"); во второй операции он становится ["Penny", "Rajesh", "Howard", "Sheldon", "Sheldon", "Leonard", "Leonard"] (с перемещением и дублированием «Леонарда»); и т.д. Учитывая положительное целое число n , найдите строку, которая была перемещена и продублирована в операции n . [Перефразировано с https://codeforces.com/problemset/problem/82/A]

Я написал рабочее решение, но он слишком медленный, когда n огромен: 

l = ['Sheldon','Leonard','Penny','Rajesh','Howard']
n = int(input()) # taking input from user to print the name of the person
                 # standing at that position

 for i in range(n):
    t = l.pop(0)
    l.append(t)
    l.append(t)

    #debug
    # print(l)

print(t)

Как я могу сделать это быстрее?

Ответы [ 3 ]

2 голосов
/ 24 июня 2019

Вот решение, которое выполняется в O(log(input/len(l))) без каких-либо реальных вычислений (без операций со списком): 

l = ['Sheldon','Leonard','Penny','Rajesh','Howard']
n = int(input()) # taking input from user to print the name of the person
                 # standing at that position

i = 0
while n>(len(l)*2**i):
    n = n - len(l)* (2**i)
    i = i + 1

index = int((n-1)/(2**i ))

print(l[index])

Объяснение: каждый раз, когда вы отодвигаете весь список назад, длина списка будет увеличиваться ровно на len(l) x 2^i. Но вы должны сначала узнать, сколько раз это происходит. Это то, что делает while (это то, что делает n = n - len(l)* (2**i)). Время останавливается, когда он осознает, что i раз добавление двойного списка произойдет. Наконец, после того как вы вычислили i, вы должны вычислить индекс. Но в i -ом добавленном списке каждый элемент копируется 2^i раз, поэтому вам нужно разделить число на 2**i. Одна небольшая деталь заключается в том, что для индекса необходимо вычесть 1, поскольку списки в Python индексируются 0, а входные данные индексируются 1.

0 голосов
/ 24 июня 2019

Как сказал @khelwood, вы можете определить, сколько раз вам нужно удвоить список.

Чтобы понять это, учтите, что если вы начинаете со списка из 5 человек и выполняете 5 шагов своей итерации,вы будете в том же порядке, что и раньше, только со всеми дважды в нем.

Я не уверен на 100%, что вы имеете в виду под n-й позицией, поскольку она все время сдвигается, но если вы имеете в виду человека впереди после nитерации, найдите наибольшее целое число i, которое удовлетворяет 

5*2^i<n

, чтобы узнать, сколько раз ваш список удвоился.Затем просто посмотрите на оставшийся список (каждое имя упоминается i раз), чтобы получить имя в позиции n-5 * 2 ^ i.

0 голосов
/ 24 июня 2019

Вы не сможете избежать расчета списка, но, возможно, вы можете сделать его немного проще:

В каждом цикле (когда Шелдон снова первый) длина списка удваивается, поэтому это выглядит так:

После 1 цикла: SSLLPPRRHH

После 2 циклов: SSSSLLLLPPPPRRRRHHHH

...

в то время как количество выпитой колы составляет 5 * ((2 ** n) -1), где n - количество циклов.

Таким образом, вы можете рассчитать состояние списка в ближайшем завершенном цикле. Например. Кола № 50:

5 * ((2 ** 3)) = 40 означает, что после 40 коксов Шелдон следующий в очереди.

Затем вы можете использовать алгоритм, описанный в задании, и получить последний в строке.

Надеюсь, это поможет.

...