Всем здравствуйте, задача с уже прошедшей олимпиады, не могу понять, где мой алгоритм оказался несовершенным. Условия :
K черепах, имеющих номера от 1 до K стоят друг за другом перед закусочной. После того, как черепаха под номером m забирает еду, она снова встает в очередь так, что за ней оказывается ровно am черепах. Даже при бесконечном количестве блюд какие-то черепахи все равно останутся голодным. Определите, сколько черепах не получат ни одного подарка, если число обедов в закусочной бесконечно. Мой код представлен ниже :
n = int(input())
a = [int(elem) for elem in input().split()]
d = {}
i = 0
nh = []
for i in range(n):
num = a[i]
if num in d:
d[num] += 1
i += 1
else:
d[num] = num + 1
if d[num] == n - 1:
nh.append(d[num])
print(len(nh))
Пример:
1 2 0
Вывод :
1
Черепаха 1 получает подарок и становится между второй и третьей черепахой. Затем черепаха 2 начинает получать подарки и сразу возвращаться на первое место в очереди. Соответственно, черепаха 3 никогда не получит подарок.
Не понимаю, где в моем коде ошибка, не может ли кто нибудь помочь?
am
? Ни в задаче, ни в кодеam
нет.am
, или легче воспринятьAm
, где A - числовое значение, на которое сдвигается черепаха, а m - "индекс" черепахи в очереди. Я перепробовал много разных вариантов, данный основывается на переборе черепашьих сдвигов и те, кто оказываются в списке nh - никогда не получат ужин, по моим соображениям.