Новая игра Шерлока

@koipaqwe · Регистрация: 10.07.2021

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

Новая игра Шерлока
Шерлок Холмс очень ценит своего напарника Ватсона, но считает его не готовым противостоять уловкам уличных мошенников. Сегодня он сделал модель популярной игры в наперстки и тренирует доктора. У него есть n коробок разного размера, при этом коробка с меньшим номером всегда помещается в коробку с большим номером.

Изначально все коробки перевернуты вверх дном и стоят рядом. Холмс может взять какую-либо коробку и накрыть ею любую другую меньшего размера. Он проделывает это много раз, периодически спрашивая Ватсона, под какой коробкой находится в настоящий момент коробка с номером #j. Ватсон должен указать номер самой верхней из накрывающих коробку #j коробки (или саму коробку #j, если она не накрыта никакой другой).

Ваша задача — по заданной последовательности действий Шерлока подсказать ответы доброму, но очень невнимательному Ватсону.

Поясним приведённый ниже пример.

Первое действие — перекладывание коробки #2 на коробку #1.
Второе действие — перекладывание коробки #3 на коробку #2.
Третье действие — вопрос, где находится коробка #1; правильный ответ — под коробкой #3.
Четвертое действие — перекладывание коробки #5 на коробку #4.
Пятое действие — вопрос, где находится коробка #5; правильный ответ — коробка#5 (она не накрыта другими).
Шестое действие — перекладывание коробки #5 на коробку #3.
Седьмое действие — вопрос, где находится коробка #4; правильный ответ — коробка #4 (она не накрыта другими).
Входные данные

В первой строке содержатся целые числа n и q (1≤n≤2⋅10⁵,1≤q≤1⋅10⁵) — количество коробок и общее количество действий: перекладываний коробок и вопросов Холмса.

В каждой из следующих q строк описывается либо корректное перекладывание коробки, либо вопрос.

Описание перекладывания коробки начинается с числа 1, после которого через пробел следует сначала номер большей коробки, а затем — номер меньшей, которая будет накрыта коробкой большего размера. Гарантируется, что большая и меньшая коробка не накрыты никакими другими.

Описание вопроса начинается с числа 2, после которого через пробел следует номер коробки, местоположение которой интересует Шерлока.

Выходные данные

Выведите ответы на вопросы Холмса — по одному в каждой строке.

Ввод
5 7
1 2 1
1 3 2
2 1
1 5 4
2 5
1 5 3
2 4

Вывод
3
5
4

@NickWhite · 02.09.2023, 10:07

Актуально срочно!

@Red white socks · 02.09.2023, 10:37

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

Актуально срочно!

Система непересекающихся множеств

@idealist · 02.09.2023, 12:32

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
n, q = map(int, input('n, q->').split())
boxes = {}
for i in range(q):
    data = list(map(int, input(f'data {i+1}->').split()))
    if data[0] == 1:
        _, bigger_num, smoller_num = data
        if smoller_num in boxes:
            boxes[smoller_num]['next'] = bigger_num
        else:
            boxes[smoller_num] = {'prev':None, 'next':bigger_num}
        if bigger_num in boxes:
            boxes[boxes[bigger_num]['prev']]['next'] = None
            boxes[bigger_num]['prev'] = smoller_num
        else:
            boxes[bigger_num] = {'prev': smoller_num, 'next': None}
    elif data[0] == 2:
        box_num = data[1]
        while boxes[box_num]['next'] != None:
            box_num = boxes[box_num]['next']
        print(box_num)

@Red white socks · 02.09.2023, 14:49

idealist, это плохая реализация СНМ. При новом запросе вы не учитываете результаты прошлых. Это может сильно сказаться на скорости

Новые блоги и статьи Все статьи Все блоги /
Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Символьное дифференцирование igorrr37 13.02.2026 / * Программа принимает математическое выражение в виде строки и выдаёт его производную в виде строки и вычисляет значение производной при заданном х Логарифм записывается как: (x-2)log(x^2+2) -. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .	И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.
«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»	SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image 8Observer8 10.02.2026 Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .

@koipaqwe 1 / 1 / 0 Регистрация: 10.07.2021 Сообщений: 27

	Новая игра Шерлока 04.09.2021, 13:19. Показов 2898. Ответов 4 Метки нет (Все метки) Новая игра Шерлока Шерлок Холмс очень ценит своего напарника Ватсона, но считает его не готовым противостоять уловкам уличных мошенников. Сегодня он сделал модель популярной игры в наперстки и тренирует доктора. У него есть n коробок разного размера, при этом коробка с меньшим номером всегда помещается в коробку с большим номером. Изначально все коробки перевернуты вверх дном и стоят рядом. Холмс может взять какую-либо коробку и накрыть ею любую другую меньшего размера. Он проделывает это много раз, периодически спрашивая Ватсона, под какой коробкой находится в настоящий момент коробка с номером #j. Ватсон должен указать номер самой верхней из накрывающих коробку #j коробки (или саму коробку #j, если она не накрыта никакой другой). Ваша задача — по заданной последовательности действий Шерлока подсказать ответы доброму, но очень невнимательному Ватсону. Поясним приведённый ниже пример. Первое действие — перекладывание коробки #2 на коробку #1. Второе действие — перекладывание коробки #3 на коробку #2. Третье действие — вопрос, где находится коробка #1; правильный ответ — под коробкой #3. Четвертое действие — перекладывание коробки #5 на коробку #4. Пятое действие — вопрос, где находится коробка #5; правильный ответ — коробка#5 (она не накрыта другими). Шестое действие — перекладывание коробки #5 на коробку #3. Седьмое действие — вопрос, где находится коробка #4; правильный ответ — коробка #4 (она не накрыта другими). Входные данные В первой строке содержатся целые числа n и q (1≤n≤2⋅10⁵,1≤q≤1⋅10⁵) — количество коробок и общее количество действий: перекладываний коробок и вопросов Холмса. В каждой из следующих q строк описывается либо корректное перекладывание коробки, либо вопрос. Описание перекладывания коробки начинается с числа 1, после которого через пробел следует сначала номер большей коробки, а затем — номер меньшей, которая будет накрыта коробкой большего размера. Гарантируется, что большая и меньшая коробка не накрыты никакими другими. Описание вопроса начинается с числа 2, после которого через пробел следует номер коробки, местоположение которой интересует Шерлока. Выходные данные Выведите ответы на вопросы Холмса — по одному в каждой строке. Ввод 5 7 1 2 1 1 3 2 2 1 1 5 4 2 5 1 5 3 2 4 Вывод 3 5 4 0

@NickWhite 0 / 0 / 0 Регистрация: 07.08.2023 Сообщений: 2
	02.09.2023, 10:07
	Актуально срочно! 0

@Red white socks 4523 / 1899 / 336 Регистрация: 18.01.2021 Сообщений: 3,489
	02.09.2023, 14:49
	idealist, это плохая реализация СНМ. При новом запросе вы не учитываете результаты прошлых. Это может сильно сказаться на скорости 0