beecrowd 1340 · Simulação paralela

Eu Posso Adivinhar a Estrutura de Dados!

Recebemos operações de inserção e remoção, mas não sabemos qual estrutura as executou. A solução testa todas as candidatas ao mesmo tempo.

Enunciado Código .py

Operação 1 x

Insere o valor x na estrutura desconhecida.

Operação 2 x

Informa que a remoção deveria devolver x.

Resposta

Uma estrutura, not sure ou impossible.

Não é DFS nem BFS

Não estamos percorrendo um grafo. Este é um problema de simulação e eliminação de hipóteses: pilha, fila e fila de prioridade recebem a mesma sequência enquanto ainda puderem explicar as saídas.

Fila de prioridade: ela não preserva a ordem de chegada. A próxima remoção devolve o maior valor disponível neste exercício.

Mapa da solução

Comece com três hipóteses verdadeiras

p, f e fp indicam quais estruturas continuam possíveis.

Repita toda inserção nas candidatas

Enquanto uma candidata está ativa, ela recebe o mesmo valor.

Compare cada remoção

Se uma candidata está vazia ou devolve outro valor, seu booleano passa para falso.

Conte as sobreviventes

Uma define a resposta; várias geram not sure; nenhuma gera impossible.

Execução interativa

Três estruturas em paralelo

Escolha um desfecho:
hipóteses

Sequência de operações

1 insere · 2 remove

Pilha

Próxima saída: último valor inserido.

Fila

Próxima saída: primeiro valor inserido.

Prioridade

Próxima saída: maior valor disponível.

Valor da operação
Quem cada uma removeu
Quem permaneceu candidata

Por que inserir valores negativos?

heapq remove primeiro o menor valor. Guardar -elemento transforma o maior valor original no menor número armazenado.

Exemplo: valores 2 e 7 viram -2 e -7. A fila retira -7 primeiro; ao negar novamente, recuperamos 7.

Código completo comentado 
from collections import deque
import heapq
import sys


def classificar(operacoes):
    # Reproduzimos a mesma sequência nas três candidatas.
    pilha = []
    fila = deque()
    prioridade = []  # Negativos transformam a min-heap em max-heap.
    pode_ser_pilha = True
    pode_ser_fila = True
    pode_ser_prioridade = True

    for tipo, valor in operacoes:
        if tipo == 1:
            # A operação 1 insere o valor.
            if pode_ser_pilha:
                pilha.append(valor)
            if pode_ser_fila:
                fila.append(valor)
            if pode_ser_prioridade:
                heapq.heappush(prioridade, -valor)
            continue

        # A operação 2 informa qual valor deveria sair.
        if pode_ser_pilha and (not pilha or pilha.pop() != valor):
            pode_ser_pilha = False
        if pode_ser_fila and (not fila or fila.popleft() != valor):
            pode_ser_fila = False
        if pode_ser_prioridade and (
            not prioridade or -heapq.heappop(prioridade) != valor
        ):
            pode_ser_prioridade = False

    candidatas = sum((pode_ser_pilha, pode_ser_fila, pode_ser_prioridade))
    if candidatas == 0:
        return "impossible"
    if candidatas > 1:
        return "not sure"
    if pode_ser_pilha:
        return "stack"
    if pode_ser_fila:
        return "queue"
    return "priority queue"


# Os casos são lidos até EOF.
dados = iter(map(int, sys.stdin.buffer.read().split()))
while True:
    try:
        quantidade = next(dados)
    except StopIteration:
        break

    operacoes = [(next(dados), next(dados)) for _ in range(quantidade)]
    print(classificar(operacoes))

Complexidade

Para cada uma das n operações, pilha e fila trabalham em O(1). A fila de prioridade insere e remove em O(log n). Assim, o limite dominante é O(n log n), com O(n) de espaço.