Top.Mail.Ru
Ответы
Аватар пользователя
zavric_228_titov
1г
Аватар пользователяПрограммирование

Помогите пожалйста создать программу на питоне.

В современном мире есть множество различных баз данных, основанных на разных структурах и принципах. В дополнение к реляционным (например, MySQL) и графовым (например, GraphQL), недавно стажер компании VK предложил идею новой базы данных DequeQL, основанной на деках. Разумеется, не все идеи стажеров действительно хорошие, но, будучи ответственным ментором, Лев решил реализовать его идею и проверить ее эффективность. Дек — структура данных, хранящая последовательность элементов, и позволяющая добавлять
новый элемент или вынимать элемент с любого из двух концов последовательности. Базовым блоком данных в DequeQL является юнит (unit) — пустой дек, соответствующий минимальной единице информации. Сама база данных представляет из себя множество пронумерованных деков, вложенных друг в друга. Дек, не вложенный ни в какой другой, называется корнем. Разумеется, если некоторый юнит не лежит в другом деке, он тоже считается корнем.
DequeQL поддерживает четыре операции на изменение:
1. push_back(d1, d2) — положить корень d1 в конец корня d2 (d1 перестает быть корнем);
2. push_front(d1, d2) — положить корень d1 в начало корня d2 (d1 перестает быть корнем);
3. pop_back(d) — достать из корня d последний элемент (при этом этот элемент становится
корнем);
4. pop_front(d) — достать из корня d первый элемент (изъятый элемент тоже становится корнем);
Обратите внимание, что операции можно производить только над корневыми элементами базы данных. Лев уже реализовал эти операции, и решил, что DequeQL может быть полезна в одном из новых проектов VK, если расширить ее функционал и добавить поддержку ответов на запрос pop_complexity(d) — какое минимальное количество операций pop_back или pop_front надо выполнить, чтобы d стал корнем? Сама структура базы данных при этом не меняется, то есть выполнять
соответствующие действия pop не надо.
Пока у Льва выходной, у вас есть возможность зарекомендовать себя в качестве квалифицированного разработчика. Вам дана база данных, состоящая из n юнитов с номерами от 1 до n. Реализуйте требуемый функционал и выведите ответ на каждый запрос.
Формат входных данных:
В первой строке ввода даны два целых числа n и m — количество юнитов в базе данных и количество запросов (1 <= n, m <= 2*10^5 ).
В i-й из следующих строк дан i-й запрос в формате «<command> d» или «<command> d1 d2», где <command> — команда или запрос, описанные в условии (1 6 d, d1, d2 6 n). Гарантируется, что операции изменения базы данных производятся только над корневыми вершинами, и что операции pop производятся только с непустыми деками.
Формат выходных данных :
Для каждого запроса информации выведите в отдельной строке ответ на этот запрос -- минимальное количество операций pop, необходимое, чтобы сделать cоответствующий элемент корнем.

По дате
По рейтингу
Аватар пользователя
aethelbeorn_1
Мастер
1г

Для реализации описанной функциональности вам необходимо создать программу на Python, которая будет обрабатывать входные данные и выполнять операции для базы данных DequeQL. Вот пример кода, который может помочь вам начать:

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889
 class DequeNode:  
 
    def __init__(self, value):  
 
        self.value = value  
 
        self.left = None  
 
        self.right = None  
 
  
 
def push_back(d1, d2):  
 
    # Реализация операции push_back  
 
    pass  
 
  
 
def push_front(d1, d2):  
 
    # Реализация операции push_front  
 
    pass  
 
  
 
def pop_back(d):  
 
    # Реализация операции pop_back  
 
    pass  
 
  
 
def pop_front(d):  
 
    # Реализация операции pop_front  
 
    pass  
 
  
 
def pop_complexity(d):  
 
    # Реализация операции pop_complexity  
 
    pass  
 
  
 
n, m = map(int, input().split())  
 
  
 
for i in range(m):  
 
    command = input().split()  
 
    if command[0] == "push_back":  
 
        d1, d2 = map(int, command[1:])  
 
        push_back(d1, d2)  
 
    elif command[0] == "push_front":  
 
        d1, d2 = map(int, command[1:])  
 
        push_front(d1, d2)  
 
    elif command[0] == "pop_back":  
 
        d = int(command[1])  
 
        pop_back(d)  
 
    elif command[0] == "pop_front":  
 
        d = int(command[1])  
 
        pop_front(d)  
 
    elif command[0] == "pop_complexity":  
 
        d = int(command[1])  
 
        print(pop_complexity(d))


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

Обратите внимание, что для реального применения потребуется более детальная логика работы с деками и базой данных, а также обработка ошибок и исключений. Кроме того, данная задача может потребовать более сложных алгоритмов обработки данных для оптимальной производительности.

Если помогло, сделайте ответ лучшим!

Аватар пользователя
factator
Гуру
1г
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677
 # Создаем словарь, где ключи - номера деков, а значения - сами деки 
deques = {i: deque() for i in range(1, n + 1)} 
 
# Определяем функции для операций над деками 
def push_back(d1, d2): 
    # Перемещаем корень d1 в конец корня d2 
    deques[d2].append(deques[d1]) 
    # Удаляем корень d1 из словаря 
    del deques[d1] 
 
def push_front(d1, d2): 
    # Перемещаем корень d1 в начало корня d2 
    deques[d2].appendleft(deques[d1]) 
    # Удаляем корень d1 из словаря 
    del deques[d1] 
 
def pop_back(d): 
    # Достаем последний элемент из корня d 
    elem = deques[d].pop() 
    # Если это дек, то добавляем его в словарь с новым номером 
    if isinstance(elem, deque): 
        new_key = max(deques.keys()) + 1 
        deques[new_key] = elem 
        # Возвращаем номер нового корня 
        return new_key 
    # Иначе возвращаем None 
    else: 
        return None 
 
def pop_front(d): 
    # Достаем первый элемент из корня d 
    elem = deques[d].popleft() 
    # Если это дек, то добавляем его в словарь с новым номером 
    if isinstance(elem, deque): 
        new_key = max(deques.keys()) + 1 
        deques[new_key] = elem 
        # Возвращаем номер нового корня 
        return new_key 
    # Иначе возвращаем None 
    else: 
        return None 
 
def pop_complexity(d): 
    # Вычисляем минимальное количество операций pop, чтобы сделать d корнем 
    # Для этого ищем d во всех деках и считаем, сколько элементов перед ним 
    count = 0 
    for key, value in deques.items(): 
        # Если d - корень, то возвращаем 0 
        if key == d: 
            return 0 
        # Если d - элемент дека, то считаем, сколько элементов перед ним 
        elif d in value: 
            index = value.index(d) 
            # Возвращаем минимум из количества элементов слева и справа 
            return min(index, len(value) - index - 1) 
    # Если d не найден, то возвращаем -1 
    return -1 
 
# Читаем количество запросов 
m = int(input()) 
 
# Обрабатываем каждый запрос 
for _ in range(m): 
    # Читаем запрос 
    query = input().split() 
    # Выполняем соответствующую операцию или выводим ответ на запрос 
    if query[0] == "push_back": 
        push_back(int(query[1]), int(query[2])) 
    elif query[0] == "push_front": 
        push_front(int(query[1]), int(query[2])) 
    elif query[0] == "pop_back": 
        pop_back(int(query[1])) 
    elif query[0] == "pop_front": 
        pop_front(int(query[1])) 
    elif query[0] == "pop_complexity": 
        print(pop_complexity(int(query[1])))
Больше по теме