beecrowd 1110 · Fila / deque
Jogando Cartas Fora
Em cada rodada, descartamos a carta do topo e movemos a nova carta do topo para o fundo. O processo termina quando sobra uma carta.
Entrada
Valores de n até aparecer 0.
Saída
Ordem das cartas descartadas e a carta restante.
Estrutura
Fila com topo no front e fundo no back.
Por que é uma fila?
A carta do topo é sempre a primeira da sequência. Remover do topo equivale a pop front; mover para o fundo combina outro pop front com push back.
Mapa da solução
Monte as cartas de 1 até n
A carta 1 ocupa o topo e a carta n ocupa o fundo.
Descarte o front
O primeiro pop(0) vai para a lista resultado.
Mova o novo front
O segundo pop(0) retira a próxima carta e o insert a coloca no fundo.
Pare quando o tamanho for 1
Essa única carta é impressa como Remaining card.
Execução interativa
Fila de cartas
Cartas ainda na fila
topo à esquerda · fundo à direitaCartas descartadas
ordem de saídaPróxima carta
- Topo
- Movida
Saída parcial
O texto final mantém exatamente os rótulos exigidos pelo exercício.
Por que usar deque?
O topo do baralho está no início da fila. popleft() retira essa carta em O(1), enquanto append() coloca a próxima carta na base, também em O(1).
A expressão cartas.append(cartas.popleft()) representa exatamente a segunda regra: retirar a carta do topo e transferi-la para a base.
Código completo comentado
from collections import deque
while True:
quantidade = int(input())
# Zero encerra a entrada e não forma um baralho.
if quantidade == 0:
break
# O início é o topo; o fim é a base do baralho.
cartas = deque(range(1, quantidade + 1))
descartadas = []
while len(cartas) > 1:
# Regra 1: descarte a carta que está no topo.
descartadas.append(cartas.popleft())
# Regra 2: mova a nova carta do topo para a base.
cartas.append(cartas.popleft())
texto_descartadas = ", ".join(map(str, descartadas))
print(f"Discarded cards: {texto_descartadas}")
print(f"Remaining card: {cartas[0]}")Complexidade da implementação
Cada carta é descartada ou movimentada um número constante de vezes. Como popleft e append custam O(1), a simulação leva O(n) de tempo e usa O(n) de espaço.