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:
https://gist.github.com/rogerioagjr/ff24a6744ad05a789af9cca7c37d1fb8
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:
https://gist.github.com/rogerioagjr/d15249ec4ad77843479574727d325802
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:
https://gist.github.com/rogerioagjr/d392630366306e94705da93f6d5a8872
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:
https://gist.github.com/rogerioagjr/0c28bec2f03f1fed96fb1f29786f1979