Вова и справочки

@maxevtish0501 · Регистрация: 09.07.2021

Студворк — интернет-сервис помощи студентам

К великому несчастью, Вова загремел в больницу с неизвестным вирусом. Не переживайте, он уже идёт на поправку и вот-вот выпишется! В попытках скрасить больничные будни, Вова придумал себе развлечение — следить за очередью в регистратуру больницы, где получают справочки.

Пациенты пронумерованы от 1 до n в том порядке, в котором они изначально стояли в очереди: первый с номером 1, последний с номером n.

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

Вова записал номера всех, кто выходил подышать, в том порядке, в котором это происходило. На следующий день он решил вспомнить, в каком порядке стояли люди в очереди после того, как случились все описанные события. Помогите ему выяснить это!

Известно, что новые люди не приходили в очередь, а старые всегда возвращались. Очередной человек выходил подышать только после того, как предыдущий человек, выходивший подышать, возвращался в конец очереди.

Пример
входные данные
4 5
2 1 2 2 1
выходные данные
3 4 2 1

плиз!

@Red white socks · 09.09.2022, 18:16

В чем проблема? Удаляйте и добавляйте в конец

@maxevtish0501 · 09.09.2022, 18:44 **[ТС]**

ограничение по времени не проходит

@anton78spb · 09.09.2022, 20:36

maxevtish0501, Только что-то с вашим ответом у меня не сходится

Python
1
2
3
4
5
6
7
8
9
10
n, m = map(int, input().split())
# n, m = 4, 5
s = list(map(int, input().split()))
# s = [2, 1, 2, 2, 1]
d = list(range(1, n + 1))
 
for i in s:
    d.append(d.pop(i - 1))
 
print(*d)

Code
1
2
3
4
5
4 5
2 1 2 2 1
1 4 2 3
 
Process finished with exit code 0

@maxevtish0501 · 09.09.2022, 22:24 **[ТС]**

надо не элемент с индексом i - 1, а элемент i.

Добавлено через 1 минуту
может построить начальный список (t) и делать t.pop?

Добавлено через 1 минуту
и это тоже по времени не проходит

Добавлено через 3 минуты
хотя не, с t плохая идея

@Red white socks · 09.09.2022, 22:27

maxevtish0501, раз уж ~~взялись читерить~~ встали на скользкую дорожку - бросайте свою застенчивость и природную скромность.
1. Приведите условие задачи полностью, без купюр, замен и с указанными ограничениями.
2. Приведите свой код (который "не проходит")
3. Покажите пошагово, как работает приведенный пример - почему получается такой ответ.

@Aael · 09.09.2022, 23:12

Сообщение от maxevtish0501

и это тоже по времени не проходит

list.pop(i) работает за линейное время, алгоритм выше рабоатет за O(n*t). Можно сделать свой список с удалением и вставкой за константное время, получится решение за O(n+t), примерно так:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
n, x = 4, [2, 1, 2, 2, 1]
 
# двусвязный список
# prev/next[p] - элемент перед/за элементом p
# нулевой элемент - вспомогательный, начало и конец списка
prev = [n, *range(n)] # O(n)
next = [*range(1, n+1), 0] # O(n)
 
for p in x: # O(t)
    # удаляем элемент p за O(1)
    next[prev[p]] = next[p]
    prev[next[p]] = prev[p]
 
    # вставляем элемент p в конец за O(1)
    next[prev[0]] = p
    prev[p] = prev[0]
    next[p] = 0
    prev[0] = p
 
# печать списка за O(n)
p = next[0]
while p != 0:
    print(p, end=' ')
    p = next[p]

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .	SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .	SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .	SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .	Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .	SDL3 для Android: Загрузка PNG с альфа-каналом с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .

@maxevtish0501 6 / 6 / 0 Регистрация: 09.07.2021 Сообщений: 63

	Вова и справочки 09.09.2022, 15:07. Показов 965. Ответов 6 Метки нет (Все метки) К великому несчастью, Вова загремел в больницу с неизвестным вирусом. Не переживайте, он уже идёт на поправку и вот-вот выпишется! В попытках скрасить больничные будни, Вова придумал себе развлечение — следить за очередью в регистратуру больницы, где получают справочки. Пациенты пронумерованы от 1 до n в том порядке, в котором они изначально стояли в очереди: первый с номером 1, последний с номером n. Пока Вова наблюдал за очередью, произошло t событий. Периодически кому-то из очереди становилось очень душно, и из-за этого пациент выходил на улицу подышать свежим воздухом, а затем сразу же возвращался обратно, вставая в конец очереди. Вова записал номера всех, кто выходил подышать, в том порядке, в котором это происходило. На следующий день он решил вспомнить, в каком порядке стояли люди в очереди после того, как случились все описанные события. Помогите ему выяснить это! Известно, что новые люди не приходили в очередь, а старые всегда возвращались. Очередной человек выходил подышать только после того, как предыдущий человек, выходивший подышать, возвращался в конец очереди. Пример входные данные 4 5 2 1 2 2 1 выходные данные 3 4 2 1 плиз! 0

@Red white socks 4523 / 1899 / 336 Регистрация: 18.01.2021 Сообщений: 3,489
	09.09.2022, 18:16
	В чем проблема? Удаляйте и добавляйте в конец 0

@maxevtish0501 6 / 6 / 0 Регистрация: 09.07.2021 Сообщений: 63
	09.09.2022, 18:44 [ТС]
	ограничение по времени не проходит 0

@maxevtish0501 6 / 6 / 0 Регистрация: 09.07.2021 Сообщений: 63
	09.09.2022, 22:24 [ТС]
	надо не элемент с индексом i - 1, а элемент i. Добавлено через 1 минуту может построить начальный список (t) и делать t.pop? Добавлено через 1 минуту и это тоже по времени не проходит Добавлено через 3 минуты хотя не, с t плохая идея 0

@Red white socks 4523 / 1899 / 336 Регистрация: 18.01.2021 Сообщений: 3,489
	09.09.2022, 22:27
	maxevtish0501, раз уж ~~взялись читерить~~ встали на скользкую дорожку - бросайте свою застенчивость и природную скромность. 1. Приведите условие задачи полностью, без купюр, замен и с указанными ограничениями. 2. Приведите свой код (который "не проходит") 3. Покажите пошагово, как работает приведенный пример - почему получается такой ответ. 0