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
, o número de iterações subsequentes. As próximas
linhas contém, cada uma, uma string sem espaços
, o nome do depositante, e uma string
, 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
, o número de depositantes diferentes. As próximas
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
Vale 1,00 ponto(s).
Table 1: Por exemplo:
\captionsetup{labelformat=empty}
| Input | Resultado | |||||
|
|
|||||
|
|
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 | ||||||||||||
| (ণ) |
|
|
|
(ণ) | ||||||||||
| (ণ) |
|
|
|
(ণ) |
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
, o número de linhas seguintes. - Cada uma das próximas
linhas contém: - uma string sem espaços
— o nome do depositante; - um espaço separador e uma string
— a descrição da marmita (essa descrição pode conter espaços; pode também ser vazia).
- uma string sem espaços
- Regra importante: se o mesmo depositante
aparecer várias vezes, somente a última descrição deve ser considerada (ou seja, as entradas mais novas sobrescrevem as anteriores). - A saída deve ter:
- na primeira linha, um inteiro
— 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
linhas, a descrição correspondente a cada depositante, em ordem alfabética pelo nome .
- na primeira linha, um inteiro
Passo 2
Ideia geral do método (sem código ainda):
- Usar uma estrutura que associe cada nome
à sua última descrição . Em Python isso é um dicionário (mapa) onde a chave é e o valor é . - Percorrer as
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) edescrição(com espaços possíveis). Para separar corretamente use um split limitado a 1 divisão: em Pythonlinha.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) e o restante (a descrição ), 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 usarrstrip('\n')para tirar apenas o\nfinal é suficiente.
Passo 4
Atualização das entradas (porque só a última conta):
- Ao ler uma entrada com
SeD, façadepositos[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
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
, 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
e depois 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
nomes custa O(M log M) comparações, onde é o número de depositantes distintos (no pior caso ). - 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
(se houver esse caso), imprimir 0e 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
linhas devem ser ignoradas; entretanto, normalmente a entrada tem exatamente 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:
-
João BifeMaria ArrozJoã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)
- após 1ª linha: depositos = {
- Ordenando nomes: [
João,Maria] → imprimir2, depoisSalada, depoisArroz.
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()