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:
- Três listas de strings. Cada lista será fornecida em uma linha especifica.
Saídas:
- 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
Entradas:
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
(palavras separadas por espaços). - Segunda linha: lista de strings
(palavras separadas por espaços). - Terceira linha: lista de strings
(palavras separadas por espaços). - Observação: as duas primeiras listas
e serão diferentes (não são idênticas), conforme o enunciado.
- Primeira linha: lista de strings
-
Saída:
- Uma sequência de caracteres (sem espaços, apenas dígitos) onde cada dígito corresponde a uma palavra da lista
, na mesma ordem. - Para cada palavra de
, o dígito é: -
se a palavra aparece em nenhuma das listas e ; -
se aparece em exatamente uma das listas ( ou ); -
se aparece nas duas listas e .
-
- Uma sequência de caracteres (sem espaços, apenas dígitos) onde cada dígito corresponde a uma palavra da lista
Passo 2
Estratégia de resolução (o plano concreto, passo a passo mental):
- Para testar se uma palavra aparece em
ou de forma rápida, converto cada uma das duas primeiras listas em um conjunto (em Python, um set). Vou chamar esses conjuntos de e , onde e . - Depois, percorro as palavras na ordem em que aparecem em
. Para cada palavra de : - Calculo
, isto é, somo quando está em e mais quando está em . Assim pode valer , ou . - Converto
para caractere e acrescento ao resultado final.
- Calculo
- 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
. Assim, em vez de percorrer toda a lista para cada palavra de (o que seria lento), uso e para obter testes rápidos.
Passo 3
Casos concretos — como funciona numa palavra:
- Suponha uma palavra
. - Se
e então e o dígito é . - Se
e então e o dígito é . - Se
e então e o dígito é . - Se
e então e o dígito é .
- Se
Passo 4
Exemplo passo a passo (usando o primeiro exemplo do enunciado) para garantir que estamos alinhados:
-
[“bola”, “garrafa”, “pedra”, “cachorro”] (peguei estes valores do enunciado). -
[“cachorro”, “pedra”, “pato”] (peguei estes valores do enunciado). -
[“bola”, “garrafa”, “pato”, “cachorro”, “pedra”] (peguei estes valores do enunciado). -
. -
. - Para cada palavra de
: - “bola”: pertence só a
. - “garrafa”: pertence só a
. - “pato”: pertence só a
. - “cachorro”: pertence a
e a . - “pedra”: pertence a
e a .
- “bola”: pertence só a
- 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()), depoisstrip()para remover espaços extras nas extremidades esplit()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
; se contiver palavras repetidas, cada ocorrência será processada e produzirá um dígito correspondente. - Complexidade: construir os conjuntos custa
onde e são tamanhos de e . Depois fazemos testes de pertinência, cada um em tempo esperado , 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))