Оптимизация кода на python

Question

У меня была задача:

Арнольд Шварценеггер стреляет в ужасного монстра Годзиллу из дробовика. Нужно найти общую величину урона, нанесённого Годзилле выстрелом.

Подсказка: возможно, для быстрой работы программы вам пригодится алгоритм Евклида.

Формат ввода

Сначала вводится количество дробинок. Затем урон от каждой дробинки. Урон от каждой дробинки выражается простой дробью, её числитель и знаменатель вводятся на отдельных строках.

Формат вывода

Суммарный урон, выраженный простой несократимой дробью с дробной чертой между числителем и знаменателем.

Пример

Ввод
3
1
60
1
30
1
100
Вывод
3/50

Я написал следующий код:

n = int(input())  a = list()  b = list()  c = list()  for plkj in range(n):
a.append(int(input()))
b.append(int(input())) tmp = 1 lol = [] for g in b:
tmp *= g for i in range(1, tmp + 1):
tmpl = 0
for j in b:
    if i % j == 0:
        tmpl += 1
if tmpl == len(b):
    lol.append(i) for ghj in range(len(b)):
c.append(a[ghj] * (lol[0] // b[ghj])) c1 = sum(c) b1 = lol[0] while c1 != 0 and b1 != 0:
if c1 > b1:
    c1 %= b1
else:
    b1 %= c1 print(str(sum(c) // (c1 + b1)) + '/' + str(lol[0] // (c1 + b1)))

Но это решение не прошло по времени, а как оптимизировать не понимаю, буду рад помощи

Answer 1

Считаем общий знаменатель перемножением всех знаменателей: 60*30*100 = 180000
Считаем общий числитель как сумму всех числителей, перемноженных на все остальные знаменатели (кроме того, который под текущим числителем): 1*30*100+1*60*100+1*30*60 = 10800
Находим НОД общего числителя и общего знаменателя алгоритмом Евклида, он равен 3600
Делим общий числитель и общий знаменатель на НОД.

# эмуляция ввода данных
inp = """3
1
60
1
30
1
100""".split('\n')


def input(): return inp.pop(0)
# конец эмуляции ввода данных

shots = [(int(input()), int(input())) for _ in range(int(input()))]
summ_uron = 1
for n, u in shots:
    summ_uron *= u
summ_shots = 0
for n, u in shots:
    summ_shots += n * summ_uron // u

a, b = summ_uron, summ_shots

while a != 0 and b != 0:  # Алгоритм нахождения НОД делением (Алгоритм Евклида)
    if a > b:
        a = a % b
    else:
        b = b % a

nod = a + b
print(f'{summ_shots // nod}/{summ_uron // nod}')

3/50

БЛОГ НА HUSL

Оптимизация кода на python

Ответы (1 шт):