Comentário Noic OBI 2020 - Fase 1 Turno B - Programação Nível 1

Comentário por Anita Ramos, Thiago Mota e Pedro Racchetti

Para conferir a prova na íntegra, clique aqui.

Divisão do Tesouro

Conhecimento prévio necessário:

Entrada e Saída

Esse é um problema bem simples, que pode ser resolvido apenas com leitura, impressão e uma lógica. A lógica funcionará assim: contaremos o capitão como 2 outros marinheiros. Assim, dividiremos o total do tesouro $A$ por $N+2$ para descobrir quanto cada marinheiro ganhará e depois dobrar o valor para o capitão. Por exemplo, se pensarmos em $A=10$ e $N=8$ , temos o seguinte:

Cada marinheiro deve receber $1$
O capitão deve receber $2$

Perceba que o capitão conta como dois outros marinheiros. Se dividirmos $A$ por $8 + 2$ (capitão), teremos 1. Por fim, dobramos esse valor para o capitão, ficando com 1 para cada marinheiro e 2 para o capitão.

Na parte da programação então, depois de declarar as variáveis e ler toda a entrada, dividimos $A$ por $N+2$ e dobramos o valor (x2). Assim, o cálculo geral fica: $2 \cdot (A/(N+2))$

Complexidade: $O(1)$ .

Segue o código comentado para melhor compreensão da solução:

	#include<bits/stdc++.h> //biblioteca utilizada
	using namespace std;
	int main()
	{
	int A,N; //declaração de variáveis
	scanf("%d", &A); //leitura do 'A'
	scanf("%d", &N); //leitura do 'N'
	printf("%d", 2(A/(N+2))); //imprimi a resposta do cálculo de 2(A/(N+2))
	return 0; //retorna a 0
	}

view raw

tesouro.cpp

hosted with ❤ by GitHub

Três por Dois

Conhecimento prévio necessário:

Vamos olhar para o seguinte caso: $[1, 2, 3, 4, 5, 6]$ . Para reduzir o preço total dos chocolates temos que tentar remover da nossa soma o maior elemento possível; para isso, vamos agrupar os três maiores elementos $(4, 5, 6)$ . Através deles é possível notar que sempre teremos que pagar os dois maiores chocolates (que, nesse caso, são os chocolates $(5, 6)$ ), pois não existe nenhuma maneira de juntar três elementos de tal forma que o menor deles seja ou o $5$ ou o $6$ . Assim, a melhor opção é remover o $4$ e pagarmos apenas $5 + 6 = 11$ nesse grupo, restando no vetor os chocolates $[1, 2, 3]$ .

Podemos aplicar esse algoritmo novamente e pegar os três maiores elementos do vetor restante e remover o menor entre eles, pagando nesse grupo o valor de $2 + 3 = 5$ ; somando os dois grupos temos, no total, $11 + 5 = 16$ .

Caso o restante do nosso vetor tenha apenas um ou dois elementos, a nossa única opção é pagar eles. Isso ocorre pois não existe nenhuma maneira de conseguir descontos com menos de $3$ chocolates.

Segue o código:

Emoticons

Conhecimento prévio necessário:

Para esse problema, basta passarmos por todas as strings fornecidas, e verificarmos a quantidade de emoticons, como descrito no problema, nelas.

Para isso, podemos usar um laço $while$ para encontrar as strings, e encadeado nesse laço um laço $for$ para passar pelas strings, e verificar se existe algum caractere nessa string é um $:$ , e é seguido por $-$ , e caso seguido por $)$ aumentaremos o número de emoticons felizes, caso seguido por $($ aumentaremos o número de emoticons tristes. No final, basta comparar os números de cada tipo de emoticon.

Complexidade: $O(M)$ .

Segue o código, comentado, para melhor compreensão da solução!

	#include<bits/stdc++.h>
	using namespace std;
	//aqui declaramos as variáveis que precisaremos no programa
	string s;
	int numfeliz, numtriste;

	int main(){
	while(cin >> s){ //a funcao de entrada cin retorna falso quando não consegue mais ler

	if(s.length() < 3) continue; //se essa palavra tem menos de tres caracteres,
	//essa palavra com certeza não é um emoticon

	for(int i = 0; i < s.length() - 2; i++){
	if(s[i] == ':' && s[i+1] == '-' && s[i+2] == ')' ) numfeliz++;
	//somamos um no numero de emoticons felizes
	if(s[i] == ':' && s[i+1] == '-' && s[i+2] == '(' ) numtriste++;
	//somamos um no numero de emoticons tristes
	}

	}
	//comparamos os numeros de emoticons
	if(numfeliz == numtriste) cout << "neutro" << endl;
	else if(numfeliz > numtriste) cout << "divertido" << endl;
	else cout << "chateado" << endl;
	}

view raw

emoticon.cpp

hosted with ❤ by GitHub