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:

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:

	#include<bits/stdc++.h> //biblioteca utilizada
	using namespace std;

	int main()
	{
	char letra[2]; //variável do tipo char para armazenar a letra na entrada
	int resp=0; //variável correspondente à quantidade de "V"'s na entrada
	for(int i=0; i<6; i++) //loop para ler a entrada
	{
	scanf(" %[^\n]s", letra); //lê até o final da linha, armazenando o caractere na variável 'letra'
	if(letra[0]=='V')resp++; //se o caractere de entrada for 'V', soma 1 à 'resp'
	}
	if(resp==0)printf("-1"); //se resp=0, imprime -1
	else if(resp==1 \|\| resp==2)printf("3"); //se resp=1 ou resp=2, imprime 3
	else if(resp==3 \|\| resp==4)printf("2"); //se resp=3 ou resp=4, imprime 2
	else if(resp==5 \|\| resp==6)printf("1"); //se resp=5 ou resp=6, imprime 1
	return 0; //o programa encerra (retorna a 0)
	}

view raw Torneio de Tênis.cpp hosted with

by GitHub

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:

	#include <bits/stdc++.h>
	using namespace std;

	constexpr int maxn = 110;

	// salvamos os vetores indicando qual foi a ultima mensagem, a soma atual e se há alguma mensagem pendente ou não
	int ans[maxn], ultima[maxn], atv[maxn];

	int main() {
	// t representa o tempo atual que estamos simulando
	int n, t = 1; scanf("%d", &n);
	bool ok = 0;
	for(int i = 0; i < n; i++) {
	// lemos o tipo do evento que nos é dado
	char c; int x; scanf(" %c %d", &c, &x);
	// se for um evento do tipo T só adicionamos o tempo dado na resposta
	if(c == 'T') t += x, ok = 0;
	// evento de tipo R
	else if(c == 'R') {
	// se o evento anterior foi do tipo T não adicionamos nada no tempo, senao adicionamos 1
	t += ok; ok = 1;
	// salvamos qual o tempo da última mensagem enviada e dizemos que existe uma mensagem pendente
	ultima[x] = t;
	atv[x] = 1;
	} else { // evento do tipo E
	// mudamos o tempo como fizemos no tipo R
	t += ok; ok = 1;
	// adicionamos na resposta para esse amigo a diferença entre os tempos de envio e resposta
	ans[x] += t - ultima[x];
	// marcamos como não havendo nenhuma mensagem pendente
	atv[x] = 0;
	}
	}
	for(int i = 1; i <= 100; i++) {
	if(ultima[i]) { // checo se esse indice de amigo recebeu alguma mensagem em qualquer momento
	printf("%d ", i);
	if(atv[i]) printf("-1\n"); // se existe alguma mensagem pendente printo -1
	else printf("%d\n", ans[i]); // senao printo o tempo de resposta
	}
	}
	}

view raw tempo_resposta.cpp hosted with

by GitHub

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

	// Comentário NOIC - OBI 2021 - Fase 1 P2 - Zero para cancelar
	// Lúcio Figueiredo

	#include <bits/stdc++.h>

	using namespace std;

	int main(void)
	{
	int n;
	scanf("%d", &n);

	stack<int> stk; // declaramos a stack

	for (int i = 1; i <= n; i++)
	{
	int x;
	scanf("%d", &x);

	if (x == 0) stk.pop();
	else stk.push(x);
	}

	// resposta do problema
	int ans = 0;

	// calculamos a soma dos números que sobram
	while (stk.size() > 0)
	{
	ans += stk.top();
	stk.pop();
	}

	printf("%d\n", ans);
	}

view raw zero.cpp hosted with

by GitHub