Comentário NOIC OBI 2016 - Fase 1 - Programação Nível 1

Comentário por Rogério Júnior

Para ver o caderno de tarefas da primeira fase da Programação Nível 1 da OBI 2016, clique aqui.

Jogo de par ou ímpar

Conhecimento prévio necessário:

Entrada e saída (Aula 1)
Estruturas condicionais (Aula 2)

Vamos salvar os números fornecidos na entrada nos inteiros p, d1 e d2. Temos duas possibilidades: ou a soma dos números é par, ou é ímpar. Para que ela seja par, ela precisa deixar resto $0$ na divisão por dois. O operador de C++ que retorna resto na divisão é o %, ou seja (d1+d2)%2, retorna o resto da soma (d1+d2) na divisão por $2$ .

Se a soma dos números for par, ou seja, deixa $0$ na divisão por $2$ ("if((d1+d2)%2==0)"), então ganha que pediu par. Se p for $0$ ("if(p==0)"), então Alice pediu par e vai ganhar, e devemos imprimir $0$ ("printf("0\n");"). Caso p seja diferente de $0$ ("else"), então Bob pediu par e ele irá ganhar ("printf("1\n")").

Entretanto, caso a soma dos números não deixe resto $0$ na divisão por $2$ ("else"), então ela é ímpar e ganhará quem pediu ímpar. Se p for $0$ ("if(p==0)"), então Bob pediu ímpar e vai ganhar, e devemos imprimir $1$ ("printf("1\n");"). Caso p seja diferente de $0$ ("else"), então Alice pediu ímpar e ela irá ganhar ("printf("0\n")").

Segue o código para melhor entendimento:

	// Jogo de par ou ímpar - F1PJ/F1P1 - OBI 2016
	// Rogério Júnior
	// Complexidade: O(1)

	#include <cstdio> // scanf e printf

	int main(){

	// declaro as variáveis que vou usar
	int p, d1, d2;

	// leio os valores de p, d1 e d2
	scanf("%d %d %d", &p, &d1, &d2);

	// se a soma de d1 e d2 for par
	if((d1+d2)%2==0){

	// então ganhará quem pediu par

	// se Alice pediu par
	if(p==0){

	// então Alice ganha
	printf("0\n");
	}

	// caso Alice não tenha pedido par
	else{

	// então Bob ganha
	printf("1\n");
	}
	}

	// se a soma de d1 e d2 não for par
	else{

	// então quem pediu ímpar ganha

	// se Alice pediu par
	if(p==0){

	// então Bob ganha
	printf("1\n");
	}

	// se Alice não pediu par
	else{

	// então Alice ganha
	printf("0\n");
	}
	}

	// ao fim do programa, retorno 0
	return 0;
	}

view raw

jogo.cpp

hosted with ❤ by GitHub

Lâmpadas

Conhecimento prévio necessário:

Entrada e saída (Aula 1)
Estruturas condicionais (Aula 2)

Vamos usar os inteiros l1 e l2 para representar os estados das duas lâmpadas. Se l1 for $1$ , então a lâmpada A está acesa. Se l1 for $0$ , ela está apagada. De maneira análoga, a lâmpada B está acesa se l2 for $1$ , e estará apagada de ele for $0$ . Deste modo, como as duas lâmpadas começam apagadas, os dois inteiros começa com valor igual a zero.

Em seguida, vamos ler o valor de n, a quantidade de vezes que vamos apertar algum interruptor. Agora, usaremos um for para lermos cada um dos interruptores apertados. Para isso, vamos declarar o inteiro idx, que irá guardar qual interruptor foi apertado, então leremos o interruptor e guardaremos em idx.

Agora, dependendo de qual interruptor pressionamos, temos duas possibilidades: se for o primeiro interruptor (idx= $1$ ), então trocamos o estado da lâmpada A (se i1 for $1$ , irá receber $0$ , e se for $0$ receberá $1$ ("if(i1==1) i1=1; else i1=0;")). Se, entretanto, o interruptor pressionado tiver sido o B, então trocamos o estado das duas lâmpadas, da mesma maneira que fizemos com a lâmpada A, no caso anterior.

Por fim, basta imprimirmos o valores em i1 e em i2. Segue o código para melhor entendimento:

	// Lâmpadas - F1PJ/F1P1 - OBI 2016
	// Rogério Júnior
	// Complexidade: O(n)

	#include <cstdio> // scanf e printf

	int main(){

	// declaro as variáveis que irei usar
	int i1=0, i2=0, n;

	// leio a quantidade de vezes que aperto um interruptor
	scanf("%d",&n);

	// para cada vez que apertamos um interruptor
	for(int i=0;i<n;i++){

	// declaro idx
	int idx;

	// leio qual interruptor foi apertado e salvo em idx
	scanf("%d",&idx);

	// se apertei o interruptor 1
	if(idx==1){

	// troco o estado da lâmpada A

	// se ela estava acesa
	if(i1==1){

	// então a apago
	i1=0;
	}

	// caso contrário, ela estava apagada
	else{

	// então a acendo
	i1=1;
	}
	}

	// caso contrário, apertei o interruptor 2
	else{

	// troco o estado da lâmpada A

	// se ela estava acesa
	if(i1==1){

	// então a apago
	i1=0;
	}

	// caso contrário, ela estava apagada
	else{

	// então a acendo
	i1=1;
	}

	// troco o estado da lâmpada B

	// se ela estava acesa
	if(i2==1){

	// então a apago
	i2=0;
	}

	// caso contrário, ela estava apagada
	else{

	// então a acendo
	i2=1;
	}
	}
	}

	// por fim, imprimo os estados das lâmpadas
	printf("%d\n%d\n",i1,i2);

	return 0;
	}

view raw

lampadas.cpp

hosted with ❤ by GitHub

Tacos de Bilhar

Conhecimento prévio necessário

Entrada e saída (Aula 1)
Estruturas condicionais (Aula 2)
Estruturas de repetição (Aula 2)
Vetores (Aula 3)

Vamos usar dois inteiros: c indicará a quantidade de consultas e resp será a quantidade de tacos produzidos. No começo, lemos o valor de c e resp começa com valor zero. Além disso, usaremos um vetor de inteiros de nome qtd, de modo que qtd[l] guarda a quantidade de tacos de comprimento l no estoque.

Deste modo, vamos ler o valor de c e usar um for para lermos cada uma das consultas. Em cada uma delas, vamos declarar o inteiro l e nele salvar o valor do comprimento a ser consultado, que deverá ser lido da entrada. Feito isso, veremos quantos tacos temos no estoque (qtd[l]). Se tivermos pelo menos um taco ("if(qtd[l]>0)"), não precisamos produzir nenhum novo taco, mas apenas retirar um do estoque ("qtd[l]--;"). Caso contrário, ou seja, não haja tacos no estoque, então precisamos produzir mais dois e vender um, logo adicionamos dois tacos à resposta ("resp++;") e um único taco ao estoque (pois o outro foi vendido) ("qtd[l]++;").

Por fim, basta imprimirmos o valor de resp. Segue o código para melhor entendimento:

	// Tacos de bilhar - F1P1 - OBI 2016
	// Rogério Júnior
	// Complexidade: O(n)

	#include <cstdio> // scanf e printf

	#define MAXN 1000100 // defino o valor de MAXN como 1000100

	// declaro as variáveis que vou usar
	int c, resp, qtd[MAXN];

	int main(){

	// leio a quantidade de consultas
	scanf("%d", &c);

	// para cada consulta
	for(int i=0;i<c;i++){

	// leio o comprimento do taco e guardo em l
	int l;
	scanf("%d", &l);

	// se houver tacos deste no estoque, retiro um
	if(qtd[l]>0) qtd[l]--;

	// caso contrário, ou seja, não haja
	else{

	// produzo dois tacos e aumento dois à resposta
	resp+=2;

	// e aumento uma unidade dele no estoque, pois vendo a outra
	qtd[l]++;
	}
	}

	// por fim, imprimo o valor de resposta
	printf("%d\n", resp);

	return 0;
	}

view raw

tacos.cpp

hosted with ❤ by GitHub

Clube dos Cinco

Conhecimento prévio necessário

Entrada e Saída (Aula 1)
Noções básicas de Princípio da Inclusão-Exclusão (União de Conjuntos)

Observe a seguinte representação dos membros do clube:

Na representação acima, temos os seguintes valores:

$X_1$ - Quantidade de membros que praticam unicamente tiro com arco
$X_2$ - Quantidade de membros que praticam unicamente badminton
$X_3$ - Quantidade de membros que praticam unicamente canoagem
$X_4$ - Quantidade de membros que praticam unicamente tiro com arco e badmintom
$X_5$ - Quantidade de membros que praticam unicamente badminton e canoagem
$X_6$ - Quantidade de membros que praticam unicamente tiro com arco e canoagem
$X_7$ - Quantidade de membros que praticam tiro com arco, badminton e canoagem simultaneamente
$X_8$ - Quantidade de membros que não pratica nenhum esporte

Note que, para que não haja ninguém mentindo, temos as seguintes equações com as variáveis que o problema nos dá

$G=X_8$ , o número de pessoas que não praticam esportes
$X_7=0$ , ninguém pratica os três esportes
$D=X_4+X_7 \Leftrightarrow D=X_4$
$E=X_6+X_7 \Leftrightarrow E=X_6$
$F=X_5+X_7 \Leftrightarrow F=X_5$
$A=X_1+X_4+X_6+X_7 \Leftrightarrow A=X_1+D+E \Leftrightarrow A-D-E=X_1$
$B=X_2+X_4+X_5+X_7 \Leftrightarrow B=X_2+D+F \Leftrightarrow B-D-F=X_2$
$C=X_3+X_5+X_6+X_7 \Leftrightarrow C=X_3+F+E \Leftrightarrow C-F-E=X_3$

Além disso, como $N$ é a quantidade total de membros do clube, temos que:

$N=X_1+X_2+X_3+X_4+X_5+X_6+X_7+X_8$

$\Leftrightarrow N=(A-D-E)+(B-D-F)+(C-F-E)+D+F+E+0+G$

$\Leftrightarrow N=A+B+C-D-E-F+G$

Deste modo, basta checarmos a última equação: se ela for verdadeira, ninguém está mentido e ninguém participa de três esportes, mas se for falsa, há um mentiroso, que participa dos três. Segue o código para melhor entendimento:

	// Clube dos Cinco - F1P1 - OBI 2016
	// Rogério Júnior
	// Complexidade: O(1)

	#include <cstdio> // scanf e printf

	int main(){

	// declaro e leio as variáveis que vou usar
	int n, a, b, c, d, e, f, g;
	scanf("%d %d %d %d %d %d %d %d", &n, &a, &b, &c, &d, &e, &f, &g);

	// se a igualdade for verdadeira, ninguém está mentindo
	if(n==a+b+c-d-e-f+g) printf("N\n");

	// caso contrário, há um mentiroso
	else printf("S\n");

	return 0;
	}

view raw

clube.cpp

hosted with ❤ by GitHub