sexta-feira, 9 de dezembro de 2011

[Programação] Telescópio - OBI 2010

Olá pessoal, nesse post irei comentar e colocar uma implementação para o problema do Telescópio, problema esse que caiu na OBI (Olimpíada Brasileira de Informática) 2010.

Link do problema no SPOJ: http://br.spoj.pl/problems/TELESCO2/

É sempre bom você tentar resolver o problema antes de ver qualquer solução ou ideias de outras pessoas referente ao problema em questão. 

Caso você tenha tentado resolver e não obteve êxito, segue abaixo a ideia para resolver o problema seguida da implementação.

Trata-se de um problema simples de resolver, se fosse para classificá-lo em um nível de dificuldade eu classificaria como fácil. Geralmente problemas com textos grandes são mais fáceis de resolver, pois no próprio texto já existem dicas de como resolvê-lo.

No texto diz que é necessário 40.000.000 de fótons por segundo para que o nosso cérebro possa perceber um objeto. As entradas do problema são as seguintes: A (área do telescópio), N (número de estrelas) e para cada estrela temos um número inteiro que representa o fluxo de fótons.

A saída do problema é só a quantidade de estrelas que podem ser visualizadas ao se utilizar o telescópio. Como saber isso? É simples, a cada fluxo de fótons de uma estrela, você irá multiplicar essa quantidade de fótons pela área (A) do telescópio. Se o resultado dessa multiplicação for maior ou igual a 40.000.000 (quantidade necessária para o cérebro perceber um objeto) então você incrementa a quantidade de estrelas.

Para você entender melhor, veja o primeiro caso de teste do problema no SPOJ:

10000 -> área do telescópio
3 -> número de estrelas
4000
3500
5100

4000*10000 = 40.000.000 (essa estrela pode ser percebida)
3500*10000 = 35.000.000 (essa estrela NÃO pode ser percebida, porque o resultado da multiplicação deu menor do que 40.000.000)
5100*10000 = 51.000.000 ( essa estrela pode ser percebida)

Conclusão: a quantidade total de estrelas que podem ser percebidas utilizando um telescópio de área 10000 milímetros quadrados é 2.

Código:



Nenhum comentário: