OBI 2021 - Fase 1 - Programação Nível 1

Para se preparar para a OBI, confira o nosso Roteiro de Estudos, nele você vai encontrar um direcionamento completo de como estudar!

Comentário por Anita Ramos, Lúcio Figueiredo e Luca Dantas

Para conferir a prova na íntegra, clique aqui.

Torneio de Tênis

Conhecimento Prévio Necessário:

• Estruturas Condicionais
• Loops

Para esse problema, podemos utilizar a estrutura de repetição $for()$ para realizar a leitura da entrada, ou seja, as letras $V$ e $P$. Como o problema se trata de contar a quantidade de vitórias (caractere $V$) na entrada, cada vez que lermos a letra $V$, somamos 1 à variável $res$. Após realizar toda a leitura, basta checar à qual intervalo dado no enunciado para a divisão dos grupos a variável $res$ se encaixa e imprimir a resposta correspondente. Para isso usamos o comando $if$ que checa:

• Se $res=0$, ou seja, o participante não será convidado a continuar o treinamento;
• Se $res=1$ ou $res=2$, ou seja, o participante ficará no grupo 3;
• Se $res=3$ ou $res=4$, ou seja, o participante ficará no grupo 2;
• Se $res=5$ ou $res=6$, ou seja, o participante ficará no grupo 1;

Complexidade: $O(1)$. Segue o código para melhor compreensão do problema:

Tempo de Resposta

Conhecimento Prévio Necessário:

• Vetores

A estratégia que iremos utilizar para resolver esse problema é simplesmente simular o processo da troca de mensagens.

Como cada amigo só manda uma mensagem por vez e cada nova mensagem de um amigo aparece depois de Sara ter respondido a mensagem anterior, podemos salvar um vetor que indica, para cada amigo, qual foi o tempo em que a última mensagem foi enviada por Sara.

Além disso também é interessante salvarmos para cada amigo um outro vetor indicando qual é o tempo de resposta para esse amigo considerando somente as mensagens respondidas anteriormente. Também utilizaremos um vetor para indicar se existe ou não alguma mensagem pendente.

Agora, para cada evento dado pelo problema iremos simular os acontecimentos da seguinte maneira: salvamos o tempo atual sempre considerando todas as regras dadas no enunciado (se virmos um evento T adicionamos o tempo dado no tempo atual e se virmos qualquer outro evento adicionamos 1). Quando virmos um evento de mensagem recebida por algum amigo, salvamos no vetor de tempos o momento em que a mensagem foi recebida, marcando assim que há no momento uma mensagem pendente. Quando virmos um evento de resposta vamos para o respectivo amigo, adicionamos no tempo de resposta dele o tempo que se passou desde o momento que ele mandou a mensagem até o momento atual e dizemos que não há nenhuma mensagem pendente desse amigo.

Complexidade: $O(n)$.

Segue o código para melhor entendimento:

Zero para cancelar

Conhecimento Prévio Necessário:

• Estrutura de dados Stack

Note que os procedimentos realizado no problema são muito semelhantes às operações de uma stack (pilha). De fato, se interpretarmos a lista de números em qualquer ponto da fala do chefe como uma stack, falar um número positivo $x$ é equivalente a realizar a função $push(x)$ e falar o número zero é equivalente a realizar a função $pop()$. Portanto, basta realizar estas duas operações em uma stack e imprimir como saída a soma dos números restantes na estrutura.

Complexidade: $O(n)$.