I was doing the Target Shooting task of the 2013 event of the Brazilian Informatics Olympiad (OBI) at Programming 2 level, which can be found here , and I managed to do it without any major difficulties. The task consisted of finding out how many points a person would make shooting at a target, considering that he would gain one point for each circumference that each shot was inside or belonged to. The program input consists of the number of circles (all whose center is located at (0,0)) and their radius and the number of shots and their coordinates. The output is just the number of points the person would make.
Well, so far so good – my code works. The problem is that in the official OBI tester, which can be found here , I received too many timed results and ended up with only 20 points out of a possible 100. Therefore, I wanted help to improve the performance of my program.
NOTE: The order of entries cannot be changed.
#!/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()
#!/usr/bin/env python # -*- coding: UTF-8 -*- def calcula_pontos(): def closure_dist2_tiro_centro(): input = raw_input().split() return (int(input) ** 2) + (int(input) ** 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()
The code above takes into account two optimizations:
- Data are calculated as soon as possible, in understanding the input list
- The second list is iterated as little as possible, considering that if a shot has a distance less than the radius of one of the circles, it has it for all the following ones.