Faça um programa que receba três listas de strings. Cada lista representa um conjunto de elementos. Cada lista será digitada em uma linha especifica. Será garantido que as duas primeiras listi serão diferentes.
Seu programa deverá exibir no dispositivo de saída padrão, para cada palavra da terceira lista, se a palavra em questão apareceu em nenhuma, uma ou nas duas listas iniciais.
Entradas:
  1. Três listas de strings. Cada lista será fornecida em uma linha especifica.
Saídas:
  1. Sequência de valores que denotam se cada palavra da terceira lista apareceu em nenhuma, uma ou nas duas listas iniciais.
Exemplo de Entrada:
bola garrafa pedra cachorro
cachorro pedra pato
bola garrafa pato cachorro pedra
Exemplo de Saída:
11122
Exemplo de Entrada:
bola garrafa pedra cachorro
cachorro pedra pato
cachorro pedra
Exemplo de Saída:
22

Passo 1

O enunciado pede um programa que leia três listas de strings, cada uma em uma linha separada, e para cada palavra da terceira lista informe se ela apareceu em nenhuma, em uma ou nas duas primeiras listas. Vou resumir claramente o que foi dado e o que é pedido (peguei todas as informações do enunciado):
  • Entradas:
    • Primeira linha: lista de strings L_1 (palavras separadas por espaços).
    • Segunda linha: lista de strings L_2 (palavras separadas por espaços).
    • Terceira linha: lista de strings L_3 (palavras separadas por espaços).
    • Observação: as duas primeiras listas L_1 e L_2 serão diferentes (não são idênticas), conforme o enunciado.
  • Saída:
    • Uma sequência de caracteres (sem espaços, apenas dígitos) onde cada dígito corresponde a uma palavra da lista L_3, na mesma ordem.
    • Para cada palavra de L_3, o dígito é:
      • 0 se a palavra aparece em nenhuma das listas L_1 e L_2;
      • 1 se aparece em exatamente uma das listas ( L_1 ou L_2);
      • 2 se aparece nas duas listas L_1 e L_2.

Passo 2

Estratégia de resolução (o plano concreto, passo a passo mental):
  • Para testar se uma palavra aparece em L_1 ou L_2 de forma rápida, converto cada uma das duas primeiras listas em um conjunto (em Python, um set). Vou chamar esses conjuntos de S_1 e S_2, onde S_1 = \text{set}(L_1) e S_2 = \text{set}(L_2).
  • Depois, percorro as palavras na ordem em que aparecem em L_3. Para cada palavra w de L_3:
    • Calculo c = \mathbf{1}_{w \in S_1} + \mathbf{1}_{w \in S_2}, isto é, somo 1 quando w está em S_1 e mais 1 quando w está em S_2. Assim c pode valer 0, 1 ou 2.
    • Converto c para caractere e acrescento ao resultado final.
  • No final, junto todos os caracteres na ordem e imprimo como uma única linha sem espaços.
Explicação didática do porquê usar conjuntos:
  • Um conjunto é uma estrutura que permite testar “pertinência” (membro ou não) em tempo constante, normalmente O(1). Assim, em vez de percorrer toda a lista L_1 para cada palavra de L_3 (o que seria lento), uso S_1 e S_2 para obter testes rápidos.

Passo 3

Casos concretos — como funciona numa palavra:
  • Suponha uma palavra w.
    • Se w \notin S_1 e w \notin S_2 então c = 0 e o dígito é 0.
    • Se w \in S_1 e w \notin S_2 então c = 1 e o dígito é 1.
    • Se w \notin S_1 e w \in S_2 então c = 1 e o dígito é 1.
    • Se w \in S_1 e w \in S_2 então c = 2 e o dígito é 2.

Passo 4

Exemplo passo a passo (usando o primeiro exemplo do enunciado) para garantir que estamos alinhados:
  • L_1 = [“bola”, “garrafa”, “pedra”, “cachorro”] (peguei estes valores do enunciado).
  • L_2 = [“cachorro”, “pedra”, “pato”] (peguei estes valores do enunciado).
  • L_3 = [“bola”, “garrafa”, “pato”, “cachorro”, “pedra”] (peguei estes valores do enunciado).
  • S_1 = \{\text{"bola"}, \text{"garrafa"}, \text{"pedra"}, \text{"cachorro"}\}.
  • S_2 = \{\text{"cachorro"}, \text{"pedra"}, \text{"pato"}\}.
  • Para cada palavra de L_3:
    • “bola”: pertence só a S_1 \Rightarrow c=1.
    • “garrafa”: pertence só a S_1 \Rightarrow c=1.
    • “pato”: pertence só a S_2 \Rightarrow c=1.
    • “cachorro”: pertence a S_1 e a S_2 \Rightarrow c=2.
    • “pedra”: pertence a S_1 e a S_2 \Rightarrow c=2.
  • Resultado concatenado: “11122”, que confere com o exemplo.

Passo 5

Detalhes de implementação e cuidados práticos:
  • Leitura: usar três chamadas a uma função que leia linha por linha (em Python, input()), depois strip() para remover espaços extras nas extremidades e split() para quebrar em palavras por espaços.
  • Caso uma das linhas esteja vazia, split() retorna lista vazia — o programa continua correto (uma lista vazia significa nenhum elemento naquela lista).
  • A ordem de saída deve respeitar a ordem das palavras em L_3; se L_3 contiver palavras repetidas, cada ocorrência será processada e produzirá um dígito correspondente.
  • Complexidade: construir os conjuntos custa O(n_1 + n_2) onde n_1 e n_2 são tamanhos de L_1 e L_2. Depois fazemos n_3 testes de pertinência, cada um em tempo esperado O(1), logo a solução é eficiente para entradas grandes.

Passo 6

Programa em Python que implementa o plano descrito (pronto para rodar). Ele lê três linhas da entrada padrão e imprime a sequência de dígitos pedida:

Resposta

L1 = input().strip().split()
L2 = input().strip().split()
L3 = input().strip().split()

S1 = set(L1)
S2 = set(L2)

res = []
for w in L3:
    c = int(w in S1) + int(w in S2)
    res.append(str\text{(c)})

print(''.join(res))

Exercícios relacionados