3

Eu estava fazendo a tarefa Tiro ao Alvo da prova de 2013 da Olimpíada Brasileira de Informática (OBI) do nível Programação 2, que pode ser encontrada aqui, e consegui fazer sem grandes dificuldades. A tarefa consistia em descobrir quantos pontos uma pessoa faria atirando em um alvo, considerando que ela ganharia um ponto a cada circunferência que cada tiro estivesse interno ou pertencesse. A entrada do programa consiste na quantidade de circunferências (todas cujo centro se localiza em (0,0)) e seus raios e na quantidade de tiros e suas coordenadas. A saída é apenas o número de pontos que a pessoa faria.

Bem, até aí tudo bem - meu código funciona. O problema é que no testador oficial da OBI, que pode ser encontrado aqui, eu recebi muitos resultados com tempo limite excedido e acabei com apenas 20 pontos de 100 possíveis. Queria ajuda, portanto, para melhorar a performance do meu programa.

OBS: A ordem das entradas não pode ser alterada.

#!/usr/bin/env python
# -*- coding: UTF-8 -*-

def calcula_pontos():
    qtd_circulos, qtd_tiros = raw_input().split()
    raios_circulos = [float(raw_input()) for circulo in range(int(qtd_circulos))]
    cord_tiros = [raw_input().split() for tiro in range(int(qtd_tiros))]
    pontos = 0
    for x, y in cord_tiros:
        for raio in raios_circulos:
            if((int(x) ** 2) + (int(y) ** 2) > (raio ** 2)):
                continue
            else:
                pontos += 1
    print pontos

calcula_pontos()

1 Resposta 1

1
#!/usr/bin/env python
# -*- coding: UTF-8 -*-

def calcula_pontos():

    def closure_dist2_tiro_centro():
        input = raw_input().split()
        return (int(input[0]) ** 2) + (int(input[0]) ** 2)

    qtd_circulos, qtd_tiros = raw_input().split()
    raios2_circulos = [(float(raw_input()) ** 2) for circulo in range(int(qtd_circulos))]
    dist2_tiros = [closure_dist2_tiro_centro() for tiro in range(int(qtd_tiros))]

    pontos = 0
    for tiro in dist2_tiros:
        for idx,raio in enumerate(raios2_circulos):
            if tiro < raio:
                pontos += (len(raios2_circulos) - idx)
                break
    print pontos

calcula_pontos()

O código acima leva em consideração duas otimizações:

  • Os dados são calculados tão logo quanto possível, na compreensão da lista de entrada
  • A segunda lista é iterada o mínimo possível, considerando que se um tiro tem distancia menor que o raio de um dos circulos, o tem para todos os seguintes

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .