Questão 7
Precheck results
Vale 1,00 ponto(s).

Depita

Reginalda quer abrir uma startup revolucionária no Vale do Silício, a Depita, que irá alugar depósitos de marmitas. É uma tecnologia revolucionária: quando você chega para trabalhar, pela manhã, deposita seu almoço em uma Depita, e saca só mais tarde, quando for comer.
Porém, Reginalda não tem muita experiência desenvolvendo, então decidiu terceirizar a parte de software da sua nova empresa. Você, sabendo da incrível oportunidade de poder revolucionar a indústria, logo se prontificou para resolver o problema de Reginalda pela modesta quantia de 3 mil dólares.

Entrada:

A primeira linha da entrada consiste de um inteiro \mathbf{N}, o número de iterações subsequentes. As próximas \mathbf{N} linhas contém, cada uma, uma string sem espaços \mathbf{S}, o nome do depositante, e uma string \mathbf{D}, que pode conter espaços, com a descrição da marmita depositada.
Se o mesmo depositante realizar o depósito múltiplas vezes, somente a última instância deve ser contabilizada, pois a Depita é programada para jogar fora a marmita anterior.

Saída:

A primeira linha da saída deve conter um inteiro \mathbf{J}, o número de depositantes diferentes. As próximas \mathbf{J} linhas devem conter, cada uma, a descrição de cada uma das marmitas depositadas, ordenadas em ordem alfabética do nome do depositante.
Table 1: Por exemplo:
\captionsetup{labelformat=empty}
Input Resultado
3
João Bife do oião Ricardo Salsicha recheada com queijo João Cuscuz com leite
2
Cuscuz com leite
Salsicha recheada com queijo
2
Zé abacates
Alberto sashimi à passarinho
2
sashimi à passarinho abacates
Resposta: (penalty regime: 0 %)
N = int(input())
depositos = {}
for _ in range(N):
    linha = input()
    partes = linha.split(' ', 1) # separa depositante e descrição (pode conter espaços)
    depositante = partes[0]
    descricao = partes[1] if len(partes) > 1 else ''
    # Atualiza o depósito do depositante (última instância)
    depositos[depositante] = descricao
# Ordenar depositantes alfabeticamente ignorando maiúsculas/minúsculas
depositantes_ordenados = sorted(depositos.keys(), key=lambda x: x.lower())
print(len(depositantes_ordenados))
for depositante in depositantes_ordenados:
    print(depositos[depositante])
|
Table 2: Precheck only
\captionsetup{labelformat=empty}
Input Esperado Got
(ণ)
3
João Bife do oião
Ricardo Salsicha recheada com queijo
João Cuscuz com leite
2
Cuscuz com leite
Salsicha recheada com queijo
2
Cuscuz com leite
Salsicha recheada com queijo
(ণ)
(ণ)
2
Zé abacates
Alberto sashimi à passarinho
2
sashimi à passarinho abacates
2
sashimi à passarinho abacates
(ণ)
J

Passo 1

O que o enunciado pede e o que nos dão (peguei tudo do enunciado):
  • A primeira linha da entrada contém um inteiro N, o número de linhas seguintes.
  • Cada uma das próximas N linhas contém:
    • uma string sem espaços S — o nome do depositante;
    • um espaço separador e uma string D — a descrição da marmita (essa descrição pode conter espaços; pode também ser vazia).
  • Regra importante: se o mesmo depositante S aparecer várias vezes, somente a última descrição D deve ser considerada (ou seja, as entradas mais novas sobrescrevem as anteriores).
  • A saída deve ter:
    • na primeira linha, um inteiro J — o número de depositantes diferentes (ou seja, o número de nomes distintos que ficaram no sistema após considerar apenas a última instância de cada um);
    • nas próximas J linhas, a descrição D correspondente a cada depositante, em ordem alfabética pelo nome S.

Passo 2

Ideia geral do método (sem código ainda):
  • Usar uma estrutura que associe cada nome S à sua última descrição D. Em Python isso é um dicionário (mapa) onde a chave é S e o valor é D.
  • Percorrer as N entradas na ordem em que aparecem e, para cada linha, atualizar o dicionário com depositos[S] = D. Isso sobrescreve automaticamente as entradas anteriores do mesmo nome.
  • No final, obter a lista de nomes únicos (chaves do dicionário), ordenar alfabeticamente e imprimir o tamanho da lista e, em seguida, as descrições na ordem dos nomes ordenados.

Passo 3

Como ler e dividir cada linha corretamente (parte técnica importante e muito comum em prova):
  • Cada linha tem nome (sem espaços) e descrição (com espaços possíveis). Para separar corretamente use um split limitado a 1 divisão: em Python linha.split(' ', 1).
  • Explicando por que split(' ', 1):
    • split(' ', 1) divide a string na primeira ocorrência do espaço, produzindo uma lista com até 2 partes: a parte antes do primeiro espaço (o nome S) e o restante (a descrição D), preservando qualquer espaço dentro da descrição.
    • Se a linha só contiver o nome sem descrição, split(' ', 1) retorna uma lista com um único elemento; nesse caso a descrição será a string vazia ''.
  • Não usar strip() na linha inteira se quiser preservar espaços iniciais na descrição (normalmente isso não é crítico aqui), mas usar rstrip('\n') para tirar apenas o \n final é suficiente.

Passo 4

Atualização das entradas (porque só a última conta):
  • Ao ler uma entrada com S e D, faça depositos[S] = D.
  • Em dicionário, atribuir com a mesma chave sobrescreve o valor anterior. Isso resolve o requisito “somente a última instância deve ser contabilizada” de forma direta e simples.

Passo 5

Ordenação pelo nome do depositante:
  • Depois de preencher o dicionário, precisamos ordenar os nomes S em ordem alfabética.
  • Em Python usamos sorted(depositos.keys(), key=lambda x: x.lower()) para ordenar ignorando diferenças entre maiúsculas e minúsculas (caso deseje um ordenamento case-insensitive).
  • Observação sobre acentos/locale: str.lower() funciona com Unicode (acentos são preservados), mas a ordem resultante depende da comparação lexicográfica Unicode e pode não corresponder exatamente à ordenação por regras de idioma (locale). Em problemas de programação competitiva normal, a ordenação lexicográfica Unicode costuma ser aceita.

Passo 6

Formato da saída:
  • Primeiro imprimir o número J, que é len(depositantes_ordenados).
  • Em seguida, para cada nome na lista ordenada, imprimir apenas a descrição associada (o valor armazenado no dicionário), cada uma em sua própria linha.
  • Garantir que as linhas sejam impressas exatamente no formato pedido (uma linha com J e depois J linhas com descrições).

Passo 7

Complexidade e limites (o que isso significa para a prova):
  • Cada linha é processada em tempo O(length_of_line) para a divisão; armazenar/atualizar no dicionário é, em média, O(1).
  • Ordenação final de M nomes custa O(M log M) comparações, onde M é o número de depositantes distintos (no pior caso M \le N).
  • Memória: O(M) para guardar o dicionário.
  • Conclusão prática: solução é eficiente para os tamanhos típicos de entradas em competições e provas.

Passo 8

Casos de borda e cuidados:
  • Se N=0 (se houver esse caso), imprimir 0 e nada mais.
  • Se uma linha tiver apenas o nome (sem descrição), tratar a descrição como '' (string vazia) e imprimir a linha vazia correspondente.
  • Entradas extras após as primeiras N linhas devem ser ignoradas; entretanto, normalmente a entrada tem exatamente N linhas.
  • Manter Unicode ao imprimir (acentos) — em Python isso é natural, apenas evitar operações que quebrem a codificação.

Passo 9

Exemplo rápido mental (para fixar):
  • Entrada:
    • N=3
    • João Bife
    • Maria Arroz
    • João Salada
  • Processamento:
    • após 1ª linha: depositos = {João: Bife}
    • após 2ª linha: depositos = {João: Bife, Maria: Arroz}
    • após 3ª linha: depositos = {João: Salada, Maria: Arroz} (João sobrescreveu)
  • Ordenando nomes: [João, Maria] → imprimir 2, depois Salada, depois Arroz.

Resposta

import sys

def main():
    line = sys.stdin.readline()
    if not line:
        return
    N = int(line.strip())
    depositos = {}
    for _ in range(N):
        linha = sys.stdin.readline()
        if not linha:
            # linha ausente; considera como nome vazio (pouco provável), pula
            continue
        linha = linha.rstrip('\n')
        partes = linha.split(' ', 1)  # separa nome e descrição (descrição pode conter espaços)
        nome = partes[0]
        descricao = partes[1] if len(partes) > 1 else ''
        depositos[nome] = descricao  # atualiza (última instância sobrescreve)

    depositantes_ordenados = sorted(depositos.keys(), key=lambda x: x.lower())
    print(len(depositantes_ordenados))
    for nome in depositantes_ordenados:
        print(depositos[nome])

if __name__ == "__main__":
    main()

Exercícios relacionados