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

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 Lúcio Figueiredo, Luca Dantas e Pedro Racchetti

Para conferir a prova na íntegra, clique aqui.

Idade de Camila

Conhecimento Prévio Necessário:

Em resumo, o problema pede como saída o segundo menor dentre três números $a_0, a_1, a_2$ dados. Para encontrar este número, basta analisar os seguintes três casos:

Caso 1: $a_0 \geq min(a_1, a_2)$ e $a_0 \leq max(a_1, a_2)$ : Neste caso, $a_0$ é o segundo maior número.
Caso 2: $a_1 \geq min(a_0, a_2)$ e $a_1 \leq max(a_0, a_2)$ : Neste caso, $a_1$ é o segundo maior número.
Caso 3: Se nenhum dos casos acima são verdadeiros, então $a_2$ é o segundo maior número.

Para analisar estes três casos, podemos utilizar a estrutura condicional If/Else if/Else e o operador lógico and.

Complexidade: $O(1)$ .

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)$ .

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:

Cifra da Nlogônia

Conhecimento prévio necessário:

String e vector

Para resolvermos esse problema, é conveniente usar as estruturas $string$ e $vector$ da STL. Também usaremos as letras como inteiros em alguns momentos, para facilitar os laços de iteração (uma letra pode ser representado por um número com auxílio da tabela ascii, subtraindo o do caractere a). Na prática, iremos simular o algoritmo descrito no problema, sendo as principais dificuldades efetuar os itens 2 e 3 para lidar com consoantes na palavra original. Para o item 2, basta passar pelo alfabeto com dois $fors$ , primeiro da direita para a esquerda, partindo da letra atual, até encontrarmos uma vogal, e depois repetir o mesmo procedimento da esquerda para a direita. Comparamos então os resultados e escolhemos a vogal mais próxima. Para o item 3, passamos da esquerda para a direita no alfabeto, partindo da letra a direita da atual (tomando o devido cuidado com a letra z), até encontramos a primeira letra que não é uma vogal.

Ao final, basta imprimir a sequência resultante para a saída.

Complexidade: $O(|P| * 26)$ . Segue o código, para melhor compreensão do problema: