1

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

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 никогда не получит подарок.

Не понимаю, где в моем коде ошибка, не может ли кто нибудь помочь?

13
  • Опишите, пожалуйста, как вы решаете задачу? Commented 9 янв. 2022 в 15:22
  • Что такое am? Ни в задаче, ни в коде am нет. Commented 9 янв. 2022 в 15:24
  • @StanislavVolodarskiy в задаче есть - за ней оказывается ровно am черепах массив, который вводится, видимо набор этих а для каждой черепахи. Но это мои догадки
    – splash58
    Commented 9 янв. 2022 в 15:44
  • am, или легче воспринять Am, где A - числовое значение, на которое сдвигается черепаха, а m - "индекс" черепахи в очереди. Я перепробовал много разных вариантов, данный основывается на переборе черепашьих сдвигов и те, кто оказываются в списке nh - никогда не получат ужин, по моим соображениям.
    – Savvon
    Commented 9 янв. 2022 в 15:45
  • 1
    а почему вы думаете, что процесс завершится за n шагов. три черепахи. первая берет и встает в середину, остальные в хвост. на 4м шаге последняя получит. не?
    – splash58
    Commented 9 янв. 2022 в 15:53

1 ответ 1

0

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

# тестовые данные
from random import randint
k = 1000
# am = [1, 2, 0]
am = [randint(0, k-1) for i in range(k)]

# список, где True - получила
get = [False for i in range(k)]

# очередь
queue = tuple(i for i in range(k))
# print(queue)

# список вариантов очередей 
qlist = set()
qlist.add(queue)

while True:
    cur = queue[0]
    get[cur] = True
    queue = queue[1:len(queue)-am[cur]] + (cur,) + queue[len(queue)-am[cur]:]
    # print(queue)
    # Если такая очередь уже была, можно заканчивать 
    if queue in qlist:
        print(k - sum(get))
        break
    qlist.add(queue)
3
  • " # Если такая очередь уже была, можно заканчивать " Почему? допустим, есть очередь (1,2,3,4,5), которая меняется так: (2,1,3,4,5,) -> (1,2,3,4,5) -> (2,3,4,5,1) -> ... С какого перепугу я должен заканчивать после 2-го шага?
    – Zombotron
    Commented 10 янв. 2022 в 18:07
  • @Zombotron, ваша иллюстрация невозможна в условиях задачи. Текущее состояние очереди полностью определяет следующее состояние. Мы получаем траекторию на конечном множестве. Рано или поздно она зациклится. Commented 10 янв. 2022 в 19:02
  • @Stanislav Volodarskiy Перечитал все еще раз комменты. Да, протупил. Нужно отдохнуть.
    – Zombotron
    Commented 10 янв. 2022 в 20:04

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.