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:
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; | |
| } |
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; | |
| } |
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; | |
| } |
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; | |
| } |
