Comentário NOIC OBI 2016 - Fase 2 - Programação Nível Júnior

Comentário por Rogério Júnior

Para ver o caderno de tarefas da segunda fase da Programação Nível Júnior da OBI 2016, clique aqui.

Este comentário utiliza os objetos cin e cout como métodos de entrada e saída. Eles estão na biblioteca iostream, do C++, e são de muito fácil uso.

Para ler uma variável qualquer a, basta a linha de código: cin >> a;

Para ler uma sequência de variáveis a, b, c, ... quaisquer, basta a linha de código: cin >> a >> b >> c >> ...;

Para imprimir uma variável qualquer a, basta a linha de código: cout << a;

Para imprimir uma sequência de variáveis a, b, c, ... quaisquer, basta a linha de código: cout << a << b << c << ...;

Medalhas

Conhecimento prévio necessário:

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

Devemos imprimir o número do atleta que terminou a prova em cada lugar. Para tal, em cada posição, basta checarmos o tempo de cada atleta e verificar se ele é quem estamos procurando. No início, vamos ler os valores da entrada e guardar nos inteiros t1, t2 e t3. Eles representarão o tempo de cada atleta, respectivamente.

Vamos checar se o primeiro atleta foi o que terminou em primeiro lugar: basta checar se o seu tempo é menor que dos outros dois (if(t1<t2 and t1<t3)). Não precisamos nos preocupar com igualdades pois o enunciado nos diz que os tempos são, necessariamente, diferentes. Caso o primeiro atleta seja de fato o primeiro colocado, imprimimos seu número (cout << "1\n";), e repetimos essa checagem com cada atleta.

Agora, basta repetirmos o mesmo processo para descobrirmos quem são o segundo e o terceiro lugar, mudando, logicamente, apenas a condição. O segundo lugar, por exemplo não tem o tempo menor que o dos outros dois, mas está entre os dois colocados, ou seja, se t1 é o segundo colocado, então ou t2>t1>t3 ou t3>t1>t2 (if((t2>t1 and t1>t3) or (t3>t1 and t1>t2))). Por fim, o último colocado deve ter um tempo maior que os outros dois.

Para cada posição, quando descobrimos qual atleta a ocupa, basta imprimirmos o número dele. Segue o código para melhor entendimento:

	// Medalhas - F2PJ - OBI 2016
	// Rogério Júnior
	// Complexidade: O(1)

	#include "iostream"

	using namespace std;

	int main(){

	int t1, t2, t3;

	cin >> t1 >> t2 >> t3;

	// vou descobrir quem é o primeiro colocado:

	if(t1<t2 and t1<t3){ // se for o atleta 1, imprimo 1

	cout << "1\n";
	}

	if(t2<t1 and t2<t3){ // se for o atleta 2, imprimo 2

	cout << "2\n";
	}

	if(t3<t1 and t3<t2){ // se for o atleta 3, imprimo 3

	cout << "3\n";
	}

	// agora, vou descobrir quem é o segundo colocado

	// nessa pate, devemos ter muito cuidado em colocar os parêntesis
	// pois temos vária condições dentro de um mesmo "if"
	// os parêntesis devem separar corretamente as condições
	// para que o coputador saiba dar a prioridade desejada ao "and" e ao "or"

	if((t2>t1 and t1>t3) or (t3>t1 and t1>t2)){ // se for o atleta 1, imprimo 1

	cout << "1\n";
	}

	if((t1>t2 and t2>t3) or (t3>t2 and t2>t1)){ // se for o atleta 2, imprimo 2

	cout << "2\n";
	}

	if((t1>t3 and t3>t2) or (t2>t3 and t3>t1)){ // se for o atleta 3, imprimo 3

	cout << "3\n";
	}

	// por fim, basta descobrir quem é o terceiro

	if(t1>t2 and t1>t3){ // se for o atleta 1, imprimo 1

	cout << "1\n";
	}

	if(t2>t1 and t2>t3){ // se for o atleta 2, imprimo 2

	cout << "2\n";
	}

	if(t3>t1 and t3>t2){ // se for o atleta 3, imprimo 3

	cout << "3\n";
	}

	return 0;
	}

view raw

medalhas.cpp

hosted with ❤ by GitHub

Gincana

Conhecimento prévio necessário

Estruturas condicionais (Aula 2)
Estruturas de repetição (Aula 2)
Algoritmo de Euclides (MDC)
Funções e recursividade (Aula 4)

Formalizando o problema, é pedido que encontremos o maior número x, que não supera M, tal que MDC(x,N)=1.

Um algoritmo bem simples, e que funciona, é percorrer os números em ordem decrescente, a partir do N, procurando o primeiro que seja primo com N (tenha MDC 1 com ele), parando a busca quando o encontramos.

De maneira geral, vamos implementar a função mdc e depois usaremos um for para percorrer os números a partir de M, em ordem decrescente, procurando um número que tenha MDC $1$ com N, parando o for quando tal número for encontrado. Se você não sabe implementar a função que calcula o MDC, veja a aula de funções.

É fácil verificar que o algoritmo funciona. Ele simplesmente procura o maior número que atenda às condições do enunciado observando todos os candidatos possíveis.

O leitor atento pode, no entanto, questionar-se acerca da complexidade de tal algoritmo, visto que, a priori, M vai até $10^{18}$ , logo, um for que começa nele e decresce pode demorar muito tempo. Porém há um fator limitante: primos! Observe que, como $2$ é o menor número primo e $2^{63} >10^{18}$ , um número menor que M só pode ser o produto de, no máximo $63$ primos, distintos, logo, o for só poderá percorrer, no máximo, $63$ primos que dividam o valor de N. Note que, se um primo não divide N, o MDC entre eles é $1$ , pois não há outros fatores primos em um primo, se não ele mesmo, que possam aparecer em N, logo, o algoritmo iria parar.

Sabemos que, em números relativamente pequenos (menos de 100 dígitos), primos são bem comuns, por isso, o intervalo percorrido pelo for, por só poder passar por $63$ primos, não é muito grande. Mais exatamente, este artigo mostra que não existem prime gaps (distâncias entre primos consecutivos) maiores que $1476$ em números até $4 \times 10^{18}$ . Deste modo, o maior intervalo que o for pode percorrer é $63 \times 1476 = 92988$ , o que não é muito grande para o computador, visto que em cada interação do for aplicaremos apenas a função mdc que é bem rápida ( $O(\log N)$ ).

Não esqueça que, pelo tamanho dos números, não podemos usar int, sendo obrigados a usarmos long long para guardar seus valores. Segue o código para melhor entendimento:

	// Medalhas - F2PJ - OBI 2016
	// Rogério Júnior
	// Complexidade: O(G(i)*log(M))

	// obs* G(i) denota max(g(i)), 1<=i<=N,
	// onde g(p_n) denota p_n-p_(n-1)
	// e p_n denota o n-ésimo primo

	#include "iostream"

	using namespace std;

	// declaro a função MDC
	long long mdc(long long a, long long b){

	// se a for menor que b, troco seus valores
	if(a<b) swap(a,b);

	// agora sei que a>=b

	// se b for zero, retorno a
	if(b==0) return a;

	// caso contrário, chamo a recursão para mdc(b,a%b)
	// seguindo o algoritmo de Euclides
	return mdc(b,a%b);
	}

	int main(){

	// declaro as variáveis n, m e resp
	long long n, m, resp;

	// leio os valores de n e m
	cin >> n >> m;

	// uso um for para percorrer os números que não superam M
	// em orem decrescente
	for(long long i=m;i>=1;i--){

	// se o MDC entr o número e N for 1
	if(mdc(i,n)==1){

	// então ele é a resposta
	resp=i;

	// e posso parar o loop
	break;
	}
	}

	// por fim, imprimo o valor da resposta
	cout << resp << "\n";

	// e retorno zero
	return 0;
	}

view raw

gincana.cpp

hosted with ❤ by GitHub

Caverna de Ordinskaya

Conhecimento prévio necessário

Estruturas condicionais (Aula 2)

A solução deste problema segue a ideia geral de um algoritmo guloso: basta sempre tentar construir a fita com o menor número e, caso ele seja menor que a medição anterior, uso a maior, pois só há duas possíveis em cada posição. Caso a maior também seja menor que a anterior, é impossível.

De maneira mais formal, seja $a_i$ o i-ésimo número da entrada e suponha que já sabemos que o valor da medição anterior ( $i-1$ ) é $s_{i-1}$ . Seja $x_i$ o menor entre $a_i$ e $M-a_i$ (o menor valor possível), e $y_i$ o maior entre $a_i$ e $M-a_i$ (o maior valor possível). Em outras palavras, $x_i=max(a_i,M-a_i)$ e $y_i=min(a_i,M-a_i)$ . Se $y \geq s_{i-1}$ , devemos utilizá-lo, ou seja determinar que $s_i=y_i$ , pois é o melhor que podemos fazer para minimizar o comprimento da corda. Se isto não for possível, então só nos resta utilizar o valor de $x_i$ ( $s_i=x_i$ ). Note que, se $x_i<s_{i-1}$ , então é impossível atribuir algum valor a $s_i$ , pois $s_{i-1}$ foi construído de modo a ter o menor valor possível.

Assim, basta guardarmos a variável resp e a variável ant. No começo, resp=ant= $0$ . Depois, usamos um for para percorrermos todas as medições. Em cada iteração i, ant será o valor de $s_{i-1}$ , e resp o atual comprimento da corda. Se for possível atribuir algum valor a $s_i$ , somamos seu tamanho a resp. Caso contrário, resp= $-1$ e paro o loop. Não podemos esquecer de atualizar o valor de ant para $s_i$ , para a próxima iteração do loop.

Por fim, basta imprimir o valor salvo em resp. Note que ant começa $0$ para que seja sempre possível usar o menor valor na primeira medição. Como a soma total pode ser, num limite bem rude, $N \times M = 5 \times 10^9$ , usaremos long long. Segue o código para melhor entendimento:

	// Caverna de Ordinskaya - F2PJ - OBI 2016
	// Rogério Júnior
	// Complexidade: O(N)

	#include "iostream"
	#include "algorithm" // min e max

	using namespace std;

	int main(){

	// declaro as variávei que vou usar
	long long n, m, resp=0, ant=0;

	// leio os valores de N e M
	cin >> n >> m;

	// para cada medição feita
	for(int i=0;i<n;i++){

	// leio o valor medido
	long long a;
	cin >> a;

	// x é o maior valor possível e y o menor
	long long x=max(a,m-a), y=min(a,m-a);

	// se possível, uso y
	if(y>=ant){

	resp+=y; // adiciono y ao comprimento total
	ant=y; // e atualizo o valor de ant
	}

	// se não, uso x
	if(y<ant and x>=ant){

	resp+=x; // adiciono x ao comprimento total
	ant=x; // e atualizo o valor de ant
	}

	// se nem x for possível, é impossível
	if(x<ant){

	resp=-1; // a respsota será -1
	break; // e dou um break no loop
	}
	}

	// por fim, imprimo a resposta
	cout << resp << "\n";

	// e retorno zero
	return 0;
	}

view raw

caverna.cpp

hosted with ❤ by GitHub

Fuga com helicóptero

Conhecimento prévio necessário:

Estruturas condicionais

Vamos fazer uma simulação da fuga do fugitivo, visto que o tamanho da pista é pequeno (apenas 16 posições). Para isso, vamos usar apenas um for e ver quem o fugitivo encontra primeiro: o helicóptero ou o policial. Suponha que o fugitivo vai na direção anti-horária. Se $i$ for sua posição atual ( $i$ começa na posição inicial do fugitivo), vamos checar se ele encontrou algum dos dois. Se ele tiver encontrado o helicóptero, então consegui fugir e imprimimos 'S'. Caso ele tenha encontrado o policial, ele não consegue, e devemos imprimir 'N'. Se qualquer um desse casos ocorrer, paramos o for. Caso o loop continue, incrementamos o valor de $i$ em uma unidade (lembre-se que consideramos o caso em que o fugitivo corre no sentido anti-horário).

Há um único caso a ser observado: se o fugitivo estiver na posição $16$ , então ele já deu uma volta completa e, na verdade, está na posição $0$ , logo, $i$ deve receber valor $0$ . Note que isso deve ser checado logo no começo do loop.

Se, no entanto, o bandido corre no sentido horário, o algoritmo é praticamente o mesmo, mas diminuímos o valor de $i$ em cada iteração do loop, ao invés de incrementá-lo. Além disso, o caso especial a ser observado (quando o fugitivo dá uma volta completa), não é mais se $i=16$ , pois o valor de $i$ começa no máximo $15$ e só decresce. Agora, vamos observar se ele é $-1$ , pois, nesse caso, deu a volta completa e, na verdade, está na posição $15$ .

Segue o código para melhor entendimento:

	// Fuga com helicóptero - F2PJ - OBI 2016
	// Rogério Júnior
	// Complexidade: O(1)

	#include "iostream"

	using namespace std;

	int main(){

	// declaro e leio os valores de h, p, f, d;
	int h, p, f, d;
	cin >> h >> p >> f >> d;

	// se a direção for anti-horária
	if(d==1){

	// para cada posição em que o fugitivo passar,
	// começando de f e aumentando a posição
	for(int i=f;;i++){

	// se tiver dado a volta completa
	if(i==16){

	// na vedade, estou na primeira posição
	i=0;
	}

	// se tiver encontrado o policial
	if(i==p){

	// imprimo 'N' e termino o loop
	cout << "N\n";
	break;
	}

	// se tiver encontrado a helicóptero
	if(i==h){

	// imprimo 'S' e termino o loop
	cout << "S\n";
	break;
	}
	}
	}

	// se a direção for horária
	if(d==-1){

	// para cada posição em que o fugitivo passar,
	// começando de f e aumentando a posição
	for(int i=f;;i--){

	// se tiver dado a volta completa
	if(i==-1){

	//na verdade, estou na última posição
	i=15;
	}

	// se tiver encontrado o policial
	if(i==p){

	// imprimo 'N' e termino o loop
	cout << "N\n";
	break;
	}

	// se tiver encontrado a helicóptero
	if(i==h){

	// imprimo 'S' e termino o loop
	cout << "S\n";
	break;
	}
	}
	}

	// por fim, retorno zero
	return 0;
	}

view raw

fuga.cpp

hosted with ❤ by GitHub